#include <bits/stdc++.h>
using namespace std;
#define InTheNameOfGod cin.tie(0); ios::sync_with_stdio(0);
#define inv pair<int, int>
void print(vector<int> &s)
{
for(auto &x : s)
cout << x << " ";
cout << "\n";
}
void print(vector<inv> &s)
{
for(auto &x : s)
cout << x.first << ":" << x.second << " ";
cout << "\n";
}
int main()
{
InTheNameOfGod
int n, k, c = 0;
cin >> n >> k;
vector<int> s(n+2);
for(int i = 1; i <= n; i++)
{
cin >> s[i];
}
vector<inv> ss;
ss.reserve(k);
queue<inv> done;
for(int i = 0, a, b; i < k; i++)
{
cin >> a >> b;
ss.push_back({a, b});
}
sort(ss.begin(), ss.end());
inv z(-1, -1);
for(inv &x : ss)
{
if(x.first <= z.second)
{
z.second = max(z.second, x.second);
continue;
}
done.push(z);
z.first = x.first;
z.second = x.second;
}
done.push(z);
done.pop();
while(!done.empty())
{
z = done.front();
done.pop();
sort(s.begin()+z.first, s.begin()+z.second+1);
}
for(int i = 1; i <= n; i++)
{
c = i == s[i] ? c+1 : c;
}
cout << c << "\n";
return 0;
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
base | 40/40 | ||||||
1 | Elfogadva | 0/0 | 3ms | 1828 KiB | |||
2 | Elfogadva | 0/0 | 8ms | 2312 KiB | |||
3 | Elfogadva | 2/2 | 2ms | 2220 KiB | |||
4 | Elfogadva | 2/2 | 2ms | 2424 KiB | |||
5 | Elfogadva | 2/2 | 2ms | 2632 KiB | |||
6 | Elfogadva | 2/2 | 2ms | 2856 KiB | |||
7 | Elfogadva | 2/2 | 2ms | 2928 KiB | |||
8 | Elfogadva | 2/2 | 2ms | 3052 KiB | |||
9 | Elfogadva | 2/2 | 2ms | 3276 KiB | |||
10 | Elfogadva | 2/2 | 3ms | 3608 KiB | |||
11 | Elfogadva | 2/2 | 46ms | 6712 KiB | |||
12 | Elfogadva | 2/2 | 46ms | 7192 KiB | |||
13 | Elfogadva | 2/2 | 46ms | 7244 KiB | |||
14 | Elfogadva | 1/1 | 46ms | 7312 KiB | |||
15 | Elfogadva | 2/2 | 46ms | 7412 KiB | |||
16 | Elfogadva | 2/2 | 48ms | 6700 KiB | |||
17 | Elfogadva | 2/2 | 50ms | 6552 KiB | |||
18 | Elfogadva | 2/2 | 50ms | 6608 KiB | |||
19 | Elfogadva | 2/2 | 50ms | 6808 KiB | |||
20 | Elfogadva | 1/1 | 50ms | 7016 KiB | |||
21 | Elfogadva | 2/2 | 48ms | 6964 KiB | |||
22 | Elfogadva | 2/2 | 48ms | 6960 KiB | |||
23 | Elfogadva | 2/2 | 48ms | 7024 KiB |