Submission #377898

#TimeUsernameProblemLanguageResultExecution timeMemory
377898VimmerSpecijacija (COCI20_specijacija)C++14
20 / 110
4083 ms135308 KiB
#include <bits/stdc++.h> //#include <ext/pb_ds/assoc_container.hpp> //#include <ext/pb_ds/tree_policy.hpp> #pragma GCC optimize("unroll-loops") #pragma GCC optimize("-O3") #pragma GCC optimize("Ofast") #define N 200051 #define NN 1005000 #define PB push_back #define M ll(1e9 + 7) #define all(x) x.begin(), x.end() #define sz(x) int(x.size()) #define pri(x) cout << x << endl #define endl '\n' #define _ << " " << #define F first #define S second using namespace std; //using namespace __gnu_pbds; typedef long long ll; //typedef tree <ll, null_type, less_equal <ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; typedef long double ld; typedef unsigned long long ull; typedef short int si; struct node { int sum = 0; node *l, *r; node(): sum(1), l(nullptr), r(nullptr) {} node(int sm): sum(sm), l(nullptr), r(nullptr) {} node(node *lt, node *rt): l(lt), r(rt), sum(lt->sum + rt->sum) {} }; vector <node*> vr; node* bld(int tl, int tr) { if (tl == tr) return new node(); else { int md = (tl + tr) >> 1; return new node(bld(tl, md), bld(md + 1, tr)); } } node* upd(node *v, int tl, int tr, int ps) { if (tl == tr) { return new node(0); } int md = (tl + tr) >> 1; if (v ->l->sum >= ps) { return new node(upd(v->l, tl, md, ps), v->r); } else { return new node(v->l, upd(v->r, md + 1, tr, ps - v->l->sum)); } } int get(node *v, int tl, int tr, int l, int r) { if (tr < l || r < tl || l > r || tl > tr) return 0; if (l <= tl && tr <= r) return v->sum; int md = (tl + tr) >> 1; return get(v->l, tl, md, l, r) + get(v->r, md + 1, tr, l, r); } int opr(node *v, int tl, int tr, int ps) { if (tl == tr) return tl; int md = (tl + tr) >> 1; if (v->l->sum >= ps) return opr(v->l, tl, md, ps); return opr(v->r, md + 1, tr, ps - v->l->sum); } int n, q, t; ll a[N]; ll lft(int i) {return 1ll * i * (i - 1) / 2;} vector <ll> vt; ll ans(ll x, ll y) { if (x == y) return x; int l = upper_bound(all(vt), x) - 1 - vt.begin(); int r = upper_bound(all(vt), y) - 1 - vt.begin(); l++; r++; ll xr = x, yr = y; x -= lft(l); y -= lft(r); x = opr(vr[n + 1 - l], 1, n + 1, x); y = opr(vr[n + 1 - r], 1, n + 1, y); if (x > y) swap(x, y); int lt = 1, rt = min(l, r); while (lt < rt) { int md = (lt + rt + 1) >> 1; int sm = get(vr[n - md + 1], 1, n + 1, x, y - 1); if (sm == 0) lt = md; else rt = md - 1; } if (lt == l) return xr; if (lt == r) return yr; return a[lt]; } int main() { ios_base::sync_with_stdio(0); istream::sync_with_stdio(0); cin.tie(0); cout.tie(0); // freopen("1.in", "r", stdin); cin >> n >> q >> t; ll m = (1ll * (n + 1) * (n + 2)) / 2; vr.PB(bld(1, n + 1)); for (int i = 1; i <= n; i++) { cin >> a[i]; vt.PB(lft(i) + 1); } for (int i = n; i >= 1; i--) { int l = a[i] - lft(i); vr.PB(upd(vr.back(), 1, n + 1, l)); } vt.PB(lft(n + 1) + 1); ll lst = 0; for (; q > 0; q--) { ll x, y; cin >> x >> y; x = (x - 1 + t * lst) % m + 1; y = (y - 1 + t * lst) % m + 1; lst = ans(x, y); pri(lst); } }

Compilation message (stderr)

Main.cpp: In constructor 'node::node(node*, node*)':
Main.cpp:35:15: warning: 'node::r' will be initialized after [-Wreorder]
   35 |     node *l, *r;
      |               ^
Main.cpp:33:9: warning:   'int node::sum' [-Wreorder]
   33 |     int sum = 0;
      |         ^~~
Main.cpp:40:5: warning:   when initialized here [-Wreorder]
   40 |     node(node *lt, node *rt): l(lt), r(rt), sum(lt->sum + rt->sum) {}
      |     ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...