Submission #1326641

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326641		gohchingjayk	Poklon (COCI17_poklon)	C++20	140 / 140	376 ms	45648 KiB

poklon

#pragma GCC optimize("O3,inline")
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define int ll

using ii = pair<int, int>;
using iii = pair<int, ii>;

constexpr int MAXN = 500'000 + 5;
constexpr int INF = 1e18 + 5;

int FST[MAXN * 2 + 5];
void point_set(int p, int v) {
	for (FST[p += MAXN] = v; p > 1; p >>= 1) FST[p >> 1] = FST[p] + FST[p ^ 1];
}

int query(int l, int r) {
	int ans = 0;
	for (l += MAXN, r += MAXN + 1; l < r; l>>=1, r>>=1) {
		if (l & 1) ans += FST[l++];
		if (r & 1) ans += FST[--r];
	}
	return ans;
}

vector<ii> queriesEndingAt[MAXN];
int A[MAXN];
map<int, int> last;
int prv[MAXN];
int ans[MAXN];

signed main() {
	ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

	int N, Q; cin >> N >> Q;
	for (int i = 1; i <= N; ++i) cin >> A[i];

	for (int i = 0; i < Q; ++i) {
		int l, r; cin >> l >> r;
		queriesEndingAt[r].emplace_back(l, i);
	}
	
	for (int i = 1; i <= N; ++i) {
		prv[i] = last[A[i]];
		last[A[i]] = i;
	}

	// when we reach i: point_set prv[i] = 1, prv[prv[i]] = -1, prv[prv[prv[i]]] = 0
	for (int i = 1; i <= N; ++i) {
		point_set(prv[i], 1);
		point_set(prv[prv[i]], -1);
		point_set(prv[prv[prv[i]]], 0);
		
		for (auto [l, q] : queriesEndingAt[i]) {
			ans[q] = query(l, i);
		}
	}
	
	for (int i = 0; i < Q; ++i) cout << ans[i] << '\n';
}

• Subtask 1: 140 / 140