| # | Time | Username | Problem | Language | Result | Execution time | Memory | 
|---|---|---|---|---|---|---|---|
| 40984 | IvanC | Poklon (COCI17_poklon) | C++14 | 362 ms | 15492 KiB | 
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define LSOne(S) (S & (-S))
using namespace std;
typedef tuple<int,int,int> trinca;
const int MAXN = 5*1e5 + 10;
const int MAXV = 1e6 + 10;
int bit[MAXN],vetor[MAXN],resposta[MAXN],N,Q,ultimo[MAXV],prox[MAXN],ptr,marcado[MAXV];
vector<trinca> perguntas;
void update(int idx,int delta){
	while(idx < MAXN){
		bit[idx] += delta;
		idx += LSOne(idx);
	}
}
int read(int idx){
	int ans = 0;
	while(idx > 0){
		ans += bit[idx];
		idx -= LSOne(idx);
	}
	return ans;
}
int main(){
	scanf("%d %d",&N,&Q);
	for(int i = 1;i<=N;i++){
		scanf("%d",&vetor[i]);
		int x = vetor[i];
		ultimo[x] = -1;
	}
	for(int i = N;i>=1;i--){
		int x = vetor[i];
		prox[i] = ultimo[x];
		ultimo[x] = i;
	}
	for(int i =1;i<=N;i++){
		int x = vetor[i];
		if(marcado[x]) continue;
		marcado[x] = 1;
		if(prox[i] != -1){
			update(prox[i],1);
			if(prox[prox[i]] != -1){
				update(prox[prox[i]],-1);
			}
		}
	}
	for(int i = 1;i<=Q;i++){
		int a,b;
		scanf("%d %d",&a,&b);
		perguntas.push_back(make_tuple(a,b,i));
	}
	sort(perguntas.begin(),perguntas.end());
	for(int i = 1;i<=N;i++){
		while(ptr < Q && get<0>(perguntas[ptr]) == i){
			resposta[get<2>(perguntas[ptr])] = read(get<1>(perguntas[ptr]));
			ptr++;
		}
		if(ptr == Q) break;
		if(prox[i] != -1){
			update(prox[i],-1);
			if(prox[prox[i]] != -1){
				update(prox[prox[i]],2);
				if(prox[prox[prox[i]]] != -1){
					update(prox[prox[prox[i]]],-1);
				}
			}
		}
	}
	for(int i = 1;i<=Q;i++) printf("%d\n",resposta[i]);
	return 0;
}
Compilation message (stderr)
| # | Verdict | Execution time | Memory | Grader output | 
|---|---|---|---|---|
| Fetching results... | ||||
