Submission #1038404

#TimeUsernameProblemLanguageResultExecution timeMemory
1038404underwaterkillerwhaleAbracadabra (CEOI22_abracadabra)C++17
100 / 100
490 ms67136 KiB
#include <bits/stdc++.h> #define se second #define fs first #define mp make_pair #define pb push_back #define ll long long #define ii pair<ll,ll> #define ld long double #define SZ(v) (int)v.size() #define ALL(v) v.begin(), v.end() #define bit(msk, i) ((msk >> i) & 1) #define iter(id, v) for(auto id : v) #define rep(i,m,n) for(int i=(m); i<=(n); i++) #define reb(i,m,n) for(int i=(m); i>=(n); i--) using namespace std; mt19937_64 rd(chrono :: steady_clock :: now().time_since_epoch().count()); ll Rand(ll l, ll r) { return uniform_int_distribution<ll> (l, r)(rd); } const int N = 2e5 + 7; const int Mod = 1e9 + 7; const int szBL = 240; const int INF = 1e9 + 7; const int BASE = 137; struct fenwick_Tree { int m; int fen[N]; void init (int n) { m = n; } void update (int pos, int val) { for (;pos <= m; pos += pos & -pos) fen[pos] += val; } int get (int pos) { int res = 0; for (;pos > 0; pos -= pos & -pos) res += fen[pos]; return res; } }fen; int n, Q; int a[N]; pair<int,int> itv[N]; vector<pair<int,int>> qr[N]; int spt[N][25]; int Ans[(int)1e6 + 7]; void solution () { cin >> n >> Q; rep (i, 1, n) cin >> a[i]; fen.init(n); rep (i, 1, n) spt[i][0] = a[i]; for (int j = 1; (1 << j) <= n; ++j) for (int i = 1; i + (1 << j) - 1 <= n; i++) spt[i][j] = max(spt[i][j - 1], spt[i + (1 << j - 1)][j - 1]); auto get = [] (int L, int R) { assert(L <= R); int K = 31 - __builtin_clz(R - L + 1); return max(spt[L][K], spt[R - (1 << K) + 1][K]); }; auto get_bound = [&] (int pos, int R) { int lf = pos, rt = R; while (lf < rt) { int mid = lf + rt + 1 >> 1; if (get(pos, mid) == a[pos]) lf = mid; else rt = mid - 1; } return lf; }; rep (i, 1, n) { int bound = get_bound(i, n); itv[a[i]] = {i, bound}; fen.update (a[i], bound - i + 1); i = bound; } rep (i, 1, Q) { int T, p; cin >> T >> p; T = min(T, n); qr[T].push_back({p, i}); } auto get_val = [] (int p) { int lf = 1, rt = n; while (lf < rt) { int mid = lf + rt >> 1; if (fen.get(mid) >= p) rt = mid; else lf = mid + 1; } return lf; }; auto simulation = [&] (int p) { int val = get_val(p); int L = itv[val].fs, R = itv[val].se; // cout << val <<"hihi\n"; if (p - fen.get(val - 1) == 1) return; int np = L + p - fen.get(val - 1) - 1; // cout << np <<" aa\n"; fen.update(val, - (R - np + 1)); itv[val] = {L, np - 1}; rep (i, np, R) { int bound = get_bound(i, R); itv[a[i]] = {i, bound}; fen.update(a[i], bound - i + 1); i = bound; } }; rep (i, 0, n) { // cout << i <<":\n"; // rep (i, 1, n) cout << a[i] <<" "<<itv[a[i]].fs<<" "<<itv[a[i]].se <<"\n"; iter (&id, qr[i]) { int val = get_val(id.fs); // cout << id.se <<" "<<id.fs<<" "<<val<<" "<<itv[val].fs<<" "<<itv[val].se<<" "<<fen.get(4)<<"qr\n"; Ans[id.se] = a[itv[val].fs + id.fs - fen.get(val - 1) - 1]; } simulation(n / 2 + 1); } rep (i, 1, Q) { cout << Ans[i] <<"\n"; } } #define file(name) freopen(name".inp", "r", stdin); \ freopen(name".out", "w", stdout); /* */ int main () { // file("c"); ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); ll num_Test = 1; // cin >> num_Test; while(num_Test--) solution(); } /* no bug challenge +2 6 25 18 40 37 29 95 41 53 39 69 61 90 14 18 22 28 18 30 32 32 63 58 71 78 */

Compilation message (stderr)

Main.cpp: In function 'void solution()':
Main.cpp:59:60: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   59 |             spt[i][j] = max(spt[i][j - 1], spt[i + (1 << j - 1)][j - 1]);
      |                                                          ~~^~~
Main.cpp: In lambda function:
Main.cpp:70:31: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   70 |             int mid = lf + rt + 1 >> 1;
      |                       ~~~~~~~~^~~
Main.cpp: In lambda function:
Main.cpp:94:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   94 |             int mid = lf + rt >> 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...