| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 996238 |
2024-06-10T09:07:25 Z |
dubabuba |
Index (COCI21_index) |
C++14 |
|
664 ms |
137080 KB |
#include <bits/stdc++.h>
using namespace std;
struct tree {
int sum;
tree *lc, *rc;
tree() : sum(0), lc(nullptr), rc(nullptr) {};
tree(int x) : sum(x), lc(nullptr), rc(nullptr) {};
tree(tree *L, tree *R) {
sum = 0;
lc = L, rc = R;
if(lc) sum += lc->sum;
if(rc) sum += rc->sum;
}
};
const int mxn = 2e5 + 10;
int sum(tree *sus) { return sus->sum; }
int a[mxn], n, q;
tree *root[mxn];
tree *build(int tl, int tr) {
if(tl == tr) return new tree(0);
int tm = (tl + tr) / 2;
return new tree(build(tl, tm), build(tm + 1, tr));
}
tree *upt(tree *sus, int tl, int tr, int pos, int add) {
if(tl == tr) return new tree(sum(sus) + add);
int tm = (tl + tr) / 2;
if(pos <= tm) {
tree *LC = upt(sus->lc, tl, tm, pos, add);
return new tree(LC, sus->rc);
} else {
tree *RC = upt(sus->rc, tm + 1, tr, pos, add);
return new tree(sus->lc, RC);
}
return nullptr;
}
int query(tree *L, tree *R, int tl, int tr, int adder) {
if(tl == tr) return tr;
int tm = (tl + tr) / 2;
int cnt = sum(R->rc) - sum(L->rc) + adder;
// cout << "(" << tl << ") " << tm + 1 << " to " << tr << " = " << cnt << endl;
if(tm + 1 > cnt) return query(L->lc, R->lc, tl, tm, cnt);
return query(L->rc, R->rc, tm + 1, tr, adder);
}
void print(tree *sus, int tl, int tr) {
// cout << tl << " -> " << tr << ": " << sum(sus) << endl;
if(tl == tr) return;
int tm = (tl + tr) / 2;
print(sus->lc, tl, tm);
print(sus->rc, tm + 1, tr);
}
int main() {
cin >> n >> q;
root[0] = build(1, n);
for(int i = 1; i <= n; i++) {
cin >> a[i];
root[i] = upt(root[i - 1], 1, n, a[i], 1);
// print(root[i], 1, n);
// cout << endl;
}
while(q--) {
int l, r;
cin >> l >> r;
// cout << "query: " << l << ' ' << r << endl;
cout << query(root[l - 1], root[r], 1, n, 0) << endl;
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2908 KB |
Output is correct |
| 2 |
Correct |
3 ms |
2908 KB |
Output is correct |
| 3 |
Correct |
4 ms |
2908 KB |
Output is correct |
| 4 |
Correct |
2 ms |
2756 KB |
Output is correct |
| 5 |
Correct |
2 ms |
2908 KB |
Output is correct |
| 6 |
Correct |
2 ms |
2756 KB |
Output is correct |
| 7 |
Correct |
5 ms |
2816 KB |
Output is correct |
| 8 |
Correct |
5 ms |
2908 KB |
Output is correct |
| 9 |
Correct |
3 ms |
2908 KB |
Output is correct |
| 10 |
Correct |
2 ms |
2908 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2908 KB |
Output is correct |
| 2 |
Correct |
3 ms |
2908 KB |
Output is correct |
| 3 |
Correct |
4 ms |
2908 KB |
Output is correct |
| 4 |
Correct |
2 ms |
2756 KB |
Output is correct |
| 5 |
Correct |
2 ms |
2908 KB |
Output is correct |
| 6 |
Correct |
2 ms |
2756 KB |
Output is correct |
| 7 |
Correct |
5 ms |
2816 KB |
Output is correct |
| 8 |
Correct |
5 ms |
2908 KB |
Output is correct |
| 9 |
Correct |
3 ms |
2908 KB |
Output is correct |
| 10 |
Correct |
2 ms |
2908 KB |
Output is correct |
| 11 |
Correct |
138 ms |
32880 KB |
Output is correct |
| 12 |
Correct |
128 ms |
32852 KB |
Output is correct |
| 13 |
Correct |
132 ms |
32852 KB |
Output is correct |
| 14 |
Correct |
169 ms |
32800 KB |
Output is correct |
| 15 |
Correct |
130 ms |
32852 KB |
Output is correct |
| 16 |
Correct |
126 ms |
32916 KB |
Output is correct |
| 17 |
Correct |
126 ms |
32908 KB |
Output is correct |
| 18 |
Correct |
131 ms |
32852 KB |
Output is correct |
| 19 |
Correct |
129 ms |
32904 KB |
Output is correct |
| 20 |
Correct |
128 ms |
32852 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2908 KB |
Output is correct |
| 2 |
Correct |
3 ms |
2908 KB |
Output is correct |
| 3 |
Correct |
4 ms |
2908 KB |
Output is correct |
| 4 |
Correct |
2 ms |
2756 KB |
Output is correct |
| 5 |
Correct |
2 ms |
2908 KB |
Output is correct |
| 6 |
Correct |
2 ms |
2756 KB |
Output is correct |
| 7 |
Correct |
5 ms |
2816 KB |
Output is correct |
| 8 |
Correct |
5 ms |
2908 KB |
Output is correct |
| 9 |
Correct |
3 ms |
2908 KB |
Output is correct |
| 10 |
Correct |
2 ms |
2908 KB |
Output is correct |
| 11 |
Correct |
138 ms |
32880 KB |
Output is correct |
| 12 |
Correct |
128 ms |
32852 KB |
Output is correct |
| 13 |
Correct |
132 ms |
32852 KB |
Output is correct |
| 14 |
Correct |
169 ms |
32800 KB |
Output is correct |
| 15 |
Correct |
130 ms |
32852 KB |
Output is correct |
| 16 |
Correct |
126 ms |
32916 KB |
Output is correct |
| 17 |
Correct |
126 ms |
32908 KB |
Output is correct |
| 18 |
Correct |
131 ms |
32852 KB |
Output is correct |
| 19 |
Correct |
129 ms |
32904 KB |
Output is correct |
| 20 |
Correct |
128 ms |
32852 KB |
Output is correct |
| 21 |
Correct |
645 ms |
137024 KB |
Output is correct |
| 22 |
Correct |
655 ms |
137048 KB |
Output is correct |
| 23 |
Correct |
624 ms |
137044 KB |
Output is correct |
| 24 |
Correct |
664 ms |
137020 KB |
Output is correct |
| 25 |
Correct |
631 ms |
137044 KB |
Output is correct |
| 26 |
Correct |
649 ms |
137044 KB |
Output is correct |
| 27 |
Correct |
650 ms |
137080 KB |
Output is correct |
| 28 |
Correct |
653 ms |
137044 KB |
Output is correct |
| 29 |
Correct |
625 ms |
137044 KB |
Output is correct |
| 30 |
Correct |
616 ms |
137040 KB |
Output is correct |
