Submission #362919

#	Time	Username	Problem	Language	Result	Execution time	Memory
362919		GioChkhaidze	Poklon (COCI17_poklon)	C++14	140 / 140	848 ms	376052 KiB

poklon

#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 (stderr)

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 / 140