| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 117201 |
2019-06-15T10:24:08 Z |
IOrtroiii |
Cake (CEOI14_cake) |
C++14 |
|
986 ms |
6028 KB |
#include <bits/stdc++.h>
using namespace std;
const int N = 250250;
int n, start, q;
int a[N];
vector<int> top10;
bool intop[N];
int t[N << 2];
void build(int v, int l, int r) {
if (l == r) {
if (!intop[l]) {
t[v] = a[l];
}
return;
}
int md = (l + r) >> 1;
build(v << 1, l, md);
build(v << 1 | 1, md + 1, r);
t[v] = max(t[v << 1], t[v << 1 | 1]);
}
void upd(int v, int l, int r, int pos, int val) {
if (pos > r || pos < l) return;
if (l == r) {
t[v] = val;
return;
}
int md = (l + r) >> 1;
upd(v << 1, l, md, pos, val);
upd(v << 1 | 1, md + 1, r, pos, val);
t[v] = max(t[v << 1], t[v << 1 | 1]);
}
int get(int v, int l, int r, int L, int R) {
if (L > r || R < l) return -N << 6;
if (L <= l && r <= R) return t[v];
int md = (l + r) >> 1;
return max(get(v << 1, l, md, L, R), get(v << 1 | 1, md + 1, r, L, R));
}
int findL(int v, int l, int r, int pos, int val) {
if (l > pos || t[v] <= val) return 0;
if (l == r) return l;
int md = (l + r) >> 1;
int ans = findL(v << 1 | 1, md + 1, r, pos, val);
if (ans == 0) return findL(v << 1, l, md, pos, val);
return ans;
}
int findR(int v, int l, int r, int pos, int val) {
if (r < pos || t[v] <= val) return n + 1;
if (l == r) return l;
int md = (l + r) >> 1;
int ans = findR(v << 1, l, md, pos, val);
if (ans == n + 1) findR(v << 1 | 1, md + 1, r, pos, val);
return ans;
}
int main() {
ios_base::sync_with_stdio(false);
cin >> n >> start;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
top10.push_back(i);
}
sort(top10.begin(), top10.end(), [&](int x, int y) {
return a[x] > a[y];
});
while (top10.size() > 10) top10.pop_back();
for (int v : top10) intop[v] = true;
build(1, 1, n);
cin >> q;
while (q--) {
char op;
cin >> op;
if (op == 'E') {
int pos, rnk;
cin >> pos >> rnk;
--rnk;
vector<int> ntop10;
for (int i = 0; i < rnk; ++i) {
++a[top10[i]];
ntop10.push_back(top10[i]);
}
a[pos] = a[top10[rnk]] + 1;
if (!intop[pos]) {
ntop10.push_back(pos);
for (int i = rnk; i + 1 < top10.size(); ++i) {
ntop10.push_back(top10[i]);
}
intop[pos] = true;
intop[top10.back()] = false;
upd(1, 1, n, pos, 0);
upd(1, 1, n, top10.back(), a[top10.back()]);
} else {
ntop10.push_back(pos);
for (int i = rnk; i < top10.size(); ++i) {
if (top10[i] != pos) {
ntop10.push_back(top10[i]);
}
}
}
top10.swap(ntop10);
} else {
int pos;
cin >> pos;
if (pos == start) {
cout << "0\n";
} else if (pos < start) {
int ans = start - pos;
int val = get(1, 1, n, pos, start - 1);
for (int v : top10) {
if (pos <= v && v < start) val = max(val, a[v]);
}
int last = findR(1, 1, n, start + 1, val);
for (int v : top10) {
if (start < v && a[v] > val) {
last = min(last, v);
}
}
ans += (last - 1 - start);
cout << ans << "\n";
} else {
int ans = pos - start;
int val = get(1, 1, n, start + 1, pos);
for (int v : top10) {
if (start < v && v <= pos) val = max(val, a[v]);
}
int last = findL(1, 1, n, start - 1, val);
for (int v : top10) {
if (v < start && a[v] > val) {
last = max(last, v);
}
}
ans += (start - 1 - last);
cout << ans << "\n";
}
}
}
}
Compilation message
cake.cpp: In function 'int main()':
cake.cpp:92:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = rnk; i + 1 < top10.size(); ++i) {
~~~~~~^~~~~~~~~~~~~~
cake.cpp:101:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = rnk; i < top10.size(); ++i) {
~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
239 ms |
1024 KB |
Output isn't correct |
| 2 |
Correct |
196 ms |
1024 KB |
Output is correct |
| 3 |
Incorrect |
223 ms |
1024 KB |
Output isn't correct |
| 4 |
Correct |
198 ms |
1024 KB |
Output is correct |
| 5 |
Incorrect |
257 ms |
1280 KB |
Output isn't correct |
| 6 |
Correct |
237 ms |
1280 KB |
Output is correct |
| 7 |
Incorrect |
253 ms |
1408 KB |
Output isn't correct |
| 8 |
Correct |
206 ms |
1280 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
232 ms |
3116 KB |
Output isn't correct |
| 2 |
Correct |
322 ms |
2908 KB |
Output is correct |
| 3 |
Correct |
191 ms |
2812 KB |
Output is correct |
| 4 |
Correct |
2 ms |
384 KB |
Output is correct |
| 5 |
Incorrect |
285 ms |
4976 KB |
Output isn't correct |
| 6 |
Incorrect |
262 ms |
4848 KB |
Output isn't correct |
| 7 |
Correct |
212 ms |
4844 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
67 ms |
936 KB |
Output isn't correct |
| 2 |
Incorrect |
71 ms |
1016 KB |
Output isn't correct |
| 3 |
Incorrect |
131 ms |
1852 KB |
Output isn't correct |
| 4 |
Incorrect |
126 ms |
1832 KB |
Output isn't correct |
| 5 |
Incorrect |
191 ms |
1144 KB |
Output isn't correct |
| 6 |
Incorrect |
244 ms |
2152 KB |
Output isn't correct |
| 7 |
Incorrect |
264 ms |
1528 KB |
Output isn't correct |
| 8 |
Incorrect |
141 ms |
2676 KB |
Output isn't correct |
| 9 |
Incorrect |
986 ms |
5896 KB |
Output isn't correct |
| 10 |
Incorrect |
643 ms |
2040 KB |
Output isn't correct |
| 11 |
Incorrect |
712 ms |
2780 KB |
Output isn't correct |
| 12 |
Incorrect |
947 ms |
5800 KB |
Output isn't correct |
| 13 |
Incorrect |
719 ms |
6028 KB |
Output isn't correct |
