oj.uz

Submission #362919

# Submission time Handle Problem Language Result Execution time Memory
362919 2021-02-04T17:42:01 Z GioChkhaidze Poklon (COCI17_poklon) C++14
140 / 140
 848 ms 376052 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 5e5 + 5;

int n, q, tr;
int a[N], ans[N], R[N], G[2 * N];
map < int , int > f; 
vector < pair < int , int > > Q[N];
deque < int > dq[N];

void upd(int x, int vl) {
	while (x <= n) {
		G[x] += vl;
		x += (x & -x);
	}
}

void update(int l, int r, int vl) {
	if (l <= r) upd(l, vl), upd(r + 1, -vl);
}

int get(int x) {
	int res = 0;
	while (x > 0) {
		res += G[x];
		x -= (x & -x);
	}
	return res;
}

main () {
	ios::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);
	cin >> n >> q;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];	
		if (!f[a[i]]) {
			f[a[i]] = ++tr;
		}
	}
	
	for (int i = 1; i <= n; ++i) {
		a[i] = f[a[i]];
	}
	
	f.clear();
	for (int i = n; i >= 1; --i) {
		if (!f[a[i]]) 
			R[i] = n + 1;	
				else 
			R[i] = f[a[i]];
		
		f[a[i]] = i;
	}
	
	for (int i = 1; i <= q; ++i) {
		int l, r;
		cin >> l >> r;
		Q[l].push_back({r, i});
	}
	
	for (int l = n; l >= 1; --l) {
		int x = a[l];
		
		if (dq[x].size() == 2) {
			int y = dq[x].front();
			update(y, R[y] - 1, -1);
			dq[x].pop_front();
		}
		
		dq[x].push_back(l);
		
		if (dq[x].size() == 2) {
			int y = dq[x].front();
			update(y, R[y] - 1, 1);
		}
		
		for (int i = 0; i < Q[l].size(); ++i) {
			int id = Q[l][i].second;
			ans[id] = get(Q[l][i].first);
		}
	}
	
	for (int i = 1; i <= q; ++i) {
		cout << ans[i] << "\n";
	}
}

Compilation message

poklon.cpp:32:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   32 | main () {
      |       ^
poklon.cpp: In function 'int main()':
poklon.cpp:79:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |   for (int i = 0; i < Q[l].size(); ++i) {
      |                   ~~^~~~~~~~~~~~~

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 268 ms 348764 KB Output is correct
2 Correct 272 ms 348908 KB Output is correct
3 Correct 267 ms 348780 KB Output is correct
4 Correct 269 ms 349164 KB Output is correct
5 Correct 383 ms 353924 KB Output is correct
6 Correct 351 ms 353900 KB Output is correct
7 Correct 470 ms 359604 KB Output is correct
8 Correct 640 ms 365164 KB Output is correct
9 Correct 710 ms 370488 KB Output is correct
10 Correct 848 ms 376052 KB Output is correct