Submission #1046936

#	Time	Username	Problem	Language	Result	Execution time	Memory
1046936		DangerNoodle7591	Index (COCI21_index)	C++17	110 / 110	1161 ms	132032 KiB

index

#include <bits/stdc++.h>
using namespace std;
#define lalala ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define ll long long 
#define int long long int
#define endl '\n'
#define N 200105
#define MM 200000
#define mod 1000000007
#define pb push_back
#define p push
#define ins insert
#define f first
#define s second

//persistent segment tree kodu ///////////////////////////////////////////////////////////////////////////////////////////////////
int n;
struct node{
	node *left, *right;
	int val;
	node(node* a,node* b){
		val=0;
		left=a;
		right=b;
		if(a) val+=a->val;
		if(b) val+=b->val;
	}
	node(){
		val=0;
		left=NULL;right=NULL;
	}
};

vector<node*> baslar;

node* update(node* x,int l,int r,int hed){
	if(l==r){
		node* yeni=new node;
		yeni->val=x->val+1;
		return yeni;
	}
	if(x->left==NULL)x->left=new node;
	if(x->right==NULL)x->right=new node;
	int mid=(l+r)/2;
	if(hed<=mid){
		return new node(update(x->left,l,mid,hed),x->right);
	}
	return new node(x->left,update(x->right,mid+1,r,hed));
	
}
inline int qua(node* x,int l,int r,int s,int e){
	if(l>r||s>r||e<l||x==NULL) return 0;
	if(s<=l&&r<=e)return x->val;
	int mid=(l+r)/2;
	return qua(x->left, l,mid,s,e)+qua(x->right,mid+1,r,s,e);
}
int cev(int x,int y){
	int l=1,r=n;
	int yes=-1;
	while(l<=r){
		int mid=(l+r)/2;
		int a=qua(baslar[x-1],1,MM,1,MM-mid+1);
		int b=qua(baslar[y],1,MM,1,MM-mid+1);
		//cout<<l<<" "<<r<<" "<<mid<<" "<<a<<" "<<b<<endl;
		if(b-a>=mid){
			yes=mid;
			l=mid+1;
		}
		else r=mid-1;

	}
	return yes;
}
signed main(){
	lalala;
	node* bas=new node;
	baslar.pb(bas);
	int q;cin>>n>>q;
	for(int i=1;i<=n;i++){
		int x;cin>>x;
		int y=MM-x+1;
		node* yeni=update(baslar[baslar.size()-1],1,MM,y);
		baslar.pb(yeni);
	}

	while(q--){
		int x,y;cin>>x>>y;
		cout<<cev(x,y)<<endl;
	}

}

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