oj.uz

Submission #579333

# Submission time Handle Problem Language Result Execution time Memory
579333 2022-06-18T23:58:23 Z penguinhacker Index (COCI21_index) C++14
110 / 110
 594 ms 137216 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

const int mxN=2e5;
int n, q, a[mxN];

struct Node {
	int sum=0;
	Node *left=nullptr, *right=nullptr;
	Node(int l, int r) {
		if (l!=r) {
			int mid=(l+r)/2;
			left=new Node(l, mid);
			right=new Node(mid+1, r);
		}
	}
	Node(int x) : sum(x) {}
	Node(Node* l, Node* r) {
		assert(l&&r);
		sum=l->sum+r->sum;
		left=l;
		right=r;
	}
	Node* upd(int i, int l=1, int r=mxN) {
		if (l>i||r<i)
			return this;
		if (l==r)
			return new Node(sum+1);
		int mid=(l+r)/2;
		return new Node(left->upd(i, l, mid), right->upd(i, mid+1, r));
	}
};

vector<Node*> roots;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> q;
	roots.push_back(new Node(1, mxN));
	for (int i=0; i<n; ++i) {
		cin >> a[i];
		roots.push_back(roots.back()->upd(a[i]));
	}
	while(q--) {
		int ql, qr;
		cin >> ql >> qr, --ql, --qr;
		Node *u=roots[ql], *v=roots[qr+1];
		int l=1, r=mxN, extra=0;
		while(l<r) {
			int mid=(l+r)/2;
			int cnt=(v->right->sum)-(u->right->sum);
			if (cnt+extra>=mid+1) {
				l=mid+1;
				u=u->right, v=v->right;
			} else {
				r=mid, extra+=cnt;
				u=u->left, v=v->left;
			}
		}
		cout << l << "\n";
	}
	return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 13396 KB Output is correct
2 Correct 20 ms 13436 KB Output is correct
3 Correct 15 ms 13396 KB Output is correct
4 Correct 14 ms 13352 KB Output is correct
5 Correct 14 ms 13396 KB Output is correct
6 Correct 14 ms 13396 KB Output is correct
7 Correct 14 ms 13372 KB Output is correct
8 Correct 14 ms 13416 KB Output is correct
9 Correct 15 ms 13392 KB Output is correct
10 Correct 14 ms 13396 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 13396 KB Output is correct
2 Correct 20 ms 13436 KB Output is correct
3 Correct 15 ms 13396 KB Output is correct
4 Correct 14 ms 13352 KB Output is correct
5 Correct 14 ms 13396 KB Output is correct
6 Correct 14 ms 13396 KB Output is correct
7 Correct 14 ms 13372 KB Output is correct
8 Correct 14 ms 13416 KB Output is correct
9 Correct 15 ms 13392 KB Output is correct
10 Correct 14 ms 13396 KB Output is correct
11 Correct 136 ms 43812 KB Output is correct
12 Correct 117 ms 43744 KB Output is correct
13 Correct 105 ms 43812 KB Output is correct
14 Correct 104 ms 43780 KB Output is correct
15 Correct 119 ms 43812 KB Output is correct
16 Correct 99 ms 43820 KB Output is correct
17 Correct 111 ms 43808 KB Output is correct
18 Correct 99 ms 43724 KB Output is correct
19 Correct 113 ms 43696 KB Output is correct
20 Correct 103 ms 43776 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 13396 KB Output is correct
2 Correct 20 ms 13436 KB Output is correct
3 Correct 15 ms 13396 KB Output is correct
4 Correct 14 ms 13352 KB Output is correct
5 Correct 14 ms 13396 KB Output is correct
6 Correct 14 ms 13396 KB Output is correct
7 Correct 14 ms 13372 KB Output is correct
8 Correct 14 ms 13416 KB Output is correct
9 Correct 15 ms 13392 KB Output is correct
10 Correct 14 ms 13396 KB Output is correct
11 Correct 136 ms 43812 KB Output is correct
12 Correct 117 ms 43744 KB Output is correct
13 Correct 105 ms 43812 KB Output is correct
14 Correct 104 ms 43780 KB Output is correct
15 Correct 119 ms 43812 KB Output is correct
16 Correct 99 ms 43820 KB Output is correct
17 Correct 111 ms 43808 KB Output is correct
18 Correct 99 ms 43724 KB Output is correct
19 Correct 113 ms 43696 KB Output is correct
20 Correct 103 ms 43776 KB Output is correct
21 Correct 498 ms 137096 KB Output is correct
22 Correct 488 ms 137076 KB Output is correct
23 Correct 594 ms 137108 KB Output is correct
24 Correct 499 ms 137080 KB Output is correct
25 Correct 578 ms 137100 KB Output is correct
26 Correct 554 ms 137216 KB Output is correct
27 Correct 525 ms 137064 KB Output is correct
28 Correct 521 ms 137068 KB Output is correct
29 Correct 542 ms 137188 KB Output is correct
30 Correct 554 ms 137140 KB Output is correct