Submission #377439

#TimeUsernameProblemLanguageResultExecution timeMemory
377439VEGAnnSpecijacija (COCI20_specijacija)C++14
20 / 110
4077 ms139768 KiB
#include <bits/stdc++.h> #define i2 array<int,2> using namespace std; typedef long long ll; const int oo = 2e9; const int N = 200100; const int M = 10; const int PW = 10; const int HPW = 233; const int md = int(1e9) + 7; ll n, a[N]; int q, t; struct seg_tree{ seg_tree *l, *r; int sm; seg_tree(): l(0), r(0), sm(0) {} seg_tree(seg_tree *v): l(v -> l), r(v -> r), sm(v -> sm) {} void build(int tl, int tr){ sm = tr - tl + 1; if (tl == tr) return; int md = (tl + tr) >> 1; l = new seg_tree(); r = new seg_tree(); l -> build(tl, md); r -> build(md + 1, tr); } void delt(int tl, int tr, int ind){ sm--; if (tl == tr) return; int md = (tl + tr) >> 1; if (l -> sm < ind){ r = new seg_tree(r); r -> delt(md + 1, tr, ind - (l -> sm)); } else { l = new seg_tree(l); l -> delt(tl, md, ind); } } ll get(int tl, int tr, int ql, int qr){ if (ql > qr) return 0; if (tl == ql && tr == qr) return sm; int md = (tl + tr) >> 1; return (l -> get(tl, md, ql, min(qr, md))) + (r -> get(md + 1, tr, max(md + 1, ql), qr)); } int get_by_cnt(int tl, int tr, int ind){ if (tl == tr) return tl; int md = (tl + tr) >> 1; if (l -> sm < ind){ return r -> get_by_cnt(md + 1, tr, ind - (l -> sm)); } else { return l -> get_by_cnt(tl, md, ind); } } }; seg_tree *root[N]; /// 0 -- layer, 1 -- index i2 get_id(ll x){ ll l = 1, r = n + 1; while (l < r){ ll md = (l + r + 1) >> 1; if (x > md * (md - 1) / 2) l = md; else r = md - 1; } return {l, x - (l * (l - 1) / 2)}; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); #ifdef _LOCAL freopen("in.txt","r",stdin); #endif // _LOCAL cin >> n >> q >> t; for (int i = 1; i <= n; i++) cin >> a[i]; root[n + 1] = new seg_tree(); root[n + 1] -> build(1, n + 1); for (int i = n; i > 0; i--){ root[i] = new seg_tree(root[i + 1]); ll id = a[i] - (ll(i) * (ll(i) - 1ll) / 2ll); root[i] -> delt(1, n + 1, id + 1); } ll last = 0; ll BIG = (ll(n) + 1) * (ll(n) + 2) / 2ll; for (; q; q--){ ll x, y; cin >> x >> y; x = ((x - 1) + t * last) % BIG + 1; y = ((y - 1) + t * last) % BIG + 1; i2 nw_x = get_id(x); i2 nw_y = get_id(y); /// do binary search int lf = 1, rt = min(nw_x[0], nw_y[0]); int ps1 = root[nw_x[0]] -> get_by_cnt(1, n + 1, nw_x[1]); int ps2 = root[nw_y[0]] -> get_by_cnt(1, n + 1, nw_y[1]); while (lf < rt){ int md = (lf + rt + 1) >> 1; if (root[md] -> get(1, n + 1, 1, ps1) == root[md] -> get(1, n + 1, 1, ps2)) lf = md; else rt = md - 1; } /// lf -- new layer /// get new id ll res = ll(lf) * (ll(lf) - 1ll) / 2ll; res += root[lf] -> get(1, n + 1, 1, ps1); last = res; // cout << res << '\n'; cout << res << endl; } return 0; }

Compilation message (stderr)

Main.cpp: In function 'std::array<int, 2> get_id(ll)':
Main.cpp:93:13: warning: narrowing conversion of 'l' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
   93 |     return {l, x - (l * (l - 1) / 2)};
      |             ^
Main.cpp:93:18: warning: narrowing conversion of '(x - ((l * (l - 1)) / 2))' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
   93 |     return {l, x - (l * (l - 1) / 2)};
      |                ~~^~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...