Submission #715123

#	Time	Username	Problem	Language	Result	Execution time	Memory
715123		TheConverseEngineer	Index (COCI21_index)	C++17	60 / 110	2574 ms	38264 KiB

index

#include <bits/stdc++.h>
using namespace std;

#define FOR(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define sqr(x) ((ll)(x))*(x)
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

struct MergeSortTree {
	vector<vi> s;
	void buildFullTree() {
		for (int i = sz(s)/2-1; i > 0; i--) { 
			s[i].resize(sz(s[i<<1]) + sz(s[i<<1|1]));
			merge(all(s[i<<1]), all(s[i<<1|1]), s[i].begin());
		}
	}
	int countGreater(int l, int r, int k) { 
		int output = 0;
		for (l += sz(s)/2, r += sz(s)/2; l < r; l /= 2, r /= 2) {
			if (l&1) output += s[l].end() - upper_bound(all(s[l]), k), l++;
			if (r&1) --r, output += s[r].end() - upper_bound(all(s[r]), k);
		}
		return output;
	}
};

int N, Q;
MergeSortTree tree;


int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> N >> Q; tree.s.resize(2*N, vi(0));
	FOR(i, 0, N) {
		int a; cin >> a; tree.s[N+i] = {a};
	}
	tree.buildFullTree();

	FOR(query, 0, Q) {
		int l, r; cin >> l >> r;
		int works = -1;
		for (int move = 262144; move > 0; move /= 2) {
			if (tree.countGreater(l-1, r, works+move-1) >= works+move) works += move;
		}
		cout << works << "\n";
	}
} 

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