제출 #1172622

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1172622		ByeWorld	Index (COCI21_index)	C++20	110 / 110	1357 ms	197276 KiB

index

#include <bits/stdc++.h>
// #define int long long
#define ll long long
#define pb push_back
#define fi first
#define se second
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
#define ld long double
using namespace std;
typedef pair<int,int> pii;
typedef pair<int,pii> ipii;
const int MAXN = 2e5+10;
const int MAXA = 2e5;
const int INF = 1e9+100;
const int SQRT = 500;
const int LOG = 21;
void chmn(auto &a, auto b){ a = min(a, b); }
void chmx(int &a, int b){ a = max(a, b); }

int n, q, a[MAXN];

struct seg {
	int l, r, val; 
	seg *le, *ri;
	void bd(int l2, int r2){
		l = l2; r = r2; val = 0;
	}
	void bnc(){
		if(le==NULL){
			le = new seg(); le->bd(l, md);
		}
		if(ri==NULL){
			ri = new seg(); ri->bd(md+1,r);
		}
	}
	int que(int x, int y){
		if(x<=l && r<=y) return val;
		if(r<x || y<l) return 0;
		bnc();
		return le->que(x,y) + ri->que(x,y);
	}
	seg* upd(int x, int p){
		if(r<x || x<l) return this;
		if(l==r){
			seg *ret; ret = new seg();
			*ret = *this;
			ret->val += p;
			return ret;
		}
		bnc();
		seg *ret; ret = new seg();
		*ret = *this;
		ret->le = le->upd(x,p);
		ret->ri = ri->upd(x,p);
		ret->val = ret->le->val + ret->ri->val;
		return ret;
	}
} *A[MAXN];
signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>q; 
	for(int i=1; i<=n; i++){
		cin>>a[i]; 
	}
	A[0] = new seg(); A[0]->bd(1,MAXA);
	for(int i=1; i<=n; i++){
		A[i] = A[i-1]->upd(a[i],1);
		// cout << A[i]->que(1,3)<<' '<<A[i]->val <<' '<<a[i]<< " pp\n";
	}
	for(int i=1; i<=q; i++){
		int le, ri; cin>>le>>ri;
		// cout << A[ri]->que(1,6)<<' '<<A[le-1]->que(1,6)<< " pp\n";
		int l=1, r=MAXA, mid=0, cnt=-1;
		while(l<=r){
			mid = md;
			if(A[ri]->que(mid,MAXA)-A[le-1]->que(mid,MAXA) >= mid)
				l = mid+1, cnt = mid;
			else r = mid-1;
		}
		cout << cnt << '\n';
	}
}

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