| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 391901 |
2021-04-20T05:40:52 Z |
wiwiho |
Cake (CEOI14_cake) |
C++14 |
|
1169 ms |
105672 KB |
#pragma GCC optimize("Ofast")
#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 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 lr, rr;
void init(int n, int _lr, int _rr){
st.resize(4 * n);
lr = _lr;
rr = _rr;
}
void push(int id){
if(st[id].tag == -1) return;
int lc = 2 * id + 1, rc = 2 * id + 2;
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;
}
void build(int l = -1, int r = -1, int id = 0){
if(l == -1) l = lr;
if(r == -1) r = rr;
st[id].sz = r - l + 1;
if(l == r) return;
int m = (l + r) / 2;
build(l, m, 2 * id + 1);
build(m + 1, r, 2 * id + 2);
}
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, 2 * id + 1);
else if(l > M) modify(l, r, f, d, M + 1, R, 2 * id + 2);
else{
modify(l, M, f, d, L, M, 2 * id + 1);
modify(M + 1, r, f + d * (M + 1 - l), d, M + 1, R, 2 * id + 2);
}
st[id].mn = min(st[2 * id + 1].rmn(), st[2 * id + 1].rmn());
st[id].mx = max(st[2 * id + 2].rmx(), st[2 * id + 2].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, 2 * id + 1);
else if(l > M) return querymn(l, r, M + 1, R, 2 * id + 2);
else{
return min(querymn(l, M, L, M, 2 * id + 1), querymn(M + 1, r, M + 1, R, 2 * id + 2));
}
}
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, 2 * id + 1);
else if(l > M) return querymx(l, r, M + 1, R, 2 * id + 2);
else{
return max(querymx(l, M, L, M, 2 * id + 1), querymx(M + 1, r, M + 1, R, 2 * id + 2));
}
}
};
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";
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 + now - 2, -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 |
Runtime error |
1 ms |
460 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
10 ms |
4284 KB |
Execution killed with signal 11 |
| 2 |
Runtime error |
11 ms |
4684 KB |
Execution killed with signal 11 |
| 3 |
Runtime error |
11 ms |
4684 KB |
Execution killed with signal 11 |
| 4 |
Correct |
1012 ms |
2520 KB |
Output is correct |
| 5 |
Runtime error |
28 ms |
10684 KB |
Execution killed with signal 11 |
| 6 |
Runtime error |
26 ms |
10988 KB |
Execution killed with signal 11 |
| 7 |
Runtime error |
28 ms |
10940 KB |
Execution killed with signal 11 |
| 8 |
Correct |
1169 ms |
5636 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
128 ms |
42436 KB |
Execution killed with signal 11 |
| 2 |
Runtime error |
117 ms |
42564 KB |
Execution killed with signal 11 |
| 3 |
Runtime error |
134 ms |
42868 KB |
Execution killed with signal 11 |
| 4 |
Runtime error |
1 ms |
460 KB |
Execution killed with signal 11 |
| 5 |
Runtime error |
373 ms |
105556 KB |
Execution killed with signal 11 |
| 6 |
Runtime error |
400 ms |
105592 KB |
Execution killed with signal 11 |
| 7 |
Runtime error |
292 ms |
105540 KB |
Execution killed with signal 11 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4 ms |
1612 KB |
Execution killed with signal 11 |
| 2 |
Runtime error |
6 ms |
2508 KB |
Execution killed with signal 11 |
| 3 |
Runtime error |
59 ms |
21424 KB |
Execution killed with signal 11 |
| 4 |
Runtime error |
54 ms |
21376 KB |
Execution killed with signal 11 |
| 5 |
Runtime error |
3 ms |
1228 KB |
Execution killed with signal 11 |
| 6 |
Runtime error |
82 ms |
27996 KB |
Execution killed with signal 11 |
| 7 |
Runtime error |
12 ms |
4684 KB |
Execution killed with signal 11 |
| 8 |
Runtime error |
129 ms |
42448 KB |
Execution killed with signal 11 |
| 9 |
Runtime error |
383 ms |
105572 KB |
Execution killed with signal 11 |
| 10 |
Runtime error |
3 ms |
1228 KB |
Execution killed with signal 11 |
| 11 |
Runtime error |
23 ms |
8780 KB |
Execution killed with signal 11 |
| 12 |
Runtime error |
278 ms |
84548 KB |
Execution killed with signal 11 |
| 13 |
Runtime error |
377 ms |
105672 KB |
Execution killed with signal 11 |
