| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 112532 |
2019-05-20T12:39:01 Z |
KCSC |
Cake (CEOI14_cake) |
C++14 |
|
1583 ms |
17048 KB |
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 250005;
int val[NMAX], sgt[NMAX << 2];
set<pair<int, int>> mst;
inline bool cmp(int x, int y) {
return val[x] < val[y]; }
void build(int nod, int lef, int rig) {
if (lef == rig) {
sgt[nod] = val[lef]; }
else {
int mid = (lef + rig) >> 1;
build(nod << 1, lef, mid);
build(nod << 1 | 1, mid + 1, rig);
sgt[nod] = max(sgt[nod << 1], sgt[nod << 1 | 1]); } }
void update(int nod, int lef, int rig, int ps) {
if (lef == rig) {
sgt[nod] = val[ps]; }
else {
int mid = (lef + rig) >> 1;
if (ps <= mid) {
update(nod << 1, lef, mid, ps); }
else {
update(nod << 1 | 1, mid + 1, rig, ps); }
sgt[nod] = max(sgt[nod << 1], sgt[nod << 1 | 1]); } }
int query(int nod, int lef, int rig, int st, int en) {
if (rig < st or en < lef) {
return -1; }
if (st <= lef and rig <= en) {
return sgt[nod]; }
else {
int mid = (lef + rig) >> 1;
return max(query(nod << 1, lef, mid, st, en),
query(nod << 1 | 1, mid + 1, rig, st, en)); } }
int binarySearchLeft(int nod, int lef, int rig, int st, int en, int val) {
if (rig < st or en < lef or sgt[nod] <= val) {
return -1; }
else if (lef == rig) {
return lef; }
else {
int mid = (lef + rig) >> 1;
int ans = binarySearchLeft(nod << 1 | 1, mid + 1, rig, st, en, val);
if (ans == -1) {
ans = binarySearchLeft(nod << 1, lef, mid, st, en, val); }
return ans; } }
int binarySearchRight(int nod, int lef, int rig, int st, int en, int val) {
if (rig < st or en < lef or sgt[nod] <= val) {
return -1; }
else if (lef == rig) {
return lef; }
else {
int mid = (lef + rig) >> 1;
int ans = binarySearchRight(nod << 1, lef, mid, st, en, val);
if (ans == -1) {
ans = binarySearchRight(nod << 1 | 1, mid + 1, rig, st, en, val); }
return ans; } }
int main(void) {
#ifdef HOME
freopen("cake.in", "r", stdin);
freopen("cake.out", "w", stdout);
#endif
int N, P; scanf("%d %d", &N, &P);
val[0] = val[N + 1] = (int) 1e7;
for (int i = 1; i <= N; ++i) {
scanf("%d", &val[i]);
mst.insert(make_pair(val[i], i)); }
build(1, 0, N + 1);
int Q; scanf("%d", &Q);
while (Q--) {
char ch; scanf("\n%c ", &ch);
if (ch == 'E') {
int pos, kth; scanf("%d %d", &pos, &kth);
vector<pair<int, int>> axs;
for (int i = 0; i < kth; ++i) {
pair<int, int> aux = *mst.rbegin();
axs.push_back(aux); mst.erase(aux); }
int axp = -1;
for (int i = 0; i < kth; ++i) {
if (axs[i].second == pos) {
axp = i; } }
if (axp != -1) {
for (; axp + 1 < kth; ++axp) {
swap(axs[axp + 1].first, axs[axp].first); }
for (int i = 0; i < kth; ++i) {
val[axs[i].second] = axs[i].first;
mst.insert(axs[i]);
update(1, 0, N + 1, axs[i].second); } }
else {
mst.erase(make_pair(val[pos], pos));
val[pos] = axs[kth - 1].first + 1;
mst.insert(make_pair(val[pos], pos));
update(1, 0, N + 1, pos);
for (int i = 0; i + 1 < kth; ++i) {
val[axs[i].second] = ++axs[i].first;
mst.insert(axs[i]);
update(1, 0, N + 1, axs[i].second); }
mst.insert(axs[kth - 1]); } }
else {
int pos; scanf("%d", &pos);
if (pos == P) {
printf("0\n"); }
else if (pos < P) {
printf("%d\n", binarySearchRight(1, 0, N + 1, P + 1, N + 1, query(1, 0, N + 1, pos, P - 1)) - pos - 1); }
else {
printf("%d\n", pos - binarySearchLeft(1, 0, N + 1, 0, P - 1, query(1, 0, N + 1, P + 1, pos)) - 1); } } }
return 0; }
Compilation message
cake.cpp: In function 'int main()':
cake.cpp:71:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int N, P; scanf("%d %d", &N, &P);
~~~~~^~~~~~~~~~~~~~~~~
cake.cpp:74:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &val[i]);
~~~~~^~~~~~~~~~~~~~~
cake.cpp:77:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int Q; scanf("%d", &Q);
~~~~~^~~~~~~~~~
cake.cpp:79:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
char ch; scanf("\n%c ", &ch);
~~~~~^~~~~~~~~~~~~~
cake.cpp:81:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int pos, kth; scanf("%d %d", &pos, &kth);
~~~~~^~~~~~~~~~~~~~~~~~~~~
cake.cpp:108:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int pos; scanf("%d", &pos);
~~~~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
Output is correct |
| 2 |
Correct |
2 ms |
256 KB |
Output is correct |
| 3 |
Correct |
3 ms |
384 KB |
Output is correct |
| 4 |
Correct |
8 ms |
384 KB |
Output is correct |
| 5 |
Correct |
21 ms |
1024 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
736 ms |
988 KB |
Output is correct |
| 2 |
Correct |
448 ms |
1020 KB |
Output is correct |
| 3 |
Correct |
530 ms |
896 KB |
Output is correct |
| 4 |
Correct |
316 ms |
1024 KB |
Output is correct |
| 5 |
Correct |
881 ms |
1876 KB |
Output is correct |
| 6 |
Correct |
753 ms |
1920 KB |
Output is correct |
| 7 |
Correct |
615 ms |
1920 KB |
Output is correct |
| 8 |
Correct |
417 ms |
1920 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
143 ms |
7100 KB |
Output is correct |
| 2 |
Correct |
98 ms |
6976 KB |
Output is correct |
| 3 |
Correct |
89 ms |
6904 KB |
Output is correct |
| 4 |
Correct |
2 ms |
384 KB |
Output is correct |
| 5 |
Correct |
345 ms |
15864 KB |
Output is correct |
| 6 |
Correct |
334 ms |
15888 KB |
Output is correct |
| 7 |
Correct |
152 ms |
15568 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
68 ms |
632 KB |
Output is correct |
| 2 |
Correct |
50 ms |
768 KB |
Output is correct |
| 3 |
Correct |
140 ms |
3632 KB |
Output is correct |
| 4 |
Correct |
170 ms |
3732 KB |
Output is correct |
| 5 |
Correct |
197 ms |
760 KB |
Output is correct |
| 6 |
Correct |
256 ms |
4756 KB |
Output is correct |
| 7 |
Correct |
206 ms |
1568 KB |
Output is correct |
| 8 |
Correct |
400 ms |
6520 KB |
Output is correct |
| 9 |
Correct |
1583 ms |
16872 KB |
Output is correct |
| 10 |
Correct |
629 ms |
1664 KB |
Output is correct |
| 11 |
Correct |
863 ms |
3024 KB |
Output is correct |
| 12 |
Correct |
1539 ms |
14324 KB |
Output is correct |
| 13 |
Correct |
1138 ms |
17048 KB |
Output is correct |
