oj.uz

Submission #707050

# Submission time Handle Problem Language Result Execution time Memory
707050 2023-03-08T11:01:57 Z Chal1shkan Izbori (COCI22_izbori) C++14
25 / 110
 411 ms 25132 KB 
# include <bits/stdc++.h>
 
# define pb push_back
# define ff first
# define ss second
# define nl "\n"
# define sz(x) ((int)(x).size())
# define deb(x) cerr << #x  << " = " << x << endl; 
# define pll pair <ll, ll>
 
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
 
const ll maxn = 2e5 + 25;
const ll inf = 2e9 + 0;
const ll mod = 1e9 + 123;
const ll dx[] = {-1, 1, 0, 0};
const ll dy[] = {0, 0, -1, 1};
 
using namespace std;
 
ll n, a[maxn];
ll b[maxn];
vector <ll> pos[maxn];
 
struct node
{
	ll sum1, sum2, upd, sz;	
} t[maxn * 4];
 
ll cnt (ll x)
{
	return x * (x + 1) / 2;
}

void push (ll v, ll tl, ll tr)
{
	if (t[v].upd && tl != tr)
	{
		ll tm = (tl + tr) >> 1;
		t[v * 2].sum1 += t[v].upd * (tm - tl + 1);
		t[v * 2 + 1].sum1 += t[v].upd * (tr - tm);
		
		t[v * 2].sum2 += t[v].upd * cnt(tm - tl + 1);
		t[v * 2 + 1].sum2 += t[v].upd * cnt(tr - tm);
		
		t[v * 2].upd += t[v].upd;
		t[v * 2 + 1].upd += t[v].upd;
		t[v].upd = 0;
	}
}
 
void update (ll l, ll r, ll x, ll v = 1, ll tl = 0, ll tr = n + n)
{
	push(v, tl, tr);
	if (tr < l || r < tl) return;
	if (l <= tl && tr <= r)
	{
		t[v].sum1 += x * (tr - tl + 1);
		t[v].sum2 += x * cnt(tr - tl + 1);
		t[v].upd += x;
		return;
	}
	ll tm = (tl + tr) >> 1;
	update(l, r, x, v * 2, tl, tm);
	update(l, r, x, v * 2 + 1, tm + 1, tr);
	t[v].sum1 = t[v * 2].sum1 + t[v * 2 + 1].sum1;
	t[v].sum2 = t[v * 2].sum1 * (tr - tm) + t[v * 2].sum2 + t[v * 2 + 1].sum2;
}
 
node get (ll l, ll r, ll v = 1, ll tl = 0, ll tr = n + n)
{
	push(v, tl, tr);
	if (tr < l || r < tl) return {0, 0, 0, 0};
	if (l <= tl && tr <= r) return {t[v].sum1, t[v].sum2, t[v].upd, tr - tl + 1};
	ll tm = (tl + tr) >> 1;
	node x = get(l, r, v * 2, tl, tm);
	node y = get(l, r, v * 2 + 1, tm + 1, tr);
	return {x.sum1 + y.sum1, x.sum1 * y.sz + x.sum2 + y.sum2, x.upd, x.sz + y.sz};
}
 
void out (ll v = 1, ll tl = 0, ll tr = n + n)
{
	push(v, tl, tr);
	cout << tl << ' ' << tr << ' ' << t[v].sum2 << nl;
	if (tl == tr)
	{
		return;
	}
	ll tm = (tl + tr) >> 1;
	out(v * 2, tl, tm);
	out(v * 2 + 1, tm + 1, tr);
}

ll query (ll l, ll r)
{
	ll x = get(0, l - 1).sum1;
	ll y = get(l, r - 1).sum2;
	return x * (r - l + 1) + y;
}

void clear (ll v = 1, ll tl = 0, ll tr = n + n)
{
	push(v, tl, tr);
	t[v].sum1 = t[v].sum2 = t[v].upd = 0;
	if (tl == tr)
	{
		return;
	}
	ll tm = (tl + tr) >> 1;
	clear(v * 2, tl, tm);
	clear(v * 2 + 1, tm + 1, tr);
}

void ma1n (/* SABR */)
{
	cin >> n;
	for (ll i = 1; i <= n; ++i)
	{
		cin >> a[i];
		b[i] = a[i];	
	}	
	sort(b + 1, b + 1 + n);
	set <ll> st;
	for (ll i = 1; i <= n; ++i)
	{
		a[i] = lower_bound(b + 1, b + 1 + n, a[i]) - b;
		st.insert(a[i]);
		pos[a[i]].pb(i);
	}
	ll ans = 0;
	for (ll x : st)
	{
		pos[x].pb(0);
		pos[x].pb(n + 1);
		sort(pos[x].begin(), pos[x].end());
		vector <pll> clr;
		ll cur = n;
		update(n, n, 1);
		clr.pb({n, n});
		for (ll i = 1; i < sz(pos[x]); ++i)
		{
			ll siz = pos[x][i] - pos[x][i - 1] - 1; 
			ans += query(cur - siz, cur - 1);
			update(cur - siz, cur - 1, 1);
			clr.pb({cur - siz, cur - 1});
			if (pos[x][i] != n + 1)
			{
				ans += get(0, cur - siz).sum1;
				update(cur - siz + 1, cur - siz + 1, 1);
				clr.pb({cur - siz + 1, cur - siz + 1});
			}
			cur = cur - siz + 1;	
		}
		for (pll p : clr)
		{
			update(p.ff, p.ss, -1);
		}
	}
	cout << ans;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
//  freopen("spainting.in", "r", stdin);
//  freopen("spainting.out", "w", stdout);
    int ttt = 1;
//  cin >> ttt;
    for (int test = 1; test <= ttt; ++test)
    {
//      cout << "Case " << test << ":" << ' ';
        ma1n();
    }
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 5032 KB Output is correct
4 Correct 4 ms 5084 KB Output is correct
5 Correct 3 ms 5076 KB Output is correct
6 Correct 3 ms 5040 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 5032 KB Output is correct
4 Correct 4 ms 5084 KB Output is correct
5 Correct 3 ms 5076 KB Output is correct
6 Correct 3 ms 5040 KB Output is correct
7 Correct 7 ms 5168 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 7 ms 5204 KB Output is correct
10 Correct 6 ms 5332 KB Output is correct
11 Correct 6 ms 5164 KB Output is correct
12 Correct 6 ms 5172 KB Output is correct
13 Correct 6 ms 5204 KB Output is correct
14 Correct 6 ms 5204 KB Output is correct
15 Correct 7 ms 5276 KB Output is correct
16 Correct 7 ms 5172 KB Output is correct
17 Correct 6 ms 5300 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 248 ms 14548 KB Output is correct
2 Correct 328 ms 16760 KB Output is correct
3 Correct 194 ms 11268 KB Output is correct
4 Correct 345 ms 16724 KB Output is correct
5 Correct 376 ms 17096 KB Output is correct
6 Correct 390 ms 17564 KB Output is correct
7 Correct 389 ms 17476 KB Output is correct
8 Correct 407 ms 17596 KB Output is correct
9 Correct 408 ms 17508 KB Output is correct
10 Correct 411 ms 17484 KB Output is correct
11 Incorrect 383 ms 25132 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 5032 KB Output is correct
4 Correct 4 ms 5084 KB Output is correct
5 Correct 3 ms 5076 KB Output is correct
6 Correct 3 ms 5040 KB Output is correct
7 Correct 7 ms 5168 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 7 ms 5204 KB Output is correct
10 Correct 6 ms 5332 KB Output is correct
11 Correct 6 ms 5164 KB Output is correct
12 Correct 6 ms 5172 KB Output is correct
13 Correct 6 ms 5204 KB Output is correct
14 Correct 6 ms 5204 KB Output is correct
15 Correct 7 ms 5276 KB Output is correct
16 Correct 7 ms 5172 KB Output is correct
17 Correct 6 ms 5300 KB Output is correct
18 Correct 248 ms 14548 KB Output is correct
19 Correct 328 ms 16760 KB Output is correct
20 Correct 194 ms 11268 KB Output is correct
21 Correct 345 ms 16724 KB Output is correct
22 Correct 376 ms 17096 KB Output is correct
23 Correct 390 ms 17564 KB Output is correct
24 Correct 389 ms 17476 KB Output is correct
25 Correct 407 ms 17596 KB Output is correct
26 Correct 408 ms 17508 KB Output is correct
27 Correct 411 ms 17484 KB Output is correct
28 Incorrect 383 ms 25132 KB Output isn't correct
29 Halted 0 ms 0 KB -