Submission #1046829

#	Time	Username	Problem	Language	Result	Execution time	Memory
1046829		elotelo966	Index (COCI21_index)	C++17	0 / 110	11 ms	13404 KiB

index

#include <bits/stdc++.h>
using namespace std;
 
#define int long long
#define OYY LLONG_MAX
#define mod 1000000007
#define faster ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define FOR for(int i=1;i<=n;i++)
#define mid (start+end)/2
#define lim 200005
#define fi first
#define se second

#define N 200000

int dizi[lim];

struct Node{
	int val;
	Node *left,*right;
	
	Node(){
		val=0;
		left=NULL;
		right=NULL;
	}
	
	Node(Node *tmp){
		val=tmp->val;
		left=tmp->left;
		right=tmp->right;
	}
};

inline void build(Node *node,int start,int end){
	//cout<<start<<" "<<end<<endl;
	if(start==end){
		node->val=0;
		return ;
	}
	node->left=new Node();
	node->right=new Node();
	build(node->left,start,mid),build(node->right,mid+1,end);
}

inline void update(Node *node,int start,int end,int l,int r,int val){
	//cout<<start<<" "<<end<<" "<<l<<" "<<r<<" "<<val<<endl;
	if(start>end || start>r || end<l || node==NULL)return ;
	if(start>=l && end<=r){
		node->val=val;
		return ;
	}
	if(l<=mid)node->left=new Node(node->left);
	else node->right=new Node(node->right);
	update(node->left,start,mid,l,r,val),update(node->right,mid+1,end,l,r,val);
	node->val=node->left->val+node->right->val;
}

inline int query(Node *node,int start,int end,int l,int r){
	if(start>end || start>r || end<l || node==NULL)return 0;
	if(start>=l && end<=r){
		return node->val;
	}
	return query(node->left,start,mid,l,r)+query(node->right,mid+1,end,l,r);
}

int32_t main(){
	faster
	int n,q;cin>>n>>q;
	FOR{
		cin>>dizi[i];
	}
	
	Node *tmp=new Node();
	
	vector<Node*> roots;
	
	build(tmp,1,N);
	
	roots.push_back(tmp);
	
	FOR{
		tmp=new Node(roots[i-1]);
		update(tmp,1,N,dizi[i],dizi[i],1);
		roots.push_back(tmp);
	}
	
	while(q--){
		int a,b;cin>>a>>b;
		int l=1,r=N;
		while(l<=r){
			int m=(l+r)/2;
			//cout<<query(roots[b],1,N,m,N)<<" "<<query(roots[a-1],1,N,m,N)<<" "<<m<<endl;
			if(query(roots[b],1,N,m,N)-query(roots[a-1],1,N,m,N)>=m){
				l=m+1;
			}
			else r=m-1;
		}
		cout<<r<<'\n';
	}
	return 0;
}

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