oj.uz

답안 #40984

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
40984 2018-02-10T18:56:32 Z IvanC Poklon (COCI17_poklon) C++14
140 / 140
 362 ms 15492 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;
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

# 결과 실행 시간 메모리 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