#include <bits/stdc++.h>
using namespace std;
#define FAST_IO ios_base::sync_with_stdio(0); cin.tie(nullptr)
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define REP(n) FOR(O, 1, (n))
#define f first
#define s second
#define pb push_back
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vii;
const int MAXN = 500100;
int n, a;
int d[MAXN];
int Q;
priority_queue<pii> q, tmp;
int cntE = 0;
int prec[MAXN];
int query (int b) {
return prec[b];
if (a == b)
return 0;
int le = a-1, ri = a+1;
int ans = 1;
//cout << " b = " << b << endl;
while (le > 0 || ri <= n) {
//cout << " le = " << le << " ri = " << ri << endl;
if (le == 0 || (ri <= n && d[ri] < d[le])){
if (ri == b) return ans;
ri++;
ans++;
} else {
if (le == b) return ans;
le--;
ans++;
}
}
return ans;
}
void precalc() {
prec[a] = 0;
int le = a-1, ri = a+1;
int ans = 1;
//cout << " b = " << b << endl;
while (le > 0 || ri <= n) {
//cout << " le = " << le << " ri = " << ri << endl;
if (le == 0 || (ri <= n && d[ri] < d[le])){
// if (ri == b) return ans;
prec[ri] = ans;
ri++;
ans++;
} else {
//if (le == b) return ans;
prec[le] = ans;
le--;
ans++;
}
}
}
void changeCake (int id, int e) {
int del = n-e+1;
FOR(i, 1, n) if (d[id] <= d[i] && d[i]<=del) d[i]--;
d[id] = del;
return;
cntE++;
REP(e-1) {
auto p = q.top();
q.pop();
p.f++;
d[p.s]++;
tmp.push(p);
}
d[id] = n-e+1 + cntE;
q.push({d[id], id});
while (!tmp.empty()) {
auto p = tmp.top();
tmp.pop();
q.push(p);
}
while ((int)q.size() > 10) {q.pop();}
}
int main()
{
FAST_IO;
cin >> n >> a;
FOR(i, 1, n) cin >> d[i];
FOR(i, 1, n) q.push({d[i], i});
while ((int)q.size() > 10) {q.pop();}
precalc();
cin >> Q;
while (Q--) {
char c;
cin >> c;
if (c == 'E') {
int id, e; cin >> id >> e;
changeCake (id, e);
/*cout << " d: ";
FOR(j, 1, n) cout << d[j] << " ";
cout << endl;*/
precalc();
} else {
int b; cin >> b;
cout << query (b)<< "\n";
}
}
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
2059 ms |
596 KB |
Time limit exceeded |
2 |
Execution timed out |
2071 ms |
596 KB |
Time limit exceeded |
3 |
Execution timed out |
2079 ms |
596 KB |
Time limit exceeded |
4 |
Execution timed out |
2071 ms |
596 KB |
Time limit exceeded |
5 |
Execution timed out |
2076 ms |
856 KB |
Time limit exceeded |
6 |
Execution timed out |
2085 ms |
856 KB |
Time limit exceeded |
7 |
Execution timed out |
2084 ms |
856 KB |
Time limit exceeded |
8 |
Execution timed out |
2074 ms |
856 KB |
Time limit exceeded |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
82 ms |
2568 KB |
Output is correct |
2 |
Correct |
50 ms |
2420 KB |
Output is correct |
3 |
Correct |
50 ms |
2416 KB |
Output is correct |
4 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
5 |
Correct |
156 ms |
4964 KB |
Output is correct |
6 |
Correct |
165 ms |
4940 KB |
Output is correct |
7 |
Correct |
104 ms |
4792 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
359 ms |
428 KB |
Output isn't correct |
2 |
Correct |
548 ms |
580 KB |
Output is correct |
3 |
Execution timed out |
2083 ms |
1412 KB |
Time limit exceeded |
4 |
Execution timed out |
2072 ms |
1448 KB |
Time limit exceeded |
5 |
Incorrect |
661 ms |
696 KB |
Output isn't correct |
6 |
Execution timed out |
2075 ms |
1748 KB |
Time limit exceeded |
7 |
Execution timed out |
2084 ms |
1016 KB |
Time limit exceeded |
8 |
Execution timed out |
2086 ms |
2000 KB |
Time limit exceeded |
9 |
Execution timed out |
2086 ms |
4376 KB |
Time limit exceeded |
10 |
Execution timed out |
2070 ms |
1356 KB |
Time limit exceeded |
11 |
Execution timed out |
2098 ms |
904 KB |
Time limit exceeded |
12 |
Execution timed out |
2089 ms |
3720 KB |
Time limit exceeded |
13 |
Execution timed out |
2058 ms |
4384 KB |
Time limit exceeded |