Submission #933131

#TimeUsernameProblemLanguageResultExecution timeMemory
933131CookieCake (CEOI14_cake)C++14
0 / 100
100 ms38240 KiB
#include<bits/stdc++.h> #include<fstream> using namespace std; #define sz(a) (int)a.size() #define ALL(v) v.begin(), v.end() #define ALLR(v) v.rbegin(), v.rend() #define ll long long #define pb push_back #define forr(i, a, b) for(int i = a; i < b; i++) #define dorr(i, a, b) for(int i = a; i >= b; i--) #define ld long double #define vt vector #include<fstream> #define fi first #define se second #define pll pair<ll, ll> #define pii pair<int, int> #define mpp make_pair const ld PI = 3.14159265359, prec = 1e-9;; using u128 = __uint128_t; //const int x[4] = {1, 0, -1, 0}; //const int y[4] = {0, -1, 0, 1}; const ll mod =1e9 + 7; const int mxn = 250000 + 5, mxq = 1e5 + 5, sq = 300, mxv = 1e4 + 5; //const int base = (1 <<18); const ll inf = 3e9 + 5, neg = -69420, inf2 = 1e14; mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); // have fun! // <3; struct ST{ int st[4 * mxn + 1], lz[4 * mxn + 1]; void init(){ for(int i = 1; i <= 4 * mxn; i++)lz[i] = -1; } void push(int nd){ int &v = lz[nd]; if(v == -1)return; lz[nd << 1] = lz[nd << 1 | 1] = st[nd << 1] = st[nd << 1 | 1] = v; v = -1; } void upd(int nd, int l, int r, int ql, int qr, int v){ if(ql > r || qr < l)return; if(ql <= l && qr >= r){ lz[nd] = st[nd] = v; return; } int mid = (l + r) >> 1; push(nd); upd(nd << 1, l, mid, ql, qr, v); upd(nd << 1 | 1, mid + 1, r, ql, qr, v); } int get(int nd, int l, int r, int id){ if(l == r)return(st[nd]); int mid = (l + r) >> 1; push(nd); if(id <= mid)return(get(nd << 1, l, mid, id)); else return(get(nd << 1 | 1, mid + 1, r, id)); } }; ST stl, str; int n, a, q; int mxid[15], d[mxn + 1], tol[mxn + 1], tor[mxn + 1]; void solve(){ cin >> n >> a; for(int i = 1; i <= n; i++){ cin >> d[i]; if(n + 1 - d[i] <= 10){ mxid[n + 1 - d[i]] = i; } } int lp = a, rp = a; tol[a] = tor[a] = a; while(lp != 1 || rp != n){ if(lp == 1){ rp++; tol[rp] = lp; }else if(rp == n){ lp--; tor[lp] = rp; }else if(d[lp - 1] < d[rp + 1]){ lp--; tor[lp] = rp; }else{ rp++; tol[rp] = lp; } } stl.init(); str.init(); cin >> q; mxid[11] = n + 1; for(int i = 1; i <= n; i++){ str.upd(1, 1, n, i, i, tor[i]); stl.upd(1, 1, n, i, i, tol[i]); } while(q--){ char c; cin >> c; if(c == 'F'){ int id; cin >> id; if(id <= a){ int idr = str.get(1, 1, n, id); cout << idr - id << "\n"; }else{ int idl = stl.get(1, 1, n, id); cout << id - idl << "\n"; } }else{ int id, e; cin >> id >> e; int val = -1; for(int i = 1; i <= 10; i++){ if(mxid[i] == id){ val = i; break; } } if(val == -1){ for(int j = 10; j >= e + 1; j++){ mxid[j] = mxid[j - 1]; } mxid[e] = id; }else{ for(int j = val; j >= e + 1; j--)mxid[j] = mxid[j - 1]; mxid[e] = id; } if(id == a)continue; bool sign = (id > a); int atl, atr, atv = e; if(sign)atl = stl.get(1, 1, n, id - 1) - 1, atr = id; else atr = str.get(1, 1, n, id + 1) + 1, atl = id; //for(int i = 1; i <= 10; i++)cout << mxid[i] << " "; //cout << "\n"; while(1){ if(sign == 0){ // -> int idmn = 11, mnv = n + 1; for(int j = atv - 1; j >= 1; j--){ if(mxid[j] >= atr && mxid[j] < mnv){ idmn = j; mnv = mxid[j]; } } stl.upd(1, 1, n, atr, mnv - 1, atl + 1); atr = mnv; atv = idmn; if(atr == n + 1){ str.upd(1, 1, n, 1, atl, n); break; } }else{ //<- int idmx = 11, mxv = 0; for(int j = atv - 1; j >= 1; j--){ if(mxid[j] <= atl && mxid[j] > mxv){ idmx = j; mxv = mxid[j]; } } str.upd(1, 1, n, mxv + 1, atl, atr - 1); atl = mxv; atv = idmx; if(atl == 0){ stl.upd(1, 1, n, atr, n, 1); break; } } sign = !sign; } } } } signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); //freopen("SODOCLA.INP", "r", stdin); //freopen("SODOCLA.INP", "w", stdout); int tt; tt = 1; while(tt--){ solve(); } return(0); } /* 10 5 2 3 4 5 6 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...