oj.uz

Submission #40981

# Submission time Handle Problem Language Result Execution time Memory
40981 2018-02-10T18:47:19 Z IvanC Poklon (COCI17_poklon) C++14
0 / 140
 5000 ms 524288 KB 
#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;
deque<int> aparicoes[MAXV];
int bit[MAXV],vetor[MAXN],resposta[MAXN],N,Q;
deque<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];
		aparicoes[x].push_back(i);
		if(aparicoes[x].size() == 2) update(i,1);
		else if(aparicoes[x].size() == 3) update(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(!perguntas.empty() && get<0>(perguntas.front()) == i){
			resposta[get<2>(perguntas.front())] = read(get<1>(perguntas.front()));
			perguntas.pop_front();
		}
		int x = vetor[i];
		aparicoes[x].pop_front();
		if(aparicoes[x].size() >= 1) update(aparicoes[x][0],-1);
		if(aparicoes[x].size() >= 2) update(aparicoes[x][1],2);
		if(aparicoes[x].size() >= 3) update(aparicoes[x][2],-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:25: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:27:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&vetor[i]);
                        ^
poklon.cpp:35: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
0 / 140.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5080 ms 524288 KB Time limit exceeded
2 Execution timed out 5086 ms 524288 KB Time limit exceeded
3 Execution timed out 5183 ms 524288 KB Time limit exceeded
4 Execution timed out 5172 ms 524288 KB Time limit exceeded
5 Execution timed out 5125 ms 524288 KB Time limit exceeded
6 Execution timed out 5077 ms 524288 KB Time limit exceeded
7 Execution timed out 5103 ms 524288 KB Time limit exceeded
8 Execution timed out 5072 ms 524288 KB Time limit exceeded
9 Execution timed out 5078 ms 524288 KB Time limit exceeded
10 Execution timed out 5076 ms 524288 KB Time limit exceeded