Submission #1019741

#	Time	Username	Problem	Language	Result	Execution time	Memory
1019741		ZeroCool	Poklon (COCI17_poklon)	C++14	140 / 140	837 ms	29776 KiB

poklon

#include <bits/stdc++.h>
using namespace std;
  
#define int long long
  
#define ll long long
#define ar array
#define ld long double
  
const int N = 5e5 + 20;
const int MOD = 1e9 + 7;
const int K = 700;
const int INF = 1e17;
const int LOG = 34;

int ans = 0;
int cnt[N];
int A[N];
void add(int x){
	x = A[x];
	ans -= cnt[x] == 2;
	cnt[x]++;
	ans += cnt[x] == 2;
}

void rem(int x){
	x = A[x];
	ans -= cnt[x] == 2;
	cnt[x]--;
	ans += cnt[x] == 2;
}

bool cmp(ar<int, 3> a, ar<int,3 > b){
	return ar<int,2>{a[0] / K, a[1]} < ar<int, 2>{b[0] / K, b[1]};
}

signed main(){ios::sync_with_stdio(false);cin.tie(0);   
	int n, q;
	cin>>n>>q;
	map<int,int> mp;
	int id = 0;
	for(int i = 0;i < n;i++){
		cin>>A[i];
		if(!mp.count(A[i]))mp[A[i]] = id++;
		A[i] = mp[A[i]];
		//cout<<A[i]<<" ";
	}
	
	//cout<<endl;
	ar<int, 3> que[q];
	for(int i = 0;i < q;i++){
		cin>>que[i][0]>>que[i][1];
		--que[i][0], --que[i][1];
		que[i][2] = i;
	}
	
	int ml = 0;
	int mr = -1;
	sort(que, que + q, cmp);
	int res[q];
	for(int i = 0;i < q;i++){
		int l = que[i][0];
		int r = que[i][1];
		int ind = que[i][2];
		//cout<<i<<endl;
		while(ml > l)add(--ml);
		while(mr < r)add(++mr);
		while(ml < l)rem(ml++);
		while(mr > r)rem(mr--);
		
		res[ind] = ans;
	}
	for(int i = 0;i < q;i++)cout<<res[i]<<" ";
}

// Te molam da raboti!

• Subtask 1: 140 / 140