23842023-01-12 09:48:51TuruTamasRendezéscpp11Időlimit túllépés 25/40372ms18672 KiB
#include <bits/stdc++.h>
using namespace std;

int N, M;

int main() {
    ios::sync_with_stdio(0); cin.tie();
    cin >> N >> M;
    vector<int> S(N);
    for (size_t i = 0; i < N; i++)
    {
        cin >> S[i];
    }
    int a, b;
    vector<pair<bool, pair<int, int>>> A(M);
    {
    vector<vector<int>> B(N);
    for (size_t i = 0; i < M; i++)
    {
        cin >> a >> b;
        a--; b--;
        for (size_t k = a; k < b + 1; k++)
        {
            B[k].push_back(i);
        }
        A[i].second = {a, b};
    }
    for (size_t i = 0; i < N; i++)
    {
        if (B[i].size() > 1) {
            for (size_t k = 0; k < B[i].size(); k++)
            {
                A[B[i][k]].first = true;
            }
        }
    }
    }
    bool f = true;
    for (pair<bool, pair<int, int>> i : A)
    {
        sort(S.begin() + i.second.first, S.begin() + i.second.second + 1);
    }
    while (f) {
        f = false;
        for (pair<bool, pair<int, int>> i : A)
        {
            if (i.first && !is_sorted(S.begin() + i.second.first, S.begin() + i.second.second + 1)) {
                sort(S.begin() + i.second.first, S.begin() + i.second.second + 1);
                f = true;
            }
        }
    }
    int counter = 0;
    for (size_t i = 0; i < S.size(); i++)
    {
        if (S[i] == i + 1) counter++;
    }
    cout << counter;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base25/40
1Elfogadva0/03ms1824 KiB
2Elfogadva0/025ms3396 KiB
3Elfogadva2/22ms2300 KiB
4Elfogadva2/22ms2436 KiB
5Elfogadva2/22ms2656 KiB
6Elfogadva2/22ms2728 KiB
7Elfogadva2/23ms3056 KiB
8Elfogadva2/23ms3260 KiB
9Elfogadva2/23ms3264 KiB
10Elfogadva2/23ms3308 KiB
11Elfogadva2/256ms15116 KiB
12Elfogadva2/248ms14852 KiB
13Elfogadva2/250ms15176 KiB
14Elfogadva1/148ms15120 KiB
15Elfogadva2/252ms15252 KiB
16Időlimit túllépés0/2372ms13064 KiB
17Időlimit túllépés0/2351ms16372 KiB
18Időlimit túllépés0/2370ms15628 KiB
19Időlimit túllépés0/2351ms15540 KiB
20Időlimit túllépés0/1347ms15108 KiB
21Időlimit túllépés0/2367ms18672 KiB
22Időlimit túllépés0/2347ms13752 KiB
23Időlimit túllépés0/2358ms15236 KiB