제출 #1195492

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1195492		lopkus	Poklon (COCI17_poklon)	C++20	140 / 140	957 ms	11184 KiB

poklon

#include<bits/stdc++.h>

using namespace std;
using ll = int;
const ll N = 5e5 + 2;
ll a[N], block, ans[N], cnt = 0;
ll A[N];
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() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	ll n, m, r,s,  l,lo,hi, mx_x, y_val, i, j, t, q;

	cin >> n >> q;
	
	block = sqrtl(n);
	map < ll, ll > mp_1, mp_2;
	for (i = 1; i <= n; i ++){
		cin >> a[i];
		mp_1[a[i]] ++;
	}
	s = 0;
	for ( auto R : mp_1) {
		mp_2[R.first] = s;
		s ++;
	}
	for (i = 1; i <= n; i ++) a[i] = mp_2[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: 140 / 140