oj.uz

Submission #1046831

# Submission time Handle Problem Language Result Execution time Memory
1046831 2024-08-07T03:47:10 Z elotelo966 Index (COCI21_index) C++17
110 / 110
 1006 ms 138044 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 10 ms 13404 KB Output is correct
2 Correct 10 ms 13608 KB Output is correct
3 Correct 18 ms 13404 KB Output is correct
4 Correct 15 ms 13360 KB Output is correct
5 Correct 13 ms 13404 KB Output is correct
6 Correct 11 ms 13356 KB Output is correct
7 Correct 11 ms 13404 KB Output is correct
8 Correct 14 ms 13528 KB Output is correct
9 Correct 12 ms 13448 KB Output is correct
10 Correct 11 ms 13404 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 13404 KB Output is correct
2 Correct 10 ms 13608 KB Output is correct
3 Correct 18 ms 13404 KB Output is correct
4 Correct 15 ms 13360 KB Output is correct
5 Correct 13 ms 13404 KB Output is correct
6 Correct 11 ms 13356 KB Output is correct
7 Correct 11 ms 13404 KB Output is correct
8 Correct 14 ms 13528 KB Output is correct
9 Correct 12 ms 13448 KB Output is correct
10 Correct 11 ms 13404 KB Output is correct
11 Correct 166 ms 44068 KB Output is correct
12 Correct 185 ms 43984 KB Output is correct
13 Correct 164 ms 43980 KB Output is correct
14 Correct 163 ms 43980 KB Output is correct
15 Correct 171 ms 44056 KB Output is correct
16 Correct 173 ms 43976 KB Output is correct
17 Correct 169 ms 43972 KB Output is correct
18 Correct 173 ms 44196 KB Output is correct
19 Correct 169 ms 44032 KB Output is correct
20 Correct 170 ms 44104 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 13404 KB Output is correct
2 Correct 10 ms 13608 KB Output is correct
3 Correct 18 ms 13404 KB Output is correct
4 Correct 15 ms 13360 KB Output is correct
5 Correct 13 ms 13404 KB Output is correct
6 Correct 11 ms 13356 KB Output is correct
7 Correct 11 ms 13404 KB Output is correct
8 Correct 14 ms 13528 KB Output is correct
9 Correct 12 ms 13448 KB Output is correct
10 Correct 11 ms 13404 KB Output is correct
11 Correct 166 ms 44068 KB Output is correct
12 Correct 185 ms 43984 KB Output is correct
13 Correct 164 ms 43980 KB Output is correct
14 Correct 163 ms 43980 KB Output is correct
15 Correct 171 ms 44056 KB Output is correct
16 Correct 173 ms 43976 KB Output is correct
17 Correct 169 ms 43972 KB Output is correct
18 Correct 173 ms 44196 KB Output is correct
19 Correct 169 ms 44032 KB Output is correct
20 Correct 170 ms 44104 KB Output is correct
21 Correct 960 ms 137996 KB Output is correct
22 Correct 961 ms 137956 KB Output is correct
23 Correct 925 ms 137908 KB Output is correct
24 Correct 1006 ms 137852 KB Output is correct
25 Correct 952 ms 138044 KB Output is correct
26 Correct 942 ms 137900 KB Output is correct
27 Correct 984 ms 137920 KB Output is correct
28 Correct 992 ms 138028 KB Output is correct
29 Correct 985 ms 137932 KB Output is correct
30 Correct 947 ms 137920 KB Output is correct