oj.uz

Submission #610899

# Submission time Handle Problem Language Result Execution time Memory
610899 2022-07-28T17:24:16 Z racsosabe Poklon (COCI17_poklon) C++14
140 / 140
 1026 ms 30636 KB 
#include<bits/stdc++.h>
using namespace::std;

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

int n;
int q;
int a[N];
int L[N];
int val[N];
int block[SQRT];
int ans[N];
int last1[N];
int last2[N];
int last3[N];
vector<int> Q[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 update(int x, int y){
	int idx = x / bsize;
	block[idx] += y;
	val[x] += y;
}

int query(int l, int r){
	int res = 0;
	while(l % bsize and l <= r){
		res += val[l];
		l++;
	}
	while(l + bsize - 1 <= r){
		res += block[l / bsize];
		l += bsize;
	}
	while(l <= r){
		res += val[l];
		l++;
	}
	return res;
}

int get_sum(int pos){
	return query(1, pos);
}

void fix(int i){
	int x = a[i];
	int l1 = last1[x], l2 = last2[x], l3 = last3[x];
	if(l2){
		update(l3 + 1, -1);
		update(l2 + 1, 1);
	}
	if(l1){
		update(l2 + 1, 1);
		update(l1 + 1, -1);
	}
	last3[x] = l2;
	last2[x] = l1;
	last1[x] = i;
}

void download(int i){
	for(int at : Q[i]){
		ans[at] = get_sum(L[at]);
	}
}

void solve(){
	for(int i = 1; i <= n; i++){
		fix(i);
		download(i);
	}
}

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++){
		int r;
		scanf("%d %d", L + i, &r);
		Q[r].emplace_back(i);
	}
	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:88:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |  scanf("%d %d", &n, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~~
poklon.cpp:89:35: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |  for(int i = 1; i <= n; i++) scanf("%d", a + i);
      |                              ~~~~~^~~~~~~~~~~~~
poklon.cpp:93:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |   scanf("%d %d", L + i, &r);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12116 KB Output is correct
2 Correct 6 ms 12092 KB Output is correct
3 Correct 9 ms 12060 KB Output is correct
4 Correct 14 ms 12244 KB Output is correct
5 Correct 162 ms 16168 KB Output is correct
6 Correct 165 ms 16184 KB Output is correct
7 Correct 363 ms 19788 KB Output is correct
8 Correct 560 ms 23332 KB Output is correct
9 Correct 773 ms 26900 KB Output is correct
10 Correct 1026 ms 30636 KB Output is correct