Submission #555740

#TimeUsernameProblemLanguageResultExecution timeMemory
555740alextodoranCake (CEOI14_cake)C++17
100 / 100
1014 ms26380 KiB
/** ____ ____ ____ ____ ____ ||a |||t |||o |||d |||o || ||__|||__|||__|||__|||__|| |/__\|/__\|/__\|/__\|/__\| **/ #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N_MAX = 250000; const int Q_MAX = 500000; const int D_MAX = N_MAX + Q_MAX * 10; int N, start; int d[N_MAX + 2]; int Q; set <int> newmax; set <int> :: iterator getMax (int i) { return (i < start ? newmax.lower_bound(i) : prev(newmax.upper_bound(i))); } int D; map <int, int> where; int Fen[D_MAX + 2]; void update (int pos, int val) { for (int i = pos; i <= D_MAX; i += i & -i) { Fen[i] += val; } } int query (int pos) { int val = 0; for (int i = pos; i >= 1; i -= i & -i){ val += Fen[i]; } return val; } void makeMax (int i) { D++; if (i < start) { set <int> :: iterator it = prev(newmax.upper_bound(i)); if (*it < i) { set <int> :: iterator neit = next(it); update(d[*neit], -(i - *it)); } while (*it > 0) { set <int> :: iterator prit = prev(it); update(d[*it], -(*it - *prit)); newmax.erase(it); it = prit; } newmax.insert(i); update(D, +(i - 0)); } else if (i > start) { set <int> :: iterator it = newmax.lower_bound(i); if (i < *it) { set <int> :: iterator prit = prev(it); update(d[*prit], -(*it - i)); } while (*it < (N + 1)) { set <int> :: iterator neit = next(it); update(d[*it], -(*neit - *it)); newmax.erase(it); it = neit; } newmax.insert(i); update(D, +((N + 1) - i)); } where.erase(d[i]); d[i] = D; where[D] = i; } int main () { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> N >> start; for (int i = 1; i <= N; i++) { cin >> d[i]; } D = N; for (int i = start - 1, curr = 0; i >= 1; i--) { if (d[i] > curr) { newmax.insert(i); curr = d[i]; } } newmax.insert(0); for (int i = start + 1, curr = 0; i <= N; i++) { if (d[i] > curr) { newmax.insert(i); curr = d[i]; } } newmax.insert(N + 1); for (int i = 1; i <= N; i++) { if (i != start) { update(d[*getMax(i)], +1); } where[d[i]] = i; } cin >> Q; while (Q--) { char type; cin >> type; if (type == 'F') { int i; cin >> i; if (i == start) { cout << 0 << "\n"; } else { set <int> :: iterator it = getMax(i); cout << 1 + query(d[*it] - 1) + abs(*it - i) << "\n"; } } else { int i, e; cin >> i >> e; e--; makeMax(i); if (e > 0) { vector <int> aux; map <int, int> :: iterator it = prev(where.end()), prit = prev(it); for (int k = 1; k <= e; k++) { it = prit; if (k < e) { prit = prev(it); } aux.push_back(it->second); } reverse(aux.begin(), aux.end()); for (int j : aux) { makeMax(j); } } } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...