Submission #446011

#	Time	Username	Problem	Language	Result	Execution time	Memory
446011		grt	Index (COCI21_index)	C++17	110 / 110	697 ms	19472 KiB

index

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>
#define ST first
#define ND second
#define PB push_back

using namespace std;
using namespace __gnu_pbds;
using ll = long long;
using pi = pair<int,int>;
using vi = vector<int>;

typedef tree<pi,null_type,less<pi>,rb_tree_tag,tree_order_statistics_node_update>ordered_set;

const int nax = 200 * 1000 + 10, INF = 1e9;
int n, q,mx;
int val[nax], l[nax], r[nax], mid[nax], ans[nax];
pi prz[nax];
vi contain[nax];

int T[nax];

void add(int a, int x) {
	while(a > 0) {
		T[a] += x;
		a -= (a & (-a));
	}
}

int ask(int a) {
	int w = 0;
	while(a < mx) {
		w += T[a];
		a += (a & (-a));
	}
	return w;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> q;
	for(int i = 1; i <= n; ++i) {
		cin >> val[i];
		mx = max(mx, val[i]);
	}
	for(int i = 1; i <= q; ++i) {
		cin >> prz[i].ST >> prz[i].ND;
		l[i] = 1; r[i] = prz[i].ND - prz[i].ST + 1;
		mid[i] = (l[i] + r[i]) / 2;
		contain[prz[i].ST - 1].PB(-i);
		contain[prz[i].ND].PB(i);
	}
	for(int rep = 0; ; ++rep) {
		for(int i = 0; i <= n; ++i) {
			if(i > 0) {
				add(val[i], 1);
			}
			for(auto x : contain[i]) {
				if(x < 0) {
					ans[-x] = -ask(mid[-x]);
				} else {
					ans[x] += ask(mid[x]);
				}
			}
		}
		for(int i = 1; i <= n; ++i) {
			add(val[i], -1);
		}
		bool any = false;
		for(int i = 1; i <= q; ++i) {
			if(l[i] <= r[i]) {
				if(ans[i] >= mid[i]) {
					l[i] = mid[i] + 1;
				} else {
					r[i] = mid[i] - 1;
				}
				mid[i] = (l[i] + r[i]) / 2;
				any = true;
			}
		}
		if(!any) break;
	}
	for(int i = 1; i <= q; ++i) {
		cout << l[i] - 1 << "\n";
	}
}

• Subtask 1: 20 / 20
• Subtask 2: 40 / 40
• Subtask 3: 50 / 50