Submission #483876

#	Time	Username	Problem	Language	Result	Execution time	Memory
483876		Sohsoh84	Index (COCI21_index)	C++17	110 / 110	1944 ms	139544 KiB

index

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

#define all(x)                      (x).begin(),(x).end()
#define X                           first
#define Y                           second
#define sep                         ' '
#define endl                        '\n'
#define debug(x)                    cerr << #x << ": " <<  x << endl;

ll poww(ll a, ll b, ll md) {
	return (!b ? 1 : (b & 1 ? a * poww(a * a % md, b / 2, md) % md : poww(a * a % md, b / 2, md) % md));
}

const ll MAXN = 1e6 + 10;
const ll INF = 8e18;
const ll MOD = 1e9 + 7; // 998244353; // 1e9 + 9;

struct Node {
	Node *L, *R;
	int val = 0;
	Node(int t_val): L(nullptr), R(nullptr), val(t_val) {};
	Node(Node* L, Node* R): L(L), R(R), val(0) {
		if (L) val += L -> val;
		if (R) val += R -> val;
	}
};

Node* Build(int L, int R) {
	if (L == R) return new Node(0);
	int mid = (L + R) >> 1;
	return new Node(Build(L, mid), Build(mid + 1, R));
}

int Query(Node* v, int L, int R, int ql, int qr) {
	if (ql > qr) return 0;
	if (L == ql && R == qr) return v -> val;
	int mid = (L + R) >> 1;
	return Query(v -> L, L, mid, ql, min(mid, qr)) + Query(v -> R, mid + 1, R, max(ql, mid + 1), qr);
}

Node* Update(Node* v, int L, int R, int ind, int val) {
	if (L == R) return new Node(val);
	int mid = (L + R) >> 1;
	if (ind <= mid) return new Node(Update(v -> L, L, mid, ind, val), v -> R);
	else return new Node(v -> L, Update(v -> R, mid + 1, R, ind, val));
}

Node* PST[MAXN];
int n, q;
vector<pll> v;

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n >> q;
	for (int i = 1; i <= n; i++) {
		int x;
		cin >> x;
		v.push_back({x, i});
	}

	sort(all(v));
	PST[n] = Build(1, n);
	for (int i = n - 1; i >= 0; i--) PST[i] = Update(PST[i + 1], 1, n, v[i].Y, 1);

	while (q--) {
		int tL, tR;
		cin >> tL >> tR;
		
		int L = 1, R = n;
		while (L < R) {
			int mid = (L + R + 1) >> 1;
			int ind = lower_bound(all(v), make_pair(1ll * mid, 0ll)) - v.begin();
			int cnt = Query(PST[ind], 1, n, tL, tR);
			if (cnt >= mid) L = mid;
			else R = mid - 1;
		}

		cout << L << endl;
	}
	return 0;
}

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