Submission #1265931

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265931		canhnam357	Poklon (COCI17_poklon)	C++20	140 / 140	1054 ms	28640 KiB

poklon

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define mask(i) (1LL << (i))
const int block = 710;
const int MAXN = 5e5 + 5;
const int MAXA = 2e5 + 51;
struct query
{
	int l, r, id;
	void in(int id)
	{
		this->id = id;
		cin >> l >> r;
		l--, r--;
	}
	bool operator<(query o) const
	{
		return make_pair(l / block, r) < make_pair(o.l / block, o.r);
	}
};
int cnt[MAXN] = {}, f[MAXN];
int32_t main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, qu;
	cin >> n >> qu;
	vector<int> v(n);
	for (int& i : v) cin >> i;
	vector<pair<int, int>> ve;
	for (int i = 0; i < n; i++) ve.emplace_back(v[i], i);
	sort(ve.begin(), ve.end());
	v[ve[0].second] = 0;
	for (int i = 1; i < n; i++)
	{
		if (ve[i].first == ve[i - 1].first) v[ve[i].second] = v[ve[i - 1].second];
		else v[ve[i].second] = v[ve[i - 1].second] + 1;
	}
	vector<query> q(qu);
	for (int i = 0; i < qu; i++) q[i].in(i);
	sort(q.begin(), q.end());
	cnt[0] = n;
	auto add = [&](int pos)
	{
		cnt[f[v[pos]]]--;
		f[v[pos]]++;
		cnt[f[v[pos]]]++;
	};
	auto remove = [&](int pos)
	{
		cnt[f[v[pos]]]--;
		f[v[pos]]--;
		cnt[f[v[pos]]]++;
	};
	for (int i = 0; i < n; i++) add(i);
	vector<int> ans(qu);
	int l = 0, r = n - 1;
	for (auto x : q)
	{
		while (x.l > l) remove(l++);
		while (x.l < l) add(--l);
		while (x.r > r) add(++r);
		while (x.r < r) remove(r--);
		ans[x.id] = cnt[2];
	}
	for (int i : ans) cout << i << '\n';
	return 0;
}

• Subtask 1: 140 / 140