oj.uz

Submission #362917

# Submission time Handle Problem Language Result Execution time Memory
362917 2021-02-04T17:37:35 Z GioChkhaidze Poklon (COCI17_poklon) C++14
0 / 140
 342 ms 524292 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 6;

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

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

void update(int l, int r, int vl) {
	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;
	map < int , int > f; 
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
	}
	
	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:72: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]
   72 |   for (int i = 0; i < Q[l].size(); ++i) {
      |                   ~~^~~~~~~~~~~~~

Subtask #1
0 / 140.0

# Verdict Execution time Memory Grader output
1 Runtime error 342 ms 524292 KB Execution killed with signal 9
2 Runtime error 312 ms 524292 KB Execution killed with signal 9
3 Runtime error 313 ms 524292 KB Execution killed with signal 9
4 Runtime error 315 ms 524292 KB Execution killed with signal 9
5 Runtime error 302 ms 524292 KB Execution killed with signal 9
6 Runtime error 305 ms 524292 KB Execution killed with signal 9
7 Runtime error 303 ms 524292 KB Execution killed with signal 9
8 Runtime error 322 ms 524292 KB Execution killed with signal 9
9 Runtime error 303 ms 524292 KB Execution killed with signal 9
10 Runtime error 309 ms 524292 KB Execution killed with signal 9