Submission #1154065

#	Time	Username	Problem	Language	Result	Execution time	Memory
1154065		i271828	Index (COCI21_index)	C++20	0 / 110	49 ms	576 KiB

index

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
using namespace std;
const int MAX=200005;

struct MrgSort{
	int s, e, m;
	MrgSort* l;MrgSort* r;
	vector<int> A={};
	MrgSort(int* X, int s, int e){
		this->s=s;
		this->e=e;
		this->m=(s+e)>>1;
		if (s==e){
			A.push_back(X[s]);
		}else{
			l=new MrgSort(X,s,m);
			r=new MrgSort(X,m+1,e);
			int lp=s,rp=m+1;
			while (A.size() < e-s+1){
				if (lp<=m && (rp>e || l->A[lp-s] < r->A[rp-m-1])){
					A.push_back(l->A[lp-s]);
					lp++;
				}else{
					A.push_back(r->A[rp-m-1]);
					rp++;
				}
			}
		}
	}
	
	int qry(int a,int b,int v){
		if (b<s||a>e) return 0;
		if (a<=s&&b>=e) return e-s+1-(lower_bound(A.begin(),A.end(),v)-A.begin());
		return l->qry(a,b,v)+r->qry(a,b,v);
	}
};

int N;
int Q;
int A[MAX];

int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin>>N>>Q;
	for (int i=0;i<N;i++){
		cin>>A[i];
	}
	
	auto m=new MrgSort(A,0,N-1);
	for (int q=0;q<Q;q++){
		int a,b;
		cin>>a>>b;
		for (int i=(b-a+1); i>=0; i--){
			if (m->qry(a,b,i)>=i){
				cout<<i<<'\n';
				break;
			}
		}
	}
}

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