oj.uz

답안 #642489

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
642489 2022-09-19T15:07:15 Z red24 Izbori (COCI22_izbori) C++14
0 / 110
 176 ms 45680 KB 
#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>>

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;
const int MX = 2e5 + 100;

vi seg[MX*4];
vi a(MX);
vi val(MX);
vi seg_ans(MX*4);
vi true_a(MX);

void build(int v, int l, int r)
{
	if (l == r)
	{
		seg[v].pb(a[l]);
		return;
	}

	int mid = (l + r)>>1;

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

	int curr_res = 0;

	vector<int> nw;
	rep(i, l-1, mid-1) nw.pb(a[i]);
	sort(nw.begin(), nw.end());

	for (auto x : seg[(v<<1) + 1])
	{
		auto it = lower_bound(nw.begin(), nw.end(), x);
		curr_res += it - nw.begin();
		//if (x > val[l-1]) curr_res++;
	}
	seg_ans[v] = curr_res + seg_ans[v<<1] + seg_ans[(v<<1)+1];

	//cout << v << ' ' << seg_ans[v] << '\n';

	while (!seg[v<<1].empty() || !seg[(v<<1) + 1].empty())
	{
		if (seg[v<<1].empty())
		{
			while (!seg[(v<<1) + 1].empty()) 
			{
				seg[v].pb(seg[(v<<1) + 1].back());
				seg[(v<<1) + 1].pop_back();
			}
			continue;
		}

		if (seg[(v<<1) + 1].empty())
		{
			while (!seg[v<<1].empty())
			{
				seg[v].pb(seg[v<<1].back());
				seg[v<<1].pop_back();
			}
			continue;
		}

		if (seg[v<<1].back() > seg[(v<<1) + 1].back())
		{
			seg[v].pb(seg[v<<1].back());
			seg[v<<1].pop_back();
		}

		else
		{
			seg[v].pb(seg[(v<<1) + 1].back());
			seg[(v<<1) + 1].pop_back();
		}
	}

	reverse(seg[v].begin(), seg[v].end());
}

void solve()
{
	// CHECK IF PROGRAM HAS TESTCASES
	int n; cin >> n;
	rep(i, 1, n) cin >> a[i];
	rep(i, 1, n) a[i] = a[i]%2;
	rep(i, 1, n) true_a[i] = a[i];

	vi pf(n+1);
	rep(i, 1, n) pf[i] = pf[i-1] + a[i];

	rep(i, 1, n) val[i] = 2*pf[i] - i;
	rep(i, 1, n) a[i] = val[i];

	build(1, 1, n);

	//rep(i, 1, 4*n) cout << seg_ans[i] << ' ';
	int res = 0;
	res += seg_ans[1] + pf[n];
	seg[1].clear();

	rep(i, 1, n) a[i] = (true_a[i]+1)%2;
	rep(i, 1, n) pf[i] = pf[i-1] + a[i];

	rep(i, 1, n) val[i] = 2*pf[i] - i;
	rep(i, 1, n) a[i] = val[i];

	build(1, 1, n);
	cout << seg_ans[1] + pf[n] + res;
}

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

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

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 15 ms 24532 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 15 ms 24532 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 176 ms 45680 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 15 ms 24532 KB Output isn't correct
2 Halted 0 ms 0 KB -