Submission #395685

#TimeUsernameProblemLanguageResultExecution timeMemory
395685MrRobot_28Specijacija (COCI20_specijacija)C++17
20 / 110
4085 ms133256 KiB
#include<bits/stdc++.h> using namespace std; #define X first #define Y second #define sz(a) (int)a.size() #define ll long long const int N = 3e5; const int T = 20; int n, m, t; ll mod; ll a[N]; struct node{ node* left; node* right; int _sz; node(){}; }; node* mass[N]; int go_to(node* v, int l, int r, int d) { if(l == r) { return l; } if(v -> left -> _sz <= d) { return go_to(v -> right, (r + l) / 2 + 1, r, d - v -> left -> _sz); } return go_to(v -> left, l, (r + l) / 2, d); } void go_to1(node* pr, node *&v, int l, int r, int k) { v -> _sz = pr -> _sz; v -> _sz--; if(l == r) { return; } if(k <= (r + l) / 2) { v -> left = new node(); v -> right = pr -> right; go_to1(pr -> left, v -> left, l, (r + l) / 2, k); } else { v -> left = pr -> left; v -> right = new node(); go_to1(pr -> right, v -> right, (r + l) / 2 + 1, r, k); } } pair <int, int> funct(ll a) { int l = -1, r = n; while(r - l > 1) { ll midd = (r + l) / 2; if((midd + 2) * (midd + 1) / 2 <= a) { l = midd; } else { r = midd; } } return {l + 1, a - 1LL * (l + 2) * (l + 1) / 2}; } int go_to2(node* v, int l, int r, int x) { if(!v -> _sz) { return -1; } if(l > x) { return -1; } if(l == r) { return l; } if(r <= x) { if(v -> right -> _sz) { return go_to2(v -> right, (r + l) / 2 + 1, r, x); } return go_to2(v -> left, l, (r + l) / 2, x); } int t1 = go_to2(v -> left, l, (r + l) / 2, x); int t2 = go_to2(v -> right, (r + l) / 2 + 1, r, x); if(t2 != -1) { return t2; } return t1; } int coun(node* v, int l, int r, int x) { if(x < l) { return 0; } if(r <= x) { return v -> _sz; } return coun(v -> left, l, (r + l) / 2, x) + coun(v -> right, (r + l) / 2 + 1, r, x); } ll query(ll a, ll b) { pair <int, int> t = funct(a); pair <int, int> t1 = funct(b); t.Y = go_to(mass[t.X], 0, n, t.Y); t1.Y = go_to(mass[t1.X], 0, n, t1.Y); // cout << t.X << " " << t.Y << " " << t1.X << " " << t1.Y << "\n"; if(t.X > t1.X) { swap(t, t1); } t.Y = go_to2(mass[t.X], 0, n, t.Y); t1.Y = go_to2(mass[t.X], 0, n, t1.Y); for(int j = T - 1; j >= 0; j--) { if(t.Y == t1.Y) { break; } // cout << j << "\n"; if((1 << j) <= t.X && go_to2(mass[t.X - (1 << j)], 0, n, t.Y) != go_to2(mass[t.X - (1 << j)], 0, n, t1.Y)) { t.Y = go_to2(mass[t.X - (1 << j)], 0, n, t.Y); t1.Y = go_to2(mass[t.X - (1 << j)], 0, n, t1.Y); t.X -= (1 << j); } } // cout << t.X << " " << t.Y << " " << t1.Y << "\n"; if(t.Y != t1.Y) { t.X--; t.Y = go_to2(mass[t.X], 0, n, t.Y); } t.Y = coun(mass[t.X], 0, n, t.Y - 1); return t.Y + 1 + 1LL * (t.X) * (t.X + 1) / 2; } void build(node* &v, int l, int r) { v -> _sz = r - l + 1; if(l == r) { return; } v -> left = new node(); v -> right = new node(); build(v -> left, l, (r + l) / 2); build(v -> right, (r + l) / 2 + 1, r); } signed main() { // ifstream cin("input1.txt.4c"); ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> m >> t; // cout << n << "\n"; mod = 1LL * (n + 1) * (n + 2) / 2; for(int i = 0; i < n; i++) { cin >> a[i]; } mass[n] = new node(); build(mass[n], 0, n); //cout << "A\n"; for(int i = n - 1; i >= 0; i--) { a[i] -= 1LL * i * (i + 1) / 2; int u = go_to(mass[i + 1], 0, n, a[i]); mass[i] = new node(); go_to1(mass[i + 1], mass[i], 0, n, u); } ll z = 0; for(int i = 0; i < m; i++) { ll a, b; cin >> a >> b; a = (a - 1 + 1LL * t * z) % mod; b = (b - 1 + 1LL * t * z) % mod; cout << (z = query(a, b)) << "\n"; } 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...