제출 #101431

#제출 시각아이디문제언어결과실행 시간메모리
101431lyc케이크 (CEOI14_cake)C++14
0 / 100
1732 ms152684 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> ii; #define fi first #define sc second #define SZ(x) (int)(x).size() #define ALL(x) (x).begin(), (x).end() struct node { int s, e, m; vector<int> v; node *l, *r; node(int _s, int _e): s(_s), e(_e), m((_s+_e)/2) { if (s != e) { l = new node(s, m); r = new node(m+1, e); } } void def(int i, int x) { if (s == e) { v.clear(); v.push_back(x); } else if (i <= m) l->def(i, x); else r->def(i, x); } void build() { if (s == e) return; l->build(); r->build(); for (int i = 0, j = 0; i < SZ(l->v) || j < SZ(r->v);) { if (i < SZ(l->v) && (j == SZ(r->v) || l->v[i] <= r->v[j])) v.push_back(l->v[i++]); else v.push_back(r->v[j++]); } //cout << s << " " << e << " : "; //for (auto x : v) cout << x << " "; cout << endl; } void update(int i, int ov, int nv) { //cout << "UPDATE " << i << " " << nv << endl; //cout << '\t'; for (auto y : v) cout << y << " "; cout << endl; if (s != e) { if (i <= m) l->update(i, ov, nv); else r->update(i, ov, nv); } stack<int> s; while (v.back() != ov) { s.push(v.back()); v.pop_back(); assert(!v.empty()); } v.pop_back(); while (!s.empty() && s.top() < nv) { v.push_back(s.top()); s.pop(); } v.push_back(nv); while (!s.empty()) { v.push_back(s.top()); s.pop(); } } void increase(int x) { if (s != e) { if (l->v.back() >= x) l->increase(x); if (r->v.back() >= x) r->increase(x); } //cout << "INCREASING " << s << " " << e << endl; for (int i = SZ(v)-1; i >= 0 && v[i] >= x; --i) { ++v[i]; } //cout << '\t'; for (auto y : v) cout <<y << " " ; cout<< endl; } ll qmax(int x, int y) { //cout << "QMAX " << x << " " << y << " of " << s << " " << e << endl; if (s == x && e == y) { assert(!v.empty()); return v.back(); } else if (y <= m) return l->qmax(x, y); else if (x > m) return r->qmax(x, y); else return max(l->qmax(x, m), r->qmax(m+1, y)); } int qcntless(int x, int y, int z) { if (s == x && e == y) return lower_bound(ALL(v), z) - v.begin(); else if (y <= m) return l->qcntless(x, y, z); else if (x > m) return r->qcntless(x, y, z); else return l->qcntless(x, m, z) + r->qcntless(m+1, y, z); } void dbg() { } } *root; int main() { //freopen("in.txt", "r", stdin); ios::sync_with_stdio(false); cin.tie(0); int n, a; cin >> n >> a; int d[n+1]; root = new node(1, n); set<int> delival; for (int i = 1; i <= n; ++i) { cin >> d[i]; d[i] *= 500000; root->def(i, d[i]); delival.insert(d[i]); } root->build(); int q; cin >> q; for (int qi = 0; qi < q; ++qi) { char t; cin >> t; if (t == 'F') { int b; cin >> b; //cout << "HI" << endl; if (b == a) cout << 0 << '\n'; else if (b < a) { //cout << "CASE 1: " << endl; int maxi = root->qmax(b, a-1); //cout << maxi << endl; int cnt = root->qcntless(a+1, n, maxi); cout << cnt + (a-b) << '\n'; } else { int maxi = root->qmax(a+1, b); //cout << "MAXI " << maxi << endl; int cnt = root->qcntless(1, a-1, maxi); cout << cnt + (b-a) << '\n'; } } else { int i, e; cin >> i >> e; //cout << "OVAL " << d[i] << endl; //for (auto x : delival) cout << x << " "; cout << endl; ll ov = d[i]; delival.erase(d[i]); auto it = delival.end(); for (it = prev(it); e > 1; --e) { auto jt = prev(it); delival.insert(*it+1); delival.erase(it); it = jt; } //if (d[i] == *it) continue; d[i] = *it+1; delival.insert(d[i]); //cout << "NVAL " << d[i] << endl; //for (auto x : delival) cout << x << " "; cout << endl; root->increase(d[i]); root->update(i, ov, d[i]); } //cout << flush; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...