제출 #1174138

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

poklon

#include<bits/stdc++.h>
#define ll long long
using namespace std;
map<ll,ll> mp;
vector<ll> a;
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(mp[x]==3) cnt++;
	if(mp[x]==2) cnt--;
	mp[x]--;
}
void add(ll x){
	if(mp[x]==1) cnt++;
	if(mp[x]==2) cnt--;
	mp[x]++;
}
int main(){
	ll n,q,i,j,l=0,r=0;
	cin>>n>>q;
	a.resize(n+1);
	vector<ll> ans(q);
	k=sqrt(n);
	for(i=1 ; i<=n ; i++){
		cin>>a[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);
	for(i=x[0][0] ; i<=x[0][1] ; i++){
		mp[a[i]]++;
	}
	for(auto v:mp){
		if(v.second==2) cnt++;
	}
	ans[x[0][2]]=cnt;
	l=x[0][0];
	r=x[0][1];
	for(i=1 ; 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--;
		}
		ans[x[i][2]]=cnt;
	}
	for(i=0 ; i<q ; i++){
		cout<<ans[i]<<"\n";
	}
	return 0;
}

• Subtask 1: 0 / 140