Submission #1221788

#TimeUsernameProblemLanguageResultExecution timeMemory
1221788sula2Index (COCI21_index)C++20
0 / 110
1 ms576 KiB
#include <bits/stdc++.h> #define all(a) (a).begin(), (a).end() using namespace std; struct node { long long sum = 0; node *l = nullptr, *r = nullptr; int L, R; node(int L, int R) : L(L), R(R) {} node* update(int ind, int x) { if (R - L == 1) { node* new_node = new node(L, R); new_node->sum = sum + x; return new_node; } node* new_node = new node(L, R); int mid = (L+R)/2; if (l == nullptr) l = new node(L, mid); if (r == nullptr) r = new node(mid, R); new_node->l = l; new_node->r = r; if (ind < mid) { new_node->l = l->update(ind, x); } else { new_node->r = r->update(ind, x); } new_node->sum = new_node->l->sum + new_node->r->sum; return new_node; } long long query(int ql, int qr) { if (ql <= L && R <= qr) { return sum; } if (qr <= L || R <= ql) return 0; return (l == nullptr ? 0 : l->query(ql, qr)) + (r == nullptr ? 0 : r->query(ql, qr)); } void dfs() { cout << L << " " << R << " " << sum << '\n'; if (l != nullptr) l->dfs(); if (r != nullptr) r->dfs(); } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); const int A = 16; int n,q; cin >> n >> q; vector<node*> roots { new node(0, A) }; for (int i = 0; i < n; i++) { int ai; cin >> ai; roots.push_back(roots.back()); roots.back() = roots.back()->update(ai, 1); } while (q--) { int l,r; cin >> l >> r; l--; auto root_l = roots[l]; auto root_r = roots[r]; int sum = 0; while (root_l->l != nullptr) { assert(root_l ->L == root_r ->L); assert(root_l ->R == root_r ->R); int x = sum + root_r -> r -> sum - root_l -> r -> sum; int mid = (root_r -> L + root_r -> R)/2; if (mid <= x) { root_r = root_r->r; root_l = root_l->r; } else { root_r = root_r->l; root_l = root_l->l; sum += x; } } cout << root_r -> L << "\n"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...