nipul1's blog

By nipul1, history, 5 years ago, In English

https://codeforces.net/contest/1181/problem/D

Data Structure used

First ,of all I have calculated number of times a city has hosted olympiad second ,I have associated all cites which have hosted same number of times

//JSD
#include<iostream>
#include<set>
#include<vector>
#define ll long long 
#include<map>
using namespace std;
int main(){
	int n,m,q,a;
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n>>m>>q;
	int Freq[m+1]={0};
	for(int i=0;i<n;i++){
		cin>>a;
		Freq[a]++;
	}
	int maa=0;
	for(int i=0;i<=m;i++){
		maa=max(maa,Freq[i]);
	}
	vector<int > mpq[maa+1];
	for(int i=1;i<=m;i++){
		mpq[Freq[i]].push_back(i);
	}
	vector<int > ans;
	int count=0;
	set<int > s;
	for(ll i=0;i<=maa;i++){
		for(auto x: mpq[i]){
			s.insert(x);
		}
		for(auto x: s){
			ans.push_back(x);
		}
	}
	while(q--){
		ll p;
		cin>>p;
		p-=(n+1);
		if(p<ans.size()){
			cout<<ans[p];
		}
		else{
			cout<<(p-ans.size())%m+1;
		}
		cout<<"\n";
	}
	return 0;
}
  • Vote: I like it
  • -16
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Atleast post your code properly .

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by nipul1 (previous revision, new revision, compare).

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

use segment tree