제출 #1190873

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1190873		qrn	Index (COCI21_index)	C++20	0 / 110	2 ms	3392 KiB

index

#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
using namespace std;
// using namespace __gnu_pbds;

#define pb push_back
#define ins insert
#define fi first
#define se second
#define endl "\n"
#define ALL(x) x.begin(), x.end()
#define intt long long

const intt mod = 1e9 + 7;
const intt base = 9973;
const intt inf = 1e18;
const intt mxN = 2e5 + 5;
const intt L = 21;

struct query {
	intt l, r, i;
};

intt bsz = 500;
bool cmp(query &a, query &b) {
	if(a.l / bsz == b.l / bsz) {
		return a.r < b.r;
	}
	return a.l / bsz < b.l / bsz;
}

vector<intt> Bit(mxN), A(mxN);

void upd(intt x, intt delta) {
	while(x <= mxN) {
		Bit[x] += delta;
		Bit[x] = max(0ll, Bit[x]);
		x += x & -x;
	}
}

intt qry(intt x, intt k, intt ql, intt qr) {
	intt cnt = 0;
	while(x > 0) {
		// if(ql == 0 && qr == 6) {
		// 	cout << cnt << "  " << k << " " << Bit[x] << " " << x << endl;
		// }
		cnt += Bit[x];
		x -= x & -x;
	}
	return cnt;
}

void rem(intt x) {	
	upd(x, -1);
}

void add(intt x) {
	upd(x, 1ll);
}

void solve() {
	intt N, Q;
	cin >> N >> Q;
	bsz = sqrt(N);
	for(intt i = 0; i < N; i++) {
		cin >> A[i];
	}

	vector<query>qrys;
	vector<intt> ans(Q);
	for(intt i = 0; i < Q; i++) {
		intt l, r;
		cin >> l >> r;
		--l;--r;
		qrys.pb({l,r,i});
	}	
	sort(ALL(qrys), cmp);

	intt curl = 0, curr = -1;
	for(intt i = 0; i < Q; i++) {
		intt l = qrys[i].l, r = qrys[i].r, idx = qrys[i].i;
		while(curl > l) {
			curl--; add(A[curl]);
			// cout << "1" << endl;
		}
		while(curl < l) {
			rem(A[curl]); curl++;
			// cout << "11" << endl;
		}
		while(curr < r) {
			curr++;
			add(A[curr]);		
			// cout << "111" << endl;
		}
		while(curr > r) {
			rem(A[curr]); 
			curr--;
			// cout << "1111" << endl;	
		} 

		intt bl = 1, br = mxN, anss = 1;
		while(bl <= br) {
			intt mid = (bl + br) / 2;
			if(qry(mxN, mid, l, r) - qry(mid-1, mid, l, r) >= mid) {
				bl = mid + 1;
				anss = mid;
			} else {
				br = mid - 1;
			}
		}
		ans[idx] = anss;
	}

	for(intt i = 0; i < Q; i++) {
		cout << ans[i] << endl;
	}
}
signed main() {
	ios_base::sync_with_stdio(0); 
	cin.tie(NULL);                
	cout.tie(NULL);
	intt tst = 1;
	// cin >> tst;
	while(tst--) {
		solve();
	}
}

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