제출 #91034

#제출 시각아이디문제언어결과실행 시간메모리
91034Flying_dragon_02케이크 (CEOI14_cake)C++14
100 / 100
541 ms11696 KiB
#include <bits/stdc++.h> using namespace std; #define fi first #define se second #define pb push_back #define mp make_pair typedef pair<int, int> ii; const int N = 250005; ii it[2][4 * N]; int n, q, a[N], x, cnt, p[15]; vector<ii> vec; ii compare(ii b, ii c, int type) { if(b.fi > c.fi) swap(b, c); if(type == 1) { if(b.fi == c.fi) return {b.fi, max(b.se, c.se)}; else return c; } else { if(b.fi == c.fi) return {b.fi, min(b.se, c.se)}; else return c; } } void build_tree(int type, int k, int l, int r) { if(l == r) { it[type][k] = {a[l], l}; return ; } int mid = (l + r) / 2; build_tree(type, k << 1, l, mid); build_tree(type, k << 1 | 1, mid + 1, r); if(type == 0) it[type][k] = compare(it[type][k << 1], it[type][k << 1 | 1], 1); else it[type][k] = compare(it[type][k << 1], it[type][k << 1 | 1], 2); } void update(int k, int l, int r, int pos, int val, int type) { if(r < pos || pos < l) return ; if(pos <= l && r <= pos) { it[type][k] = {val, l}; return ; } int mid = (l + r) >> 1; update(k << 1, l, mid, pos, val, type); update(k << 1 | 1, mid + 1, r, pos, val, type); if(pos < x) it[type][k] = compare(it[type][k << 1], it[type][k << 1 | 1], 1); else it[type][k] = compare(it[type][k << 1], it[type][k << 1 | 1], 2); } int get(int k, int l, int r, int L, int R, int type) { if(r < L || R < l || L > R) return 0; if(L <= l && r <= R) return it[type][k].fi; int mid = (l + r) >> 1; return max(get(k << 1, l, mid, L, R, type), get(k << 1 | 1, mid + 1, r, L, R, type)); } int climb(int k, int l, int r, int L, int R, int type, int val) { if(r < L || R < l || L > R) return -1; if(l == r) return it[type][k].se; int mid = (l + r) >> 1; if(type == 0) { if(it[type][k << 1 | 1].fi >= val) return climb(k << 1 | 1, mid + 1, r, L, R, type, val); return climb(k << 1, l, mid, L, R, type, val); } else { if(it[type][k << 1].fi >= val) return climb(k << 1, l, mid, L, R, type, val); return climb(k << 1 | 1, mid + 1, r, L, R, type, val); } } void getpos(int pos) { int val, po; if(pos < x) { val = get(1, 1, x - 1, pos, x - 1, 0); if(x + 1 <= n) { po = climb(1, x + 1, n, x + 1, n, 1, val); if(get(1, x + 1, n, x + 1, po, 1) > val) cout << abs(po - 1 - pos) << "\n"; else cout << abs(po - pos) << "\n"; return ; } else { cout << n - pos << "\n"; return ; } } else { val = get(1, x + 1, n, x + 1, pos, 1); if(x - 1 >= 1) { po = climb(1, 1, x - 1, 1, x - 1, 0, val); if(get(1, 1, x - 1, po, x - 1, 0) > val) cout << abs(pos - po - 1) << "\n"; else cout << abs(po - pos) << "\n"; return ; } else { cout << pos - 1 << "\n"; return ; } } //cout << val << " " << po << " " << pos << "\n"; } int main() { cin.tie(0), ios::sync_with_stdio(0); //freopen("test.inp", "r", stdin); cin >> n >> x; for(int i = 1; i <= n; i++) { cin >> a[i]; vec.pb({a[i], i}); } if(x - 1 >= 1) build_tree(0, 1, 1, x - 1); if(x + 1 <= n) build_tree(1, 1, x + 1, n); sort(vec.begin(), vec.end()); for(int i = n - 1; i >= max(0, n - 11); i--) p[n - i] = vec[i].se; cnt = n; cin >> q; while(q--) { char c; int pos, e; cin >> c; if(c == 'F') { cin >> pos; if(pos == x) cout << "0\n"; else getpos(pos); } else { cin >> pos >> e; int lim = min(n, 10); for(int i = lim; i >= e + 1; i--) { if(p[i] == pos) { lim = i; break; } } for(int i = lim; i >= e + 1; i--) p[i] = p[i - 1]; p[e] = pos; for(int i = e; i >= 1; i--) { if(p[i] == x) {++cnt; continue;} if(p[i] < x) update(1, 1, x - 1, p[i], ++cnt, 0); else update(1, x + 1, n, p[i], ++cnt, 1); } } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...