#pragma GCC optimize("Ofast", "unroll-loops")
#pragma GCC target("avx2")
#include <bits/stdc++.h>
using namespace std;
#define arr array
#define pii pair<int, int>
#define pq priority_queue
const int MX_N = 2e5 + 5;
int n;
arr<int, MX_N> vl, rq;
bool chck(int sz) {
arr<int, MX_N> scr = {0};
pq<pii, vector<pii>, greater<pii>> ord;
for (int i = 1; i <= n; i++) scr[i] = -rq[i];
for (int i = 1; i <= sz; i++) scr[vl[i]]++;
for (int i = 1; i <= n; i++) ord.push({scr[i], i});
if (ord.top().first >= 0) return true;
for (int i = sz + 1; i <= n; i++) {
scr[vl[i]]++, scr[vl[i - sz]]--;
ord.push({scr[vl[i - sz]], vl[i - sz]});
while (scr[ord.top().second] != ord.top().first) {
int j = ord.top().second; ord.pop();
ord.push({scr[j], j});
}
if (ord.top().first >= 0) return true;
}
return false;
}
int bn_srch() {
int lw = 1, hgh = n;
while (lw != hgh) {
// cout << lw << " " << hgh << endl;
int md = (lw + hgh) / 2;
if (chck(md)) hgh = md;
else lw = md + 1;
}
return ((chck(lw)) ? lw : -1);
}
int main() {
// freopen("mrt.in", "r", stdin);
int tmp1, tmp2; cin >> n >> tmp1 >> tmp2;
for (int i = 1; i <= n; i++) { cin >> vl[i]; vl[i]++; }
for (int i = 1; i <= tmp2; i++) { int x; cin >> x; cin >> rq[x + 1]; }
if (!chck(n)) { cout << "impossible" << endl; exit(0); }
int ans = bn_srch();
cout << ans << endl;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
1112 KB |
Output is correct |
2 |
Correct |
1 ms |
1116 KB |
Output is correct |
3 |
Correct |
1 ms |
1120 KB |
Output is correct |
4 |
Correct |
1 ms |
1116 KB |
Output is correct |
5 |
Correct |
1 ms |
1112 KB |
Output is correct |
6 |
Correct |
1 ms |
1116 KB |
Output is correct |
7 |
Correct |
1 ms |
1116 KB |
Output is correct |
8 |
Correct |
1 ms |
1116 KB |
Output is correct |
9 |
Correct |
1 ms |
1116 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
14 ms |
1372 KB |
Output is correct |
2 |
Correct |
3 ms |
1216 KB |
Output is correct |
3 |
Correct |
3 ms |
1372 KB |
Output is correct |
4 |
Correct |
4 ms |
1372 KB |
Output is correct |
5 |
Correct |
3 ms |
1224 KB |
Output is correct |
6 |
Correct |
9 ms |
1316 KB |
Output is correct |
7 |
Correct |
1 ms |
1120 KB |
Output is correct |
8 |
Correct |
1 ms |
1120 KB |
Output is correct |
9 |
Correct |
1 ms |
1120 KB |
Output is correct |
10 |
Correct |
1 ms |
1120 KB |
Output is correct |
11 |
Correct |
1 ms |
1120 KB |
Output is correct |
12 |
Correct |
1 ms |
1120 KB |
Output is correct |
13 |
Correct |
1 ms |
1120 KB |
Output is correct |
14 |
Correct |
1 ms |
1120 KB |
Output is correct |
15 |
Correct |
1 ms |
1120 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
198 ms |
8992 KB |
Output is correct |
2 |
Execution timed out |
2040 ms |
9284 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
245 ms |
10688 KB |
Output is correct |
2 |
Correct |
297 ms |
10556 KB |
Output is correct |
3 |
Correct |
176 ms |
10220 KB |
Output is correct |
4 |
Correct |
99 ms |
6152 KB |
Output is correct |
5 |
Correct |
98 ms |
6600 KB |
Output is correct |
6 |
Correct |
353 ms |
11140 KB |
Output is correct |
7 |
Correct |
102 ms |
9184 KB |
Output is correct |
8 |
Correct |
213 ms |
9972 KB |
Output is correct |
9 |
Correct |
195 ms |
8928 KB |
Output is correct |
10 |
Execution timed out |
2015 ms |
9288 KB |
Time limit exceeded |
11 |
Halted |
0 ms |
0 KB |
- |