| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 642489 |
2022-09-19T15:07:15 Z |
red24 |
Izbori (COCI22_izbori) |
C++14 |
|
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;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
24532 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
24532 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
176 ms |
45680 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
24532 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
