oj.uz

Submission #707057

# Submission time Handle Problem Language Result Execution time Memory
707057 2023-03-08T11:09:17 Z Chal1shkan Izbori (COCI22_izbori) C++14
25 / 110
 350 ms 16688 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;
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 * 8];
 
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 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 3 ms 5076 KB Output is correct
5 Correct 3 ms 5076 KB Output is correct
6 Correct 3 ms 5076 KB Output is correct

Subtask #2
15.0 / 15.0

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

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 255 ms 14556 KB Output is correct
2 Correct 323 ms 16036 KB Output is correct
3 Correct 179 ms 11100 KB Output is correct
4 Correct 350 ms 16528 KB Output is correct
5 Correct 350 ms 16688 KB Output is correct
6 Incorrect 12 ms 8148 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 3 ms 5076 KB Output is correct
5 Correct 3 ms 5076 KB Output is correct
6 Correct 3 ms 5076 KB Output is correct
7 Correct 6 ms 5204 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 7 ms 5204 KB Output is correct
10 Correct 7 ms 5204 KB Output is correct
11 Correct 6 ms 5204 KB Output is correct
12 Correct 7 ms 5204 KB Output is correct
13 Correct 6 ms 5204 KB Output is correct
14 Correct 5 ms 5204 KB Output is correct
15 Correct 6 ms 5204 KB Output is correct
16 Correct 6 ms 5204 KB Output is correct
17 Correct 5 ms 5332 KB Output is correct
18 Correct 255 ms 14556 KB Output is correct
19 Correct 323 ms 16036 KB Output is correct
20 Correct 179 ms 11100 KB Output is correct
21 Correct 350 ms 16528 KB Output is correct
22 Correct 350 ms 16688 KB Output is correct
23 Incorrect 12 ms 8148 KB Output isn't correct
24 Halted 0 ms 0 KB -