Submission #642511

#	Time	Username	Problem	Language	Result	Execution time	Memory
642511		red24	Izbori (COCI22_izbori)	C++14	40 / 110	3051 ms	21264 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define vi vector<int> 
#define vvi vector<vector<int>>
#define pi pair<int, int>
#define ppi pair<pair<int, int>>
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define OK cout << "OK" << '\n'
#define qi queue<int>
#define sti stack<int>
#define si stack<int>
#define yes cout << "Yes" << '\n'
#define no cout << "No" << '\n'
#define pb push_back
#define eb emplace_back
#define vpi vector<pair<int, int>>
#define ll long long
#define nl cout << '\n'
#define ok cout << "OK" << '\n'
#define mp make_pair
#define repr(i, b, a) for (int i = b; i >= a; i--)
#define veb vector<bool>
#define vveb vector<vector<bool>>
#define int long long

void printvec(vi v)
{
	rep(i, 1, v.size()-1) cout << v[i] << ' '; nl;
}

long long binpow(long long a, long long b) {
    long long res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}

long long binpowmod(long long a, long long b, long long m) {
    a %= m;
    long long res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}

void compress(vi &a)
{
	int n = a.size() - 1;
	vpi pairs(n+1);
	rep(i, 1, n) pairs[i] = mp(a[i],i);
	sort(pairs.begin(), pairs.end());

	int c = 1;
	rep(i, 1, n)
	{
		if (pairs[i].first > pairs[i-1].first && i > 1) c++;
		a[pairs[i].second] = c;
	}
	return;
}

// PROGRAM
const int MOD = (int)1e9 + 7;

void build(int v, int l, int r, vi &a, vi &seg, vi &seg_val)
{
	// cout << v << "  " << l << ' ' << r << endl;
	if (l == r)
	{
		return;
	}

	int mid = (l + r)/2;

	build(v<<1, l, mid, a, seg, seg_val);
	build((v<<1) + 1, mid + 1, r, a, seg, seg_val);

	vi vec;
	rep(i, l - 1, mid - 1) vec.pb(a[i]);
	sort(vec.begin(), vec.end());

	int curr_res = 0;
	rep(i, mid + 1, r)
	{
		auto it = lower_bound(vec.begin(), vec.end(), a[i]);
		curr_res += it - vec.begin();
	}
	seg_val[v]  = curr_res + seg_val[v<<1] + seg_val[(v<<1)+1];
}

void solve()
{
	// CHECK IF PROGRAM HAS TESTCASES
	int n; cin >> n;
	vi a(n+1);
	rep(i, 1, n) cin >> a[i];
	compress(a);

	int mx = -1;
	rep(i, 1, n) mx = max(mx, a[i]);

	int res = 0;

	rep(c, 1, mx)
	{
		vi b(n+1);
		rep(i, 1, n) 
		{
			if (a[i] == c) b[i] = 1;
			else b[i] = 0;
		}
		vi pf(n+1);
		rep(i, 1, n) pf[i] = pf[i-1] + b[i];
		rep(i, 1, n) b[i] = 2*pf[i] - i;

		vi seg_val(4*n+10);
		vi seg(4*n+10);

		build(1, 1, n, b, seg, seg_val);

		res += seg_val[1] + pf[n];
	}

	cout << res << '\n';
}

int32_t main()
{
	//fastio
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	//fastio
	
	int T = 1;
	//cin >> T;
	while (T--) solve();
}

Compilation message (stderr)

Main.cpp: In function 'void printvec(std::vector<long long int>)':
Main.cpp:8:40: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 | #define rep(i, a, b) for (int i = a; i <= b; i++)
......
   29 |  rep(i, 1, v.size()-1) cout << v[i] << ' '; nl;
      |      ~~~~~~~~~~~~~~~~                   
Main.cpp:29:2: note: in expansion of macro 'rep'
   29 |  rep(i, 1, v.size()-1) cout << v[i] << ' '; nl;
      |  ^~~

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