Submission #1174044

#	Time	Username	Problem	Language	Result	Execution time	Memory
1174044		nuutsnoynton	Poklon (COCI17_poklon)	C++20	84 / 140	5094 ms	20092 KiB

poklon

#include<bits/stdc++.h>

using namespace std;
using ll = long long;
const ll N = 5e5 + 2;
ll a[N], block, ans[N], cnt = 0;
map < ll, ll > A;
struct Mo {
	ll lo, hi, ind;
};
bool cmp(Mo A, Mo B) {
	if ((A.lo)/block != (B.lo)/block)  return A.lo < B.lo;
	return A.hi < B.hi;
	
}
void Add(ll x) {
	if ( A[a[x]] == 2) cnt --;
	A[a[x]] ++;
	if ( A[a[x]] == 2) cnt ++;
	return ;
}
void Remove(ll x) {
	if ( A[a[x]] == 2) cnt --;
	A[a[x]] --;
	if ( A[a[x]] == 2) cnt ++;
	return ;
}
int main() {
	ll n, m, r, l,lo,hi, mx_x, y_val, i, j, t, q;

	cin >> n >> q;
	
	block = sqrtl(n);
	for (i = 1; i <= n; i ++){
		cin >> a[i];
	}
	
	vector < Mo > v;
	for (i = 1; i <= q; i ++) {
		cin >> l >> r;
		v.push_back({l, r, i});
	}
	sort(v.begin(), v.end(), cmp);
	lo = 1;
	hi = 0;
	
	for (i = 0; i < v.size(); i ++) {
		l = v[i].lo;
		r = v[i].hi;
		while (lo < l) {
			Remove(lo);
			lo ++;
		}
		while ( lo > l) {
			lo --;
			Add(lo);
		}
		while ( hi < r) {
			hi ++;
			Add(hi);
		}
		while ( hi > r) {
			Remove(hi);
			hi --;
		}
		ans[v[i].ind] = cnt;
	}
	for (i = 1; i <= q; i ++) {
		cout << ans[i] << "\n";
	}
	
	
}

• Subtask 1: 84 / 140