| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 454956 |
2021-08-05T10:50:18 Z |
kingfran1907 |
Cake (CEOI14_cake) |
C++14 |
|
697 ms |
16484 KB |
#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;
typedef long long llint;
const int maxn = 3e5+10;
const int base = 31337;
const int mod = 1e9+7;
const llint inf = (1LL << 55);
const int logo = 18;
const int off = 1 << logo;
const int treesiz = off << 1;
struct tournament {
llint tour[treesiz];
tournament() {
for (int i = 0; i < treesiz; i++)
tour[i] = inf;
}
void update(int x, llint val) {
x += off;
tour[x] = val;
x /= 2;
while (x > 0) tour[x] = max(tour[x * 2], tour[x * 2 + 1]), x /= 2;
}
llint query(int a, int b, int l, int r, int node) {
if (l > b || r < a) return -inf;
if (l >= a && r <= b) return tour[node];
int mid = (l + r) / 2;
return max(query(a, b, l, mid, node * 2), query(a, b, mid + 1, r, node * 2 + 1));
}
int fin(int l, int r, int node, llint val) {
if (l == r) return l;
int mid = (l + r) / 2;
//printf("looking: (%d %d) %d (%d) --> %lld %lld\n", l, r, node, val, tour[node * 2], tour[node * 2 + 1]);
if (tour[node * 2] < val) return fin(mid + 1, r, node * 2 + 1, val);
return fin(l, mid, node * 2, val);
}
} lef, rig;
int n, q;
int a;
llint niz[maxn];
void update(int x, llint val) {
if (x <= a) lef.update(a - x, val);
else rig.update(x - a - 1, val);
}
int main() {
scanf("%d%d", &n, &a); a--;
for (int i = 0; i < n; i++) {
scanf("%lld", niz+i);
}
for (int i = 0; i < n; i++) update(i, niz[i]);
set< pair<llint, int> > s;
for (int i = 0; i < n; i++) {
s.insert(make_pair(-niz[i], i));
while (s.size() > 11) s.erase(--s.end());
}
scanf("%d", &q);
while (q--) {
char type;
scanf(" %c", &type);
if (type == 'E') {
int ind, pos;
scanf("%d%d", &ind, &pos); ind--;
vector< int > v;
llint val = s.begin()->first; val *= -1;
for (int i = 0; i < pos - 1; i++) {
int tr = s.begin()->second;
s.erase(s.begin());
niz[tr] = val + pos - i;
v.push_back(tr);
}
s.erase(make_pair(-niz[ind], ind));
niz[ind] = val + 1;
s.insert(make_pair(-niz[ind], ind));
update(ind, niz[ind]);
for (int tren : v) {
update(tren, niz[tren]);
s.insert(make_pair(-niz[tren], tren));
}
while (s.size() > 11) s.erase(--s.end());
} else {
int x;
scanf("%d", &x); x--;
if (x == a) printf("0\n");
else if (x <= a) {
int sol = a - x;
int maxi = lef.query(0, a - x, 0, off - 1, 1);
int kol = rig.fin(0, off - 1, 1, maxi);
printf("%d\n", sol + kol);
} else {
int sol = x - a - 1;
llint maxi = rig.query(0, x - a - 1, 0, off - 1, 1);
int kol = lef.fin(0, off - 1, 1, maxi);
printf("%d\n", sol + kol);
}
}
}
return 0;
}
Compilation message
cake.cpp: In function 'int main()':
cake.cpp:60:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
60 | scanf("%d%d", &n, &a); a--;
| ~~~~~^~~~~~~~~~~~~~~~
cake.cpp:62:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
62 | scanf("%lld", niz+i);
| ~~~~~^~~~~~~~~~~~~~~
cake.cpp:73:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
73 | scanf("%d", &q);
| ~~~~~^~~~~~~~~~
cake.cpp:76:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
76 | scanf(" %c", &type);
| ~~~~~^~~~~~~~~~~~~~
cake.cpp:80:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
80 | scanf("%d%d", &ind, &pos); ind--;
| ~~~~~^~~~~~~~~~~~~~~~~~~~
cake.cpp:103:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
103 | scanf("%d", &x); x--;
| ~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
8396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
491 ms |
12532 KB |
Output is correct |
| 2 |
Incorrect |
341 ms |
12288 KB |
Output isn't correct |
| 3 |
Correct |
351 ms |
12540 KB |
Output is correct |
| 4 |
Correct |
249 ms |
8564 KB |
Output is correct |
| 5 |
Correct |
504 ms |
12788 KB |
Output is correct |
| 6 |
Incorrect |
481 ms |
13168 KB |
Output isn't correct |
| 7 |
Correct |
513 ms |
13044 KB |
Output is correct |
| 8 |
Correct |
243 ms |
8688 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
106 ms |
9800 KB |
Output isn't correct |
| 2 |
Incorrect |
85 ms |
9668 KB |
Output isn't correct |
| 3 |
Incorrect |
75 ms |
9648 KB |
Output isn't correct |
| 4 |
Incorrect |
5 ms |
8396 KB |
Output isn't correct |
| 5 |
Correct |
127 ms |
11076 KB |
Output is correct |
| 6 |
Incorrect |
135 ms |
11056 KB |
Output isn't correct |
| 7 |
Incorrect |
112 ms |
10928 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
81 ms |
8568 KB |
Output isn't correct |
| 2 |
Incorrect |
41 ms |
8672 KB |
Output isn't correct |
| 3 |
Incorrect |
76 ms |
9388 KB |
Output isn't correct |
| 4 |
Incorrect |
97 ms |
9284 KB |
Output isn't correct |
| 5 |
Incorrect |
147 ms |
9576 KB |
Output isn't correct |
| 6 |
Incorrect |
135 ms |
10444 KB |
Output isn't correct |
| 7 |
Incorrect |
143 ms |
10224 KB |
Output isn't correct |
| 8 |
Correct |
214 ms |
10820 KB |
Output is correct |
| 9 |
Incorrect |
697 ms |
16484 KB |
Output isn't correct |
| 10 |
Incorrect |
516 ms |
12924 KB |
Output isn't correct |
| 11 |
Incorrect |
567 ms |
13900 KB |
Output isn't correct |
| 12 |
Correct |
680 ms |
16048 KB |
Output is correct |
| 13 |
Correct |
608 ms |
16452 KB |
Output is correct |
