Submission #579333

#	Time	Username	Problem	Language	Result	Execution time	Memory
579333		penguinhacker	Index (COCI21_index)	C++14	110 / 110	594 ms	137216 KiB

index

#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 / 20
• Subtask 2: 40 / 40
• Subtask 3: 50 / 50