oj.uz

답안 #402059

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
402059 2021-05-11T09:04:43 Z keta_tsimakuridze Poklon (COCI17_poklon) C++14
140 / 140
 4163 ms 28616 KB 
#include<bits/stdc++.h>
#define f first
#define int long long
#define s second
#define pii pair<pair<int,int>,int> 
using namespace std;
const int N=5e5+5,mod=1e9+7;
int t,c[N],cnt[N],a_[N],ans[N],q,n,Block;
string s;
pair<int,int> a[N];
pii p[N];
bool compare(pii a,pii b){
	if((a.f.f-1)/Block != (b.f.f-1)/Block) return a.f.f < b.f.f;
	return a.f.s < b.f.s;
}
void remove(int u) {
	c[cnt[a_[u]]]--;
	cnt[a_[u]]--; 
	c[cnt[a_[u]]]++;
}
void add(int u){
	c[cnt[a_[u]]]--; 
	cnt[a_[u]]++;
	c[cnt[a_[u]]]++;
}
 main(){
	// t=1;
	cin>>n>>q;
	Block=sqrt(n);
	for(int i=1;i<=n;i++){
		cin >> a[i].f;
		a[i].s = i;
	}
	sort(a+1,a+n+1);
	int idx=0;
	for(int i=1;i<=n;i++){
		if(a[i].f!=a[i-1].f) idx++;
		a_[a[i].s] = idx;
	}
	for(int i=1;i<=q;i++){
		cin >> p[i].f.f >> p[i].f.s;
		p[i].s = i;
	}
	sort(p+1,p+q+1,compare);
	int curL = 0 , curR = -1;
	for(int i=1;i<=q;i++){
		int L = p[i].f.f;
		int R = p[i].f.s; 
		while(curL < L) { 
			remove(curL);
			curL++;
		}
		while(curL > L){
			curL--;
			add(curL);
		}
		while(curR < R){
			curR++;
			add(curR);
		}
		while(curR > R){
			remove(curR);
			curR--;
		} 
		ans[p[i].s] = c[2];
	}
	for(int i=1;i<=q;i++) cout<<ans[i]<<endl;
}

Compilation message

poklon.cpp:26:2: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   26 |  main(){
      |  ^~~~

Subtask #1
140.0 / 140.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 3 ms 332 KB Output is correct
3 Correct 4 ms 332 KB Output is correct
4 Correct 17 ms 612 KB Output is correct
5 Correct 515 ms 5944 KB Output is correct
6 Correct 522 ms 5940 KB Output is correct
7 Correct 1259 ms 11736 KB Output is correct
8 Correct 2119 ms 17424 KB Output is correct
9 Correct 3094 ms 23016 KB Output is correct
10 Correct 4163 ms 28616 KB Output is correct