제출 #895618

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
895618		vjudge1	Izbori (COCI22_izbori)	C++17	0 / 110	292 ms	31836 KiB

Main

#include <bits/stdc++.h>
#define pb push_back
#define pf push_front
using namespace std;
#define F first
#define S second
typedef long long ll;
#define pii pair <int, int>
#define pll pair <ll, ll>
typedef long double ld;
const ll N = 2 * 1e5 + 10;
const ll mod = 1e9 + 7;

ll um(ll a, ll b){
	return ((1LL * a * b) % mod + mod) % mod;
}
ll subr(ll a, ll b){
	return ((1LL * a - b) % mod + mod) % mod;
}
ll add(ll a, ll b){
	return ((1LL * a + b) % mod + mod) % mod;
}
ll binpow(ll x, ll step){
	ll res = 1LL;
	while(step){
		if(step & 1) res = um(res, x);
		x = um(x, x);
		step /= 2;
	}
	return res;
}
int arr[N], b[N], n;
vector <int> vec[N];
struct segtree {
	ll sz;
	vector <ll> tree, cnt, com;
	vector <bool> z;
	void cl(ll x, ll lx, ll rx){
		if(rx - lx == 1){
			if(z[x]) cnt[x] = com[x] = tree[x] = z[x] = 0;
			return;
		}
		if(z[x] == true){
			cnt[x] = com[x] = tree[x] = 0;
			z[2 * x + 1] = z[2 * x + 2] = true;
			z[x] = false;
		}
	}
	void prop(ll x, ll lx, ll rx){
		if(rx - lx == 1) return;
		ll mid = (lx + rx) / 2;
		cl(2 * x + 1, lx, mid);
		cl(2 * x + 2, mid, rx);
		
		com[2 * x + 1] += com[x];
		com[2 * x + 2] = com[2 * x + 2] + com[x] + cnt[x] * (rx - lx) / 2;
		cnt[2 * x + 1] += cnt[x];
		cnt[2 * x + 2] += cnt[x];
		cnt[x] = com[x] = tree[x] = 0;
		
		find(2 * x + 1, lx, mid);
		find(2 * x + 2, mid, rx);
	}
	void init(ll n){
		sz = 1;
		while(sz < n) sz *= 2;
		tree.assign(2 * sz - 1, 0LL);
		cnt.assign(2 * sz - 1, 0LL);
		com.assign(2 * sz - 1, 0LL);
		z.assign(2 * sz - 1, false);
	}
	void find(ll x, ll l, ll r){
		if(r - l == 1){
			tree[x] = com[x] + cnt[x];
		} else{
			tree[x] = com[x] * (r - l) + cnt[x] * ((r - l) * (r - l + 1) / 2LL);
			if(z[2 * x + 1] == false) tree[x] += tree[2 * x + 1];
			if(z[2 * x + 2] == false) tree[x] += tree[2 * x + 2];
		}
	}
	ll get(ll l, ll r, ll x, ll lx, ll rx){
		prop(x, lx, rx);
		if(lx >= r || l >= rx) return 0LL;
		if(l <= lx && rx <= r){
			find(x, lx, rx);
			return tree[x];
		}
		ll mid = (lx + rx) / 2;
		ll s1 = get(l, r, 2 * x + 1, lx, mid);
		ll s2 = get(l, r, 2 * x + 2, mid, rx);
		return s1 + s2;
	}
	ll get(ll l, ll r){
		return get(l, r, 0, 0, sz);
	}
	void upd(ll l, ll r, ll x, ll lx, ll rx){
		prop(x, lx, rx);
		if(l >= rx || lx >= r) return;
		if(l <= lx && rx <= r){
			com[x] += (lx - l);
			cnt[x]++;
			find(x, lx, rx);
			return;
		}
		ll mid = (lx + rx) / 2;
		upd(l, r, 2 * x + 1, lx, mid);
		upd(l, r, 2 * x + 2, mid, rx);
		tree[x] = tree[2 * x + 1] + tree[2 * x + 2];
	}
	void upd(ll l, ll r){
		upd(l, r, 0, 0, sz);
	}
	void upd2(ll l, ll r, ll s, ll x, ll lx, ll rx){
		prop(x, lx, rx);
		if(l >= rx || lx >= r) return;
		if(l <= lx && rx <= r){
			com[x] += s;
			find(x, lx, rx);
			return;
		}
		ll mid = (lx + rx) / 2;
		upd2(l, r, s, 2 * x + 1, lx, mid);
		upd2(l, r, s, 2 * x + 2, mid, rx);
		tree[x] = tree[2 * x + 1] + tree[2 * x + 2];
	}
	void upd2(ll l, ll s){
		upd2(l, sz, s, 0, 0, sz);
	}

};
int main() {
	ios::sync_with_stdio(false);
  	cin.tie(NULL);
  	cin >> n;
  	for(int i = 0; i < n; i++){
  		cin >> arr[i];
  		b[i] = arr[i];
  	}
  	sort(b, b + n);
  	int sz = unique(b, b + n) - b;
  	for(int i = 0; i < sz; i++){
  		vec[i].pb(-1);
  	}
  	for(int i = 0; i < n; i++){
  		arr[i] = lower_bound(b, b + sz, arr[i]) - b; 
  		vec[arr[i]].pb(i);
  	}
  	for(int i = 0; i < sz; i++){
  		vec[i].pb(n);
  	}
  	segtree obj;
  	obj.init(2 * n + 5);
  	ll ans = 0;
  	for(int i = 0, plus; i < sz; i++){
  		plus = 0;
  		for(int index = 0; index < (int)vec[i].size() - 1; index++){
  			int pref = plus * 2 - vec[i][index] - 1;
  			plus++;
			int from = pref - (vec[i][index + 1] - vec[i][index] - 1) + n, to = pref + 1 + n;
			ll local = obj.get(from, to);
			ans += local;
			obj.upd(from + 1, to);
			obj.upd2(to, to - from);
  		}
  		obj.z[0] = true;
  	}
  	cout << ans;
  return 0;
}

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