제출 #1174067

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1174067		Nomio	Poklon (COCI17_poklon)	C++20	84 / 140	5093 ms	10184 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;
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];
	for(int i = 0; i < n; i++) {
		cin >> 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];
	map<ll, int> c;
	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: 84 / 140