Submission #818107

#	Time	Username	Problem	Language	Result	Execution time	Memory
818107		vjudge1	Poklon (COCI17_poklon)	C++17	140 / 140	301 ms	32784 KiB

poklon

#include <bits/stdc++.h> 
#define fi first 
#define se second
#define mp make_pair
#define getbit(x, i) (((x) >> (i)) & 1)
#define all(x) x.begin(), x.end()
#define TASK ""
 
using namespace std;
 
template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
	if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
	if (a < b) {a = b; return true;} return false;
}
 
const long long inf = 1e18;
const int mod = 1e9 + 7;
const int N = 5e5 + 7;

int n, q;
int a[N], ans[N], last1[N], last2[N], bit[N];
vector <int> value;
vector <pair <int, int>> queries[N];

struct FenwickTree {
	void update(int i, int value) {
		for (; i <= n; i += i & -i) bit[i] += value;
	}

	int get(int i) {
		int res = 0;
		for (; i; i -= i & -i) res += bit[i];
		return res;
	}

	int query(int l, int r) {
		return get(r) - get(l - 1);
	}
} ft;

void add(int index, int value) {
	if (last2[index] != 0) {
		ft.update(last2[index], value);
		if (last2[last2[index]] != 0) {
			ft.update(last2[last2[index]], -value);
		}
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> q;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
		value.emplace_back(a[i]);
	}

	sort(all(value));
	value.erase(unique(all(value)), value.end());

	for (int i = 1; i <= n; ++i) a[i] = lower_bound(all(value), a[i]) - value.begin() + 1;
 
	for (int i = 1; i <= q; ++i) {
		int l, r; cin >> l >> r;
		queries[l].emplace_back(r, i);
	}

	for (int i = n; i >= 1; --i) {
		if (last1[a[i]]) add(last1[a[i]], -1);
		last2[i] = last1[a[i]];
		last1[a[i]] = i;
		add(i, 1);

		for (auto [r, idx] : queries[i]) {
			ans[idx] = ft.query(i, r);
		}
	}

	for (int i = 1; i <= q; ++i) cout << ans[i] << ' ';
}

• Subtask 1: 140 / 140