제출 #1174171

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1174171		javkhlantogs	Poklon (COCI17_poklon)	C++20	140 / 140	1716 ms	45220 KiB

poklon

#include<bits/stdc++.h>
#define ll long long
using namespace std;
map<ll,vector<ll>> mp;
vector<ll> a,b;
ll k,cnt=0;
bool check(vector<ll> f,vector<ll> g){
	if(f[0]/k==g[0]/k) return f[1]<g[1];
	return f[0]<g[0];
}
void rem(ll x){
	if(b[x]==3) cnt++;
	if(b[x]==2) cnt--;
	b[x]--;
}
void add(ll x){
	if(b[x]==1) cnt++;
	if(b[x]==2) cnt--;
	b[x]++;
}
int main(){
	ll n,q,i,j,l=0,r=0;
	cin>>n>>q;
	a.resize(n+1);
	b.resize(n+1);
	vector<ll> ans(q);
	k=sqrt(n);
	for(i=1 ; i<=n ; i++){
		cin>>a[i];
		mp[a[i]].push_back(i);
	}
	i=0;
	for(auto v:mp){
		for(j=0 ; j<v.second.size() ; j++){
			a[v.second[j]]=i;
		}
		i++;
	}
	vector<vector<ll>> x(q,vector<ll>(3));
	for(i=0 ; i<q ; i++){
		cin>>x[i][0]>>x[i][1];
		x[i][2]=i;
	}
	sort(x.begin(),x.end(),check);
	l=1;
	r=0;
	for(i=0 ; i<q ; i++){
		while(l<x[i][0]){
			rem(a[l]);	
			l++;
		}
		while(r<x[i][1]){
			r++;
			add(a[r]);
		}
		while(r>x[i][1]){
			rem(a[r]);
			r--;
		}
		while(l>x[i][0]) {
      l--;
      add(a[l]);
    }
		ans[x[i][2]]=cnt;
	}
	for(i=0 ; i<q ; i++){
		cout<<ans[i]<<"\n";
	}
	return 0;
}

• Subtask 1: 140 / 140