Submission #1174069

#	Time	Username	Problem	Language	Result	Execution time	Memory
1174069		Nomio	Poklon (COCI17_poklon)	C++20	140 / 140	485 ms	11152 KiB

poklon

#include<bits/stdc++.h>
#define s second
#define f first
#define P pair<pair<int, int>, int> 
using namespace std;
using ll = long long;
int sz;
const int maxn = 5e5 + 1;
int c[maxn] {};
bool cmp(P a, P b) {
	if(a.f.f / sz == b.f.f / sz) {
		if((a.f.f / sz) % 2 == 0) return (a.f.s < b.f.s);
		else return (a.f.s > b.f.s);
	} return (a.f.f < b.f.f);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, q;
	cin >> n >> q;
	sz = sqrt(n) + 1;
	int a[n];
	set<int> s;
	for(int i = 0; i < n; i++) {
		cin >> a[i];
		s.insert(a[i]);
	}
	map<int, int> M;
	int id = 0;
	while(!s.empty()) {
		int x = *s.begin();
		s.erase(x);
		M[x] = id;
		id++;
	}
	for(int i = 0; i < n; i++) {
		a[i] = M[a[i]];
	}
	vector<P> v;
	for(int i = 0; i < q; i++) {
		int x, y;
		cin >> x >> y;
		x--, y--;
		v.push_back({{x, y}, i});
	}
	sort(v.begin(), v.end(), cmp);
	int L = 0, R = 0;
	int b[q];
	int cnt = 0;
	c[a[0]] = 1;
	for(P p : v) {
		int l = p.f.f;
		int r = p.f.s;
		int id = p.s;
		while(R < r) {
			R++;
			c[a[R]]++;
			if(c[a[R]] == 2) cnt++;
			if(c[a[R]] == 3) cnt--;
		}
		while(L > l) {
			L--;
			c[a[L]]++;
			if(c[a[L]] == 2) cnt++;
			if(c[a[L]] == 3) cnt--;
		}
		while(L < l) {
			c[a[L]]--;
			if(c[a[L]] == 1) cnt--;
			if(c[a[L]] == 2) cnt++;
			L++;
		}
		while(R > r) {
			c[a[R]]--;
			if(c[a[R]] == 1) cnt--;
			if(c[a[R]] == 2) cnt++;
			R--;
		}
		b[id] = cnt;
	}
	for(int i = 0; i < q; i++) {
		cout << b[i] << '\n';
	}
	return 0;
}

• Subtask 1: 140 / 140