| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 391878 |
2021-04-20T04:25:46 Z |
wiwiho |
Cake (CEOI14_cake) |
C++14 |
|
2000 ms |
42032 KB |
#include <bits/stdc++.h>
#define eb emplace_back
#define mp make_pair
#define F first
#define S second
#define printv(a, b) {\
for(auto pv : a) b << pv << " ";\
b << "\n";\
}
using namespace std;
using pii = pair<int, int>;
ostream& operator<<(ostream& o, pii p){
return o << '(' << p.F << ',' << p.S << ')';
}
bool assertflag = false;
void waassert(bool t){
if(!assertflag || t) return;
cout << "OAO\n";
exit(0);
}
struct Node{
int mn = 0, mx = 0, tag = -1, d = -1, sz;
int l = -1, r = -1;
int rmn(){
if(tag == -1) return mn;
return min(tag, tag + d * (sz - 1));
}
int rmx(){
if(tag == -1) return mx;
return max(tag, tag + d * (sz - 1));
}
};
struct SegmentTree{
vector<Node> st;
int ts = 0;
int lr, rr;
void init(int n, int _lr, int _rr){
st.resize(2 * n);
lr = _lr;
rr = _rr;
}
void push(int id){
if(st[id].tag == -1) return;
int lc = st[id].l, rc = st[id].r;
st[lc].tag = st[id].tag;
st[rc].tag = st[id].tag + st[id].d * st[lc].sz;
st[lc].d = st[rc].d = st[id].d;
st[id].mn = st[id].rmn();
st[id].mx = st[id].rmx();
st[id].tag = st[id].d = -1;
}
int build(int l = -1, int r = -1){
if(l == -1) l = lr;
if(r == -1) r = rr;
int id = ts++;
st[id].sz = r - l + 1;
if(l == r) return id;
int m = (l + r) / 2;
st[id].l = build(l, m);
st[id].r = build(m + 1, r);
return id;
}
void modify(int l, int r, int f, int d = 0, int L = -1, int R = -1, int id = 0){
if(L == -1) L = lr;
if(R == -1) R = rr;
//cerr << "modify " << l << " " << r << " " << f << " " << d << " " << L << " " << R << "\n";
//waassert(L <= l && r <= R && l <= r);
if(l == L && r == R){
st[id].tag = f;
st[id].d = d;
return;
}
push(id);
int M = (L + R) / 2;
if(r <= M) modify(l, r, f, d, L, M, st[id].l);
else if(l > M) modify(l, r, f, d, M + 1, R, st[id].r);
else{
modify(l, M, f, d, L, M, st[id].l);
modify(M + 1, r, f + d * (M + 1 - l), d, M + 1, R, st[id].r);
}
st[id].mn = min(st[st[id].l].rmn(), st[st[id].r].rmn());
st[id].mx = max(st[st[id].l].rmx(), st[st[id].r].rmx());
}
int querymn(int l, int r, int L = -1, int R = -1, int id = 0){
if(L == -1) L = lr;
if(R == -1) R = rr;
waassert(L <= l && r <= R && l <= r);
if(l == L && r == R) return st[id].rmn();
push(id);
int M = (L + R) / 2;
if(r <= M) return querymn(l, r, L, M, st[id].l);
else if(l > M) return querymn(l, r, M + 1, R, st[id].r);
else{
return min(querymn(l, M, L, M, st[id].l), querymn(M + 1, r, M + 1, R, st[id].r));
}
}
int querymx(int l, int r, int L = -1, int R = -1, int id = 0){
if(L == -1) L = lr;
if(R == -1) R = rr;
waassert(L <= l && r <= R && l <= r);
if(l == L && r == R) return st[id].rmx();
push(id);
int M = (L + R) / 2;
if(r <= M) return querymx(l, r, L, M, st[id].l);
else if(l > M) return querymx(l, r, M + 1, R, st[id].r);
else{
return max(querymx(l, M, L, M, st[id].l), querymx(M + 1, r, M + 1, R, st[id].r));
}
}
};
int n, a;
void assertrange(int l, int r){
waassert(l <= r && 1 <= l && r <= n);
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n >> a;
SegmentTree pos, order;
pos.init(n, 1, n);
order.init(n, 1, n);
pos.build();
order.build();
vector<int> d(n + 1);
map<int, int, greater<>> rk;
for(int i = 1; i <= n; i++){
cin >> d[i];
rk[d[i]] = i;
}
int l = a, r = a;
pos.modify(a, a, 1);
order.modify(1, 1, a);
//printv(d, cerr);
//printv(rk, cerr);
for(int i = 2; i <= n; i++){
if(r == n){
l--;
pos.modify(l, l, i);
order.modify(i, i, l);
//cerr << l << " " << i << "\n";
}
else if(l == 1){
r++;
pos.modify(r, r, i);
order.modify(i, i, r);
//cerr << r << " " << i << "\n";
}
else if(d[l - 1] < d[r + 1]){
l--;
pos.modify(l, l, i);
order.modify(i, i, l);
//cerr << l << " " << i << "\n";
}
else{
r++;
pos.modify(r, r, i);
order.modify(i, i, r);
//cerr << r << " " << i << "\n";
}
}
//cerr << "pos ";
//for(int i = 1; i <= n; i++) cerr << pos.querymn(i, i) << " ";
//cerr << "\n";
//cerr << "order ";
//for(int i = 1; i <= n; i++) cerr << order.querymn(i, i) << " ";
//cerr << "\n";
assertflag = true;
int q;
cin >> q;
while(q--){
char c;
cin >> c;
if(c == 'F'){
int b;
cin >> b;
cout << pos.querymn(b, b) - 1 << "\n";
continue;
}
int i, e;
cin >> i >> e;
//cerr << "start " << i << " " << e << "\n";
vector<int> tmp;
for(int j = 0; j < e - 1; j++){
tmp.eb(rk.begin()->S);
rk.erase(rk.begin());
}
tmp.eb(i);
rk.erase(d[i]);
while(!tmp.empty()){
d[tmp.back()] = rk.empty() ? 1 : rk.begin()->F + 1;
rk[d[tmp.back()]] = tmp.back();
tmp.pop_back();
}
//printv(rk, cerr);
int now = i;
int nowpos = pos.querymn(now, now);
if(nowpos == 1) continue;
while(true){
int l = order.querymn(1, nowpos - 1), r = order.querymx(1, nowpos - 1);
//cerr << "test " << now << " " << l << " " << r << "\n";
if(now == l - 1){
int go = n + 1;
for(auto it = rk.begin(); it->S != now; it++){
if(it->S > r) go = min(go, it->S);
}
if(go - 1 > r){
//assertrange(r + 1, go - 1);
//assertrange(nowpos, nowpos + (go - 1) - (r + 1));
pos.modify(r + 1, go - 1, nowpos, 1);
order.modify(nowpos, nowpos + (go - 1) - (r + 1), r + 1, 1);
nowpos += go - 1 - r;
}
pos.modify(now, now, nowpos);
order.modify(nowpos, nowpos, now);
nowpos++;
if(go != n + 1) now = go;
else if(now == 1) break;
else{
pos.modify(1, now - 1, nowpos, -1);
order.modify(nowpos, n, now - 1, -1);
break;
}
}
else{
int go = 0;
for(auto it = rk.begin(); it->S != now; it++){
if(it->S < l) go = max(go, it->S);
}
if(go + 1 < l){
//assertrange(go + 1, l - 1);
//assertrange(nowpos, nowpos + (l - 1) - (go + 1));
pos.modify(go + 1, l - 1, nowpos + (l - 1) - (go + 1), -1);
order.modify(nowpos, nowpos + (l - 1) - (go + 1), l - 1, -1);
nowpos += l - 1 - go;
}
pos.modify(now, now, nowpos);
order.modify(nowpos, nowpos, now);
nowpos++;
if(go != 0) now = go;
else if(now == n) break;
else{
pos.modify(now + 1, n, nowpos, 1);
order.modify(nowpos, n, now + 1, 1);
break;
}
}
}
//cerr << "pos ";
//for(int i = 1; i <= n; i++) cerr << pos.querymn(i, i) << " ";
//cerr << "\n";
//cerr << "order ";
//for(int i = 1; i <= n; i++) cerr << order.querymn(i, i) << " ";
//cerr << "\n";
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
1656 KB |
Output isn't correct |
| 2 |
Incorrect |
10 ms |
1940 KB |
Output isn't correct |
| 3 |
Incorrect |
10 ms |
1904 KB |
Output isn't correct |
| 4 |
Incorrect |
1346 ms |
1912 KB |
Output isn't correct |
| 5 |
Incorrect |
24 ms |
4172 KB |
Output isn't correct |
| 6 |
Incorrect |
21 ms |
4340 KB |
Output isn't correct |
| 7 |
Incorrect |
54 ms |
4272 KB |
Output isn't correct |
| 8 |
Incorrect |
1470 ms |
4324 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
112 ms |
16360 KB |
Output isn't correct |
| 2 |
Incorrect |
119 ms |
16580 KB |
Output isn't correct |
| 3 |
Runtime error |
126 ms |
33208 KB |
Execution killed with signal 11 |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Correct |
413 ms |
41068 KB |
Output is correct |
| 6 |
Incorrect |
328 ms |
40448 KB |
Output isn't correct |
| 7 |
Incorrect |
254 ms |
40516 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
716 KB |
Output isn't correct |
| 2 |
Incorrect |
5 ms |
1100 KB |
Output isn't correct |
| 3 |
Incorrect |
52 ms |
8264 KB |
Output isn't correct |
| 4 |
Incorrect |
45 ms |
8332 KB |
Output isn't correct |
| 5 |
Incorrect |
2 ms |
592 KB |
Output isn't correct |
| 6 |
Incorrect |
71 ms |
10768 KB |
Output isn't correct |
| 7 |
Incorrect |
9 ms |
1868 KB |
Output isn't correct |
| 8 |
Correct |
1213 ms |
16400 KB |
Output is correct |
| 9 |
Incorrect |
324 ms |
40372 KB |
Output isn't correct |
| 10 |
Incorrect |
2 ms |
588 KB |
Output isn't correct |
| 11 |
Incorrect |
23 ms |
3540 KB |
Output isn't correct |
| 12 |
Incorrect |
246 ms |
32320 KB |
Output isn't correct |
| 13 |
Execution timed out |
2091 ms |
42032 KB |
Time limit exceeded |
