# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
553242 |
2022-04-25T07:36:10 Z |
Aldas25 |
Cake (CEOI14_cake) |
C++14 |
|
2000 ms |
1048576 KB |
#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) {
//cntE++;
REP(e-1) {
auto p = q.top();
q.pop();
p.f++;
d[p.s]++;
tmp.push(p);
}
int x = q.top().f;
d[id] = x+1;
while (!q.empty()) {
auto p = q.top();
q.pop();
if (p.s != id) tmp.push(p);
}
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;I*/
//precalc();
//cout << " prec: ";
//FOR(j, 1, n) cout << prec[j] << " ";
//cout << endl;
} else {
int b; cin >> b;
cout << query (b)<< "\n";
}
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
1375 ms |
1048576 KB |
Execution killed with signal 9 |
2 |
Incorrect |
214 ms |
4812 KB |
Output isn't correct |
3 |
Incorrect |
261 ms |
4860 KB |
Output isn't correct |
4 |
Incorrect |
222 ms |
4728 KB |
Output isn't correct |
5 |
Runtime error |
1214 ms |
1048576 KB |
Execution killed with signal 9 |
6 |
Incorrect |
280 ms |
5668 KB |
Output isn't correct |
7 |
Incorrect |
227 ms |
5472 KB |
Output isn't correct |
8 |
Incorrect |
227 ms |
5728 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
2074 ms |
2632 KB |
Time limit exceeded |
2 |
Execution timed out |
2059 ms |
2576 KB |
Time limit exceeded |
3 |
Incorrect |
914 ms |
2596 KB |
Output isn't correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Execution timed out |
2025 ms |
4244 KB |
Time limit exceeded |
6 |
Execution timed out |
2039 ms |
4276 KB |
Time limit exceeded |
7 |
Incorrect |
439 ms |
4416 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
63 ms |
888 KB |
Output isn't correct |
2 |
Incorrect |
81 ms |
844 KB |
Output isn't correct |
3 |
Incorrect |
1008 ms |
2296 KB |
Output isn't correct |
4 |
Incorrect |
913 ms |
2244 KB |
Output isn't correct |
5 |
Incorrect |
136 ms |
1512 KB |
Output isn't correct |
6 |
Execution timed out |
2072 ms |
3104 KB |
Time limit exceeded |
7 |
Incorrect |
583 ms |
2640 KB |
Output isn't correct |
8 |
Incorrect |
186 ms |
4188 KB |
Output isn't correct |
9 |
Execution timed out |
2016 ms |
4796 KB |
Time limit exceeded |
10 |
Incorrect |
437 ms |
2432 KB |
Output isn't correct |
11 |
Execution timed out |
2078 ms |
5232 KB |
Time limit exceeded |
12 |
Execution timed out |
2066 ms |
4564 KB |
Time limit exceeded |
13 |
Execution timed out |
2055 ms |
692984 KB |
Time limit exceeded |