Submission #1270478

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270478		algoproclub	Izbori (COCI22_izbori)	C++20	25 / 110	3093 ms	10052 KiB

Main

// UUID: 8449edc8-1a1d-4764-af4d-301d2bcff899
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<int> t;
int si;
void upd(int x, int del)
{
	for(t[x += si] += del; x > 1; x >>= 1) t[x >> 1] = t[x] + t[x ^ 1];
}
int get(int l, int r)
{
	int ans = 0;
	for(l += si, r += si + 1; l < r; l >>= 1, r >>= 1)
	{
		if(l & 1) ans += t[l++];
		if(r & 1) ans += t[--r];
	}
	return ans;
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	si = 2 * n + 2;
	t.resize(2 * si);
	map<int, vector<int> > m;
	vector<int> a(n + 1);
	for(int i = 1; i <= n; i++)
	{
		int x;
		cin >> x;
		a[i] = x;
		m[x].push_back(i);
	}
	ll ans = 0;
	for(auto [val, v] : m)
	{
		vector<int> tem;
		set<int> s;
		s.insert(0);
		int z = 0;
		for(auto x : v) s.insert(x);
		for(auto x : v)
		{
			z = x + 1;
			while(s.count(z)) z++;
			if(z <= n)
			{
				s.insert(z);
			}
		}
		z = n + 1;
		for(int i = v.size() - 1; i >= 0; i--)
		{
			int x = v[i];
			z = x - 1;
			while(s.count(z)) z--;
			if(z > 0)
			{
				s.insert(z);
			}
		}
		int la = -1;
		int act = 0;
		for(auto x : s)
		{
			act -= (x - la - 1);
			if(x != 0)
			{
				if(a[x] == val) act++;
				else act--;
			}
			ans += get(0, act + n - 1);
			upd(act + n, 1);
			tem.push_back(act + n);
			la = x;
		}
		for(auto x : tem) upd(x, -1);
	}
	cout << ans << "\n";
}

• Subtask 1: 10 / 10
• Subtask 2: 15 / 15
• Subtask 3: 0 / 15
• Subtask 4: 0 / 70