| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 117199 |
2019-06-15T10:13:42 Z |
IOrtroiii |
Cake (CEOI14_cake) |
C++14 |
|
954 ms |
11904 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 |
252 ms |
5152 KB |
Output isn't correct |
| 2 |
Correct |
199 ms |
5112 KB |
Output is correct |
| 3 |
Incorrect |
223 ms |
5112 KB |
Output isn't correct |
| 4 |
Correct |
199 ms |
5112 KB |
Output is correct |
| 5 |
Incorrect |
273 ms |
5540 KB |
Output isn't correct |
| 6 |
Correct |
241 ms |
6048 KB |
Output is correct |
| 7 |
Incorrect |
237 ms |
5648 KB |
Output isn't correct |
| 8 |
Correct |
199 ms |
5904 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
218 ms |
4012 KB |
Output isn't correct |
| 2 |
Correct |
204 ms |
3800 KB |
Output is correct |
| 3 |
Correct |
181 ms |
3680 KB |
Output is correct |
| 4 |
Correct |
2 ms |
384 KB |
Output is correct |
| 5 |
Incorrect |
288 ms |
6864 KB |
Output isn't correct |
| 6 |
Incorrect |
266 ms |
6800 KB |
Output isn't correct |
| 7 |
Correct |
213 ms |
6540 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
67 ms |
940 KB |
Output isn't correct |
| 2 |
Incorrect |
70 ms |
1024 KB |
Output isn't correct |
| 3 |
Incorrect |
123 ms |
2472 KB |
Output isn't correct |
| 4 |
Incorrect |
120 ms |
2472 KB |
Output isn't correct |
| 5 |
Incorrect |
189 ms |
1912 KB |
Output isn't correct |
| 6 |
Incorrect |
268 ms |
3480 KB |
Output isn't correct |
| 7 |
Incorrect |
278 ms |
2808 KB |
Output isn't correct |
| 8 |
Incorrect |
137 ms |
4576 KB |
Output isn't correct |
| 9 |
Incorrect |
954 ms |
11896 KB |
Output isn't correct |
| 10 |
Incorrect |
646 ms |
5288 KB |
Output isn't correct |
| 11 |
Incorrect |
730 ms |
6584 KB |
Output isn't correct |
| 12 |
Incorrect |
951 ms |
11040 KB |
Output isn't correct |
| 13 |
Incorrect |
775 ms |
11904 KB |
Output isn't correct |
