Submission #1046877

#	Time	Username	Problem	Language	Result	Execution time	Memory
1046877		vjudge1	Index (COCI21_index)	C++17	110 / 110	961 ms	134344 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: 20 / 20
• Subtask 2: 40 / 40
• Subtask 3: 50 / 50