Submission #1046918

#	Time	Username	Problem	Language	Result	Execution time	Memory
1046918		vjudge1	Index (COCI21_index)	C++17	110 / 110	515 ms	134328 KiB

index

#include<bits/stdc++.h>
#define ll long long
#define MOD 1000000007
#define all(x) x.begin(),x.end()
#define ff first
#define ss second
#define pb push_back
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

using namespace std;

const int N=200000;

struct Node{
	int val=0;
	Node *l=NULL,*r=NULL;
};

void build(Node *node,int l,int r){
	if(l==r)return;
	int mid=(l+r)/2;
	node->l=new Node;
	node->r=new Node;
	build(node->l,l,mid);
	build(node->r,mid+1,r);
	return;
}

void update(Node *node,Node *pre,int l,int r,int x,int y){
	if(l==r){
		node->val=y;
		return;
	}
	int mid=(l+r)/2;
	if(x<=mid){
		node->r=pre->r;
		node->l=new Node;
		update(node->l,pre->l,l,mid,x,y);
	}
	else{
		node->l=pre->l;
		node->r=new Node;
		update(node->r,pre->r,mid+1,r,x,y);
	}
	node->val=node->l->val+node->r->val;
	return;
}

int query(Node *node,Node *pre,int l,int r,int k){
	if(l==r){
		return l;
	}
	int mid=(l+r)/2;
	if(node->r->val-pre->r->val+k>=mid+1){
		return query(node->r,pre->r,mid+1,r,k);
	}
	return query(node->l,pre->l,l,mid,k+node->r->val-pre->r->val);
}

int32_t main(){
	fast;
	int n,q;
	cin>>n>>q;
	vector<int>arr(n+1);
	for(int i=1;i<=n;i++){
		cin>>arr[i];
	}
	vector<Node*>pre(n+1);
	pre[0]=new Node;
	build(pre[0],1,N);
	vector<int>cnt(N+1);
	for(int i=1;i<=n;i++){
		cnt[arr[i]]++;
		pre[i]=new Node;
		update(pre[i],pre[i-1],1,N,arr[i],cnt[arr[i]]);
	}
	while(q--){
		int l,r;
		cin>>l>>r;
		cout<<query(pre[r],pre[l-1],1,N,0)<<endl;
	}
}

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