oj.uz

답안 #610874

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
610874 2022-07-28T16:54:49 Z racsosabe Poklon (COCI17_poklon) C++14
126 / 140
 5000 ms 16440 KB 
#include<bits/stdc++.h>
using namespace::std;

const int N = 500000 + 5;
const int bsize = 710;

int n;
int q;
int a[N];
int id[N];
int ans[N];
int L[N], R[N];

void compress(){
	set<int> S;
	for(int i = 1; i <= n; i++) S.emplace(a[i]);
	int len = 0;
	map<int, int> id;
	for(int x : S){
		id[x] = len++;
	}
	for(int i = 1; i <= n; i++) a[i] = id[a[i]];
}

void solve(){
	vector<int> queries(q);
	iota(queries.begin(), queries.end(), 1);
	sort(queries.begin(), queries.end(), [&] (int i, int j){
		if(id[i] == id[j]) return id[i] & 1 ? R[i] < R[j] : R[i] > R[j];
		return id[i] < id[j];
	});
	unordered_map<int, int> cnt;
	cnt.reserve(524288);
	cnt.max_load_factor(0.25);
	int cur = 0;
	int l = 1, r = 1;
	for(int at : queries){
		while(r <= R[at]){
			cnt[a[r]]++;
			if(cnt[a[r]] == 2) cur++;
			else if(cnt[a[r]] == 3) cur--;
			r += 1;
		}
		while(L[at] < l){
			l--;
			cnt[a[l]]++;
			if(cnt[a[l]] == 2) cur++;
			else if(cnt[a[l]] == 3) cur--;
		}
		while(l < L[at]){
			cnt[a[l]]--;
			if(cnt[a[l]] == 1) cur--;
			else if(cnt[a[l]] == 2) cur++;
			l++;
		}
		while(R[at] + 1 < r){
			r--;
			cnt[a[r]]--;
			if(cnt[a[r]] == 1) cur--;
			else if(cnt[a[r]] == 2) cur++;
		}
		ans[at] = cur;
	}
}

int main(){
	scanf("%d %d", &n, &q);
	for(int i = 1; i <= n; i++) scanf("%d", a + i);
	//compress();
	for(int i = 1; i <= q; i++){
		scanf("%d %d", L + i, R + i);
		id[i] = L[i] / bsize;
	}
	solve();
	for(int i = 1; i <= q; i++) printf("%d\n", ans[i]);
	return 0;
}

Compilation message

poklon.cpp: In function 'int main()':
poklon.cpp:67:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |  scanf("%d %d", &n, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~~
poklon.cpp:68:35: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |  for(int i = 1; i <= n; i++) scanf("%d", a + i);
      |                              ~~~~~^~~~~~~~~~~~~
poklon.cpp:71:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |   scanf("%d %d", L + i, R + i);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
126.0 / 140.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4692 KB Output is correct
2 Correct 5 ms 4692 KB Output is correct
3 Correct 8 ms 4692 KB Output is correct
4 Correct 32 ms 4820 KB Output is correct
5 Correct 715 ms 7092 KB Output is correct
6 Correct 744 ms 7096 KB Output is correct
7 Correct 1805 ms 9440 KB Output is correct
8 Correct 3380 ms 11812 KB Output is correct
9 Correct 4858 ms 14144 KB Output is correct
10 Execution timed out 5029 ms 16440 KB Time limit exceeded