Submission #446007

#	Time	Username	Problem	Language	Result	Execution time	Memory
446007		grt	Index (COCI21_index)	C++17	60 / 110	2552 ms	29820 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;
int val[nax], l[nax], r[nax], mid[nax], ans[nax];
pi prz[nax];
vi contain[nax];
ordered_set S;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> q;
	for(int i = 1; i <= n; ++i) {
		cin >> 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 < 20; ++rep) {
		S.clear();
		int id = 1;
		for(int i = 0; i <= n; ++i) {
			if(i > 0) {
				S.insert({-val[i], id++});
			}
			for(auto x : contain[i]) {
				if(x < 0) {
					ans[-x] = -S.order_of_key({-mid[-x], INF});
				} else {
					ans[x] += S.order_of_key({-mid[x], INF});
				}
			}
		}
		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;
			}
		}
	}
	for(int i = 1; i <= q; ++i) {
		cout << l[i] - 1 << "\n";
	}
}

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