# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
546092 |
2022-04-06T10:29:35 Z |
blue |
Cake (CEOI14_cake) |
C++17 |
|
1347 ms |
27528 KB |
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
using pii = pair<int, int>;
#define sz(x) int(x.size())
int N;
vi d;
struct segtree
{
int Z;
vi l, r, mxv;
void build(int i, int L, int R)
{
// cerr << "build " << i << ' ' << L << ' ' << R << '\n';
l[i] = L;
r[i] = R;
if(l[i] == r[i])
{
// cerr << "case 1\n";
mxv[i] = d[l[i]];
}
else
{
// cerr << "case 2\n";
build(2*i, L, (L+R)/2);
build(2*i+1, (L+R)/2+1, R);
mxv[i] = max(mxv[2*i], mxv[2*i+1]);
}
// cerr << i << " -> " << l[i] << ' ' << r[i] << " : " << mxv[i] << '\n';
// cerr << "exit\n";
}
segtree()
{
Z = 4*(1+N+1);
l = r = mxv = vi(1 + Z);
build(1, 0, N+1);
}
void update(int i, int p, int v)
{
if(l[i] == r[i]) mxv[i] = v;
else
{
if(p <= (l[i] + r[i])/2) update(2*i, p, v);
else update(2*i+1, p, v);
mxv[i] = max(mxv[2*i], mxv[2*i+1]);
}
}
int rangemax(int i, int L, int R)
{
// cerr << "rangemax : " << i << ' ' << l[i] << ' ' << r[i] << " <> " << L << ' ' << R << '\n';
if(R < l[i] || r[i] < L) return -1'000'000'000;
else if(L <= l[i] && r[i] <= R) return mxv[i];
else return max(rangemax(2*i, L, R), rangemax(2*i+1, L, R));
}
int locatenextgeq(int p, int v)
{
int i = 1;
while(l[i] != r[i])
{
if(p <= (l[i] + r[i])/2)
i = 2*i;
else
i = 2*i + 1;
}
if(mxv[i] >= v) return l[i];
int rp = 1;
while(!(rp && l[i] != r[i] && mxv[2*i+1] >= v))
{
if((i & 1) == 0)
rp = 1;
else
rp = 0;
i /= 2;
}
i = 2*i + 1;
while(l[i] != r[i])
{
if(mxv[2*i] >= v)
i = 2*i;
else
i = 2*i + 1;
}
return l[i];
}
int locateprevgeq(int p, int v) //find the largest i <= p such that S[i] >= v
{
int i = 1;
while(l[i] != r[i])
{
if(p <= (l[i] + r[i])/2)
i = 2*i;
else
i = 2*i + 1;
}
if(mxv[i] >= v) return l[i];
// cerr << "positional i = " << i << '\n';
// cerr << l[i] << ' ' << r[i] << ' ' << mxv[i] << '\n';
int lp = 0;
while(!(lp && l[i] != r[i] && mxv[2*i] >= v))
{
if(i & 1) lp = 1;
else lp = 0;
i /= 2;
// cerr << i << ' ' << l[i] << ' ' << r[i] << " : " << mxv[2*i] << '\n';
if(i == 0)
{
cerr << "??????\n";
while(1);
}
}
i = 2*i;
// cerr << "resulting i = " << i << '\n';
// cerr << l[i] << ' ' << r[i] << '\n';
while(l[i] != r[i])
{
if(mxv[2*i + 1] >= v)
i = 2*i + 1;
else
i = 2*i;
}
return l[i];
}
};
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// cerr << "enter cake\n";
int a;
cin >> N >> a;
d = vi(1+N+1);
for(int i = 1; i <= N; i++) cin >> d[i];
d[0] = d[N+1] = 1'000'000'000;
int ld = N+1;
segtree S;
// cerr << "done\n";
set<pii> elements;
for(int i = 1; i <= N; i++)
elements.insert({d[i], i});
int Q;
cin >> Q;
// cerr << "\n\n";
// for(int i = 0; i <= N+1; i++) cerr << S.rangemax(1, i, i) << ' ';
// cerr << '\n';
{
vector<pii> poslist;
for(int i = 1; i <= N; i++) poslist.push_back({S.rangemax(1, i, i), i});
sort(poslist.begin(), poslist.end());
// for(pii p : poslist) cerr << p.second << ' ';
// cerr << '\n';
}
for(int j = 1; j <= Q; j++)
{
char c;
cin >> c;
if(c == 'E')
{
// cerr << "enter E\n";
int i, e;
cin >> i >> e;
elements.erase({d[i], i});
d[i] = ++ld;
// cerr << "new di = " <<
vector<pii> new_elements;
new_elements.push_back({d[i], i});
int nld = ld + e;
for(int f = 1; f <= e-1; f++)
{
auto x = *elements.rbegin();
new_elements.push_back({nld - (f-1), x.second});
elements.erase(x);
}
ld = nld + 1;
// cerr << "\n\n";
for(auto x : new_elements)
{
S.update(1, x.second, x.first);
// cerr << "score of " << x.second << " = " << x.first << '\n';
elements.insert(x);
d[x.second] = x.first;
}
// cerr << "new elements size = " << sz(new_elements) << '\n';
// cerr << "move array index " << i << " to rank = " << e << '\n';
// for(int i = 0; i <= N+1; i++) cerr << S.rangemax(1, i, i) << ' ';
// cerr << '\n';
// {
// vector<pii> poslist;
// for(int i = 1; i <= N; i++) poslist.push_back({S.rangemax(1, i, i), i});
// sort(poslist.begin(), poslist.end());
// for(pii p : poslist) cerr << p.second << ' ';
// cerr << '\n';
// }
// cerr << "exit E\n";
}
else
{
// cerr << "enter F\n";
int b;
cin >> b;
if(a == b)
{
cout << 0 << '\n';
continue;
}
if(a < b)
{
// cerr << "hello " << a << ' ' << b << " \n";
int rmx = S.rangemax(1, a+1, b);
// cerr << "rmx = " << rmx << '\n';
// cerr << "rmx = " << rmx << '\n';
// cerr << "a-1 = " << a-1 << '\n';
// cerr << "locate prev geq " << a-1 << ' ' << rmx+1 << '\n';
int prvp = S.locateprevgeq(a-1, rmx);
// cerr << "prvp = " << prvp << '\n';
cout << b - prvp - 1 << '\n';
}
else
{
// cerr << "!\n";
int rmx = S.rangemax(1, b, a-1);
// cerr << "rmx = " << rmx << '\n';
// cerr << "rmx = " << rmx << '\n';
int nxtp = S.locatenextgeq(a+1, rmx);
// cerr << "nxtp = " << nxtp << '\n';
cout << nxtp - b - 1 << '\n';
}
// cerr << "exit F\n";
}
}
// cerr << "exit cake\n";
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
320 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
6 ms |
468 KB |
Output is correct |
5 |
Correct |
19 ms |
1664 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
599 ms |
1844 KB |
Output is correct |
2 |
Correct |
331 ms |
1944 KB |
Output is correct |
3 |
Correct |
390 ms |
1940 KB |
Output is correct |
4 |
Correct |
196 ms |
1944 KB |
Output is correct |
5 |
Correct |
631 ms |
3364 KB |
Output is correct |
6 |
Correct |
533 ms |
3460 KB |
Output is correct |
7 |
Correct |
415 ms |
3388 KB |
Output is correct |
8 |
Correct |
254 ms |
3408 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
123 ms |
11736 KB |
Output is correct |
2 |
Correct |
102 ms |
11668 KB |
Output is correct |
3 |
Correct |
87 ms |
11704 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
268 ms |
27440 KB |
Output is correct |
6 |
Correct |
256 ms |
27420 KB |
Output is correct |
7 |
Correct |
161 ms |
27528 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
62 ms |
968 KB |
Output is correct |
2 |
Correct |
42 ms |
1268 KB |
Output is correct |
3 |
Correct |
115 ms |
5996 KB |
Output is correct |
4 |
Correct |
145 ms |
6096 KB |
Output is correct |
5 |
Correct |
163 ms |
1332 KB |
Output is correct |
6 |
Correct |
197 ms |
8132 KB |
Output is correct |
7 |
Correct |
161 ms |
2348 KB |
Output is correct |
8 |
Correct |
276 ms |
11740 KB |
Output is correct |
9 |
Correct |
1347 ms |
27480 KB |
Output is correct |
10 |
Correct |
553 ms |
2228 KB |
Output is correct |
11 |
Correct |
737 ms |
4272 KB |
Output is correct |
12 |
Correct |
1279 ms |
22592 KB |
Output is correct |
13 |
Correct |
868 ms |
27448 KB |
Output is correct |