Submission #40984

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
40984	2018-02-10T18:56:32 Z	IvanC	Poklon (COCI17_poklon)	C++14	140 / 140	362 ms	15492 KB

poklon

#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

poklon.cpp: In function 'int main()':
poklon.cpp:24:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&N,&Q);
                      ^
poklon.cpp:26:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&vetor[i]);
                        ^
poklon.cpp:48:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&a,&b);
                       ^

Subtask #1

140.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	616 KB	Output is correct
3	Correct	2 ms	696 KB	Output is correct
4	Correct	4 ms	780 KB	Output is correct
5	Correct	66 ms	3612 KB	Output is correct
6	Correct	67 ms	3696 KB	Output is correct
7	Correct	141 ms	6664 KB	Output is correct
8	Correct	215 ms	9560 KB	Output is correct
9	Correct	345 ms	12572 KB	Output is correct
10	Correct	362 ms	15492 KB	Output is correct