Submission #711036

#	Time	Username	Problem	Language	Result	Execution time	Memory
711036		LastRonin	Izbori (COCI22_izbori)	C++14	110 / 110	545 ms	31888 KiB

Main

#include <bits/stdc++.h>
#define speed ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define ll long long
#define pb push_back
#define mp make_pair
#define f first
#define pii pair<int, int>
#define pill pair<ll, ll>
#define s second
#define ld long double
using namespace std;

const ll N = 5e5 + 10;
const ll M = 5e6 + 10;
const ll mod = 1e4 + 7;
const ll big = 1e4;
const double eps = 1e-8;

ll t, n, k;
ll a[N];

//start : 9:59
vector<int> g[N], gg;
int kek[8 * N], sz = 0;
int cur_ver = 0;

struct seg {
	ll t[8 * N] = {0};
	ll c[8 * N] = {0};
	int d[8 * N] = {0};
	int ver[8 * N] = {0};
	void push(ll v, ll l, ll r) {
	    if(ver[v] != cur_ver)t[v] = 0, c[v] = 0, d[v] = 0, ver[v] = cur_ver;
		t[v] = t[v] + c[v] * (r - l + 1) + d[v] * (r - l + 1) * (r - l + 2) / 2ll;
		if(l != r) {
			int m = (l + r) >> 1ll;
		    if(ver[v * 2] != cur_ver)t[v * 2] = 0, c[v * 2] = 0, d[v * 2] = 0, ver[v * 2] = cur_ver;
		    if(ver[v * 2 + 1] != cur_ver)t[v * 2 + 1] = 0, c[v * 2 + 1] = 0, d[v * 2 + 1] = 0, ver[v * 2 + 1] = cur_ver;
			c[v * 2] += c[v];
			c[v * 2 + 1] += c[v] + d[v] * ((m + 1) - l);
			d[v * 2] += d[v];
			d[v * 2 + 1] += d[v];
		}
		c[v] = 0, d[v] = 0;
		return;
	}
	void upd1(ll l, ll r, ll v = 1, ll tl = 0, ll tr = 2 * n) {
		if(l > tr || tl > r)
			return;
		push(v, tl, tr);
		if(l <= tl && tr <= r) {
			c[v] += (tl - l);
			d[v] += 1;
			push(v, tl, tr);
			return;			
		}
		ll m = (tl + tr) >> 1ll;
		upd1(l , r, v * 2, tl, m);
		upd1(l , r, v * 2 + 1, m + 1, tr);
		t[v] = t[v * 2] + t[v * 2 + 1];
	}
	void upd2(ll l, ll r, ll z, ll v = 1, ll tl = 0, ll tr = 2 * n) {
		if(l > tr || tl > r)
			return;
		push(v, tl, tr);
		if(l <= tl && tr <= r) {
			c[v] += z;
			push(v, tl, tr);
			return;			
		}
		ll m = (tl + tr) >> 1ll;
		upd2(l , r, z, v * 2, tl, m);
		upd2(l , r, z, v * 2 + 1, m + 1, tr);
		t[v] = t[v * 2] + t[v * 2 + 1];
	}
	ll get(ll l, ll r, ll v = 1, ll tl = 0, ll tr = 2 * n) {
		if(l > tr || tl > r)
			return 0;
		push(v, tl, tr);
		if(l <= tl && tr <= r) {
			return t[v];			
		}
		ll m = (tl + tr) >> 1ll;
		return get(l , r, v * 2, tl, m) + get(l , r, v * 2 + 1, m + 1, tr);
	}
} rt;

int main() {
    speed;
	cin >> n;
	vector<int> szh;
	for(int i = 1; i <= n; i++) {
		cin >> a[i];
		szh.pb(a[i]);
	}
    sort(szh.begin(), szh.end());
	szh.erase(unique(szh.begin(), szh.end()), szh.end());
	for (int i = 1; i <= n; i++) {
	    a[i] = lower_bound(szh.begin(), szh.end(), a[i]) - szh.begin() + 1;
		g[a[i]].pb(i);
	}
	k = szh.size();
	ll ans = 0;
	for(int i = 1; i <= k; i++) {
		if(g[i].size() == 0)continue;
		cur_ver++;
		rt.upd1(-g[i][0] + 1 + n, n);
		rt.upd2(n + 1, 2 * n, n - (n - g[i][0]));		
		for(int j = 0; j < g[i].size(); j++) {
			int cnt = j + 1;
			int cur = g[i][j];
			int nxt = n + 1;
			if(g[i].size() != j + 1)
				nxt = g[i][j + 1];	
			ans = (ans + rt.get(2 * cnt - nxt + n, 2 * cnt - cur + n - 1));
			rt.upd1(2 * cnt - (nxt - 1) + n, 2 * cnt - cur + n);
			rt.upd2(2 * cnt - cur + n + 1, 2 * n, nxt - cur);
		}
	}
	cout << ans << "\n";
}
/*
6 1
3 1 5 3 7 5
4 6 4

*/

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:109:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |   for(int j = 0; j < g[i].size(); j++) {
      |                  ~~^~~~~~~~~~~~~
Main.cpp:113:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  113 |    if(g[i].size() != j + 1)
      |       ~~~~~~~~~~~~^~~~~~~~

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