oj.uz

Submission #1046877

# Submission time Handle Problem Language Result Execution time Memory
1046877 2024-08-07T05:37:47 Z vjudge1 Index (COCI21_index) C++17
110 / 110
 961 ms 134344 KB 
    #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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 13404 KB Output is correct
2 Correct 11 ms 13404 KB Output is correct
3 Correct 11 ms 13404 KB Output is correct
4 Correct 11 ms 13404 KB Output is correct
5 Correct 13 ms 13404 KB Output is correct
6 Correct 12 ms 13540 KB Output is correct
7 Correct 11 ms 13412 KB Output is correct
8 Correct 13 ms 13460 KB Output is correct
9 Correct 12 ms 13348 KB Output is correct
10 Correct 12 ms 13400 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 13404 KB Output is correct
2 Correct 11 ms 13404 KB Output is correct
3 Correct 11 ms 13404 KB Output is correct
4 Correct 11 ms 13404 KB Output is correct
5 Correct 13 ms 13404 KB Output is correct
6 Correct 12 ms 13540 KB Output is correct
7 Correct 11 ms 13412 KB Output is correct
8 Correct 13 ms 13460 KB Output is correct
9 Correct 12 ms 13348 KB Output is correct
10 Correct 12 ms 13400 KB Output is correct
11 Correct 172 ms 43212 KB Output is correct
12 Correct 167 ms 43248 KB Output is correct
13 Correct 211 ms 43208 KB Output is correct
14 Correct 181 ms 43292 KB Output is correct
15 Correct 167 ms 43304 KB Output is correct
16 Correct 172 ms 43392 KB Output is correct
17 Correct 167 ms 43208 KB Output is correct
18 Correct 165 ms 43092 KB Output is correct
19 Correct 167 ms 43208 KB Output is correct
20 Correct 170 ms 43152 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 13404 KB Output is correct
2 Correct 11 ms 13404 KB Output is correct
3 Correct 11 ms 13404 KB Output is correct
4 Correct 11 ms 13404 KB Output is correct
5 Correct 13 ms 13404 KB Output is correct
6 Correct 12 ms 13540 KB Output is correct
7 Correct 11 ms 13412 KB Output is correct
8 Correct 13 ms 13460 KB Output is correct
9 Correct 12 ms 13348 KB Output is correct
10 Correct 12 ms 13400 KB Output is correct
11 Correct 172 ms 43212 KB Output is correct
12 Correct 167 ms 43248 KB Output is correct
13 Correct 211 ms 43208 KB Output is correct
14 Correct 181 ms 43292 KB Output is correct
15 Correct 167 ms 43304 KB Output is correct
16 Correct 172 ms 43392 KB Output is correct
17 Correct 167 ms 43208 KB Output is correct
18 Correct 165 ms 43092 KB Output is correct
19 Correct 167 ms 43208 KB Output is correct
20 Correct 170 ms 43152 KB Output is correct
21 Correct 917 ms 134344 KB Output is correct
22 Correct 927 ms 134308 KB Output is correct
23 Correct 961 ms 134116 KB Output is correct
24 Correct 947 ms 134316 KB Output is correct
25 Correct 921 ms 134332 KB Output is correct
26 Correct 933 ms 134336 KB Output is correct
27 Correct 955 ms 134268 KB Output is correct
28 Correct 918 ms 134332 KB Output is correct
29 Correct 924 ms 134252 KB Output is correct
30 Correct 904 ms 134212 KB Output is correct