| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 536723 |
2022-03-14T00:32:18 Z |
LucaDantas |
Cake (CEOI14_cake) |
C++17 |
|
2000 ms |
17156 KB |
#include <bits/stdc++.h>
using namespace std;
constexpr int maxn = 2e6+10, logn = 22;
int a[maxn];
struct BIT {
int bit[maxn];
void upd(int x, int v) {
for(; x < maxn; x += x&-x)
bit[x] += v;
}
int query(int x) {
int ans = 1;
for(; x > 0; x -= x&-x)
ans += bit[x];
return ans;
}
int bs(int x) {
// quero achar o x-esimo cara ativo
int pos = 0;
for(int l = logn-1; l >= 0; l--) {
if(pos + (1 << l) >= maxn) continue;
if(bit[pos + (1 << l)] < x)
x -= bit[pos + (1 << l)], pos += 1<<l;
}
return pos+1;
}
void fill() { for(int i = 1; i < maxn; i++) bit[i] = i&-i; } // todo mundo ativado com 1
} bit;
struct Query { int x, e; } qr[maxn];
vector<pair<int,int>> op;
int main() {
int n, st; scanf("%d %d", &n, &st);
for(int i = 1; i <= n; i++)
scanf("%d", a+i), op.push_back({i, n-a[i]+1});
int q; scanf("%d", &q);
for(int i = 1; i <= q; i++) {
char c; scanf(" %c", &c);
if(c == 'E') {
scanf("%d %d", &qr[i].x, &qr[i].e);
op.push_back({n+i, qr[i].e});
} else {
int x; scanf("%d", &x);
qr[i] = {x, -1};
}
}
reverse(op.begin(), op.end());
bit.fill();
int mx = 0;
for(auto [id, e] : op) {
int val = bit.bs(e);
bit.upd(val, -1); // removo esse cara
mx = max(mx, val);
if(id > n) qr[id-n].e = val;
else a[id] = val;
}
for(auto [id, e] : op)
if(id > n) qr[id-n].e = mx-qr[id-n].e+1;
else a[id] = mx-a[id]+1;
vector<int> l, r; // salvo os dois paretos
for(int i = st+1; i <= n; i++)
if(!r.size() || a[i] > a[r.back()])
r.push_back(i);
r.push_back(n+1); a[n+1] = 0x3f3f3f3f;
for(int i = st-1; i >= 1; i--)
if(!l.size() || a[i] > a[l.back()])
l.push_back(i);
l.push_back(0); a[0] = 0x3f3f3f3f;
for(int i = 1; i <= q; i++) {
if(qr[i].e == -1) {
// query
int x = qr[i].x;
if(x == st) puts("0");
else if(x > st) {
auto mx = *(--upper_bound(r.begin(), r.end(), x));
int L = 0, R = (int)(l.size())-1, ans = 1;
while(L <= R) {
int M = (L+R) >> 1;
if(a[l[M]] > a[mx])
ans = l[M]+1, R = M-1;
else
L = M+1;
}
printf("%d\n", x - ans); // não inclui x
} else {
auto mx = *lower_bound(l.rbegin(), l.rend(), x);
int L = 0, R = (int)(r.size())-1, ans = n;
while(L <= R) {
int M = (L+R) >> 1;
if(a[r[M]] > a[mx])
ans = r[M]-1, R = M-1;
else
L = M+1;
}
printf("%d\n", ans - x); // não inclui x
}
} else {
// upd
auto [x, val] = qr[i];
a[x] = val;
/* if(x < st) swap(l, r);
vector<int> sv = {x};
while(r.size() && (x > st ? r.back() > x : r.back() < x))
sv.push_back(r.back()), r.pop_back();
for(int x : sv)
if(!r.size() || a[x] > a[r.back()])
r.push_back(x);
if(x < st) swap(l, r); */
l.clear(), r.clear();
for(int i = st+1; i <= n; i++)
if(!r.size() || a[i] > a[r.back()])
r.push_back(i);
r.push_back(n+1); a[n+1] = 0x3f3f3f3f;
for(int i = st-1; i >= 1; i--)
if(!l.size() || a[i] > a[l.back()])
l.push_back(i);
l.push_back(0); a[0] = 0x3f3f3f3f;
}
}
}
Compilation message
cake.cpp: In function 'int main()':
cake.cpp:38:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
38 | int n, st; scanf("%d %d", &n, &st);
| ~~~~~^~~~~~~~~~~~~~~~~~
cake.cpp:40:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
40 | scanf("%d", a+i), op.push_back({i, n-a[i]+1});
| ~~~~~^~~~~~~~~~~
cake.cpp:42:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
42 | int q; scanf("%d", &q);
| ~~~~~^~~~~~~~~~
cake.cpp:44:16: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
44 | char c; scanf(" %c", &c);
| ~~~~~^~~~~~~~~~~
cake.cpp:46:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
46 | scanf("%d %d", &qr[i].x, &qr[i].e);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
cake.cpp:49:16: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
49 | int x; scanf("%d", &x);
| ~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
8148 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
8148 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2095 ms |
16164 KB |
Time limit exceeded |
| 2 |
Execution timed out |
2081 ms |
16188 KB |
Time limit exceeded |
| 3 |
Execution timed out |
2096 ms |
16208 KB |
Time limit exceeded |
| 4 |
Execution timed out |
2089 ms |
16124 KB |
Time limit exceeded |
| 5 |
Execution timed out |
2088 ms |
16304 KB |
Time limit exceeded |
| 6 |
Execution timed out |
2099 ms |
16376 KB |
Time limit exceeded |
| 7 |
Execution timed out |
2096 ms |
16376 KB |
Time limit exceeded |
| 8 |
Execution timed out |
2076 ms |
16444 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
109 ms |
10848 KB |
Output is correct |
| 2 |
Correct |
79 ms |
10796 KB |
Output is correct |
| 3 |
Incorrect |
78 ms |
10656 KB |
Output isn't correct |
| 4 |
Incorrect |
5 ms |
8148 KB |
Output isn't correct |
| 5 |
Correct |
177 ms |
12680 KB |
Output is correct |
| 6 |
Incorrect |
198 ms |
12636 KB |
Output isn't correct |
| 7 |
Correct |
149 ms |
12432 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
272 ms |
9000 KB |
Output isn't correct |
| 2 |
Correct |
408 ms |
9016 KB |
Output is correct |
| 3 |
Execution timed out |
2078 ms |
9996 KB |
Time limit exceeded |
| 4 |
Execution timed out |
2089 ms |
9976 KB |
Time limit exceeded |
| 5 |
Incorrect |
496 ms |
10392 KB |
Output isn't correct |
| 6 |
Execution timed out |
2079 ms |
11036 KB |
Time limit exceeded |
| 7 |
Execution timed out |
2099 ms |
11104 KB |
Time limit exceeded |
| 8 |
Execution timed out |
2093 ms |
12608 KB |
Time limit exceeded |
| 9 |
Execution timed out |
2069 ms |
17148 KB |
Time limit exceeded |
| 10 |
Incorrect |
1707 ms |
15336 KB |
Output isn't correct |
| 11 |
Execution timed out |
2065 ms |
14560 KB |
Time limit exceeded |
| 12 |
Execution timed out |
2061 ms |
16568 KB |
Time limit exceeded |
| 13 |
Execution timed out |
2083 ms |
17156 KB |
Time limit exceeded |
