# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
642511 |
2022-09-19T17:27:49 Z |
red24 |
Izbori (COCI22_izbori) |
C++14 |
|
3000 ms |
21264 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>>
#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
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;
| ^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
316 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
316 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
121 ms |
400 KB |
Output is correct |
8 |
Correct |
2 ms |
212 KB |
Output is correct |
9 |
Correct |
4 ms |
468 KB |
Output is correct |
10 |
Correct |
5 ms |
524 KB |
Output is correct |
11 |
Correct |
4 ms |
468 KB |
Output is correct |
12 |
Correct |
4 ms |
468 KB |
Output is correct |
13 |
Correct |
4 ms |
524 KB |
Output is correct |
14 |
Correct |
4 ms |
468 KB |
Output is correct |
15 |
Correct |
5 ms |
468 KB |
Output is correct |
16 |
Correct |
4 ms |
468 KB |
Output is correct |
17 |
Correct |
1 ms |
456 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
128 ms |
13492 KB |
Output is correct |
2 |
Correct |
175 ms |
17260 KB |
Output is correct |
3 |
Correct |
99 ms |
10136 KB |
Output is correct |
4 |
Correct |
178 ms |
17988 KB |
Output is correct |
5 |
Correct |
188 ms |
18692 KB |
Output is correct |
6 |
Correct |
206 ms |
19828 KB |
Output is correct |
7 |
Correct |
201 ms |
19712 KB |
Output is correct |
8 |
Correct |
204 ms |
19736 KB |
Output is correct |
9 |
Correct |
204 ms |
19852 KB |
Output is correct |
10 |
Correct |
229 ms |
19744 KB |
Output is correct |
11 |
Correct |
68 ms |
19736 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
316 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
121 ms |
400 KB |
Output is correct |
8 |
Correct |
2 ms |
212 KB |
Output is correct |
9 |
Correct |
4 ms |
468 KB |
Output is correct |
10 |
Correct |
5 ms |
524 KB |
Output is correct |
11 |
Correct |
4 ms |
468 KB |
Output is correct |
12 |
Correct |
4 ms |
468 KB |
Output is correct |
13 |
Correct |
4 ms |
524 KB |
Output is correct |
14 |
Correct |
4 ms |
468 KB |
Output is correct |
15 |
Correct |
5 ms |
468 KB |
Output is correct |
16 |
Correct |
4 ms |
468 KB |
Output is correct |
17 |
Correct |
1 ms |
456 KB |
Output is correct |
18 |
Correct |
128 ms |
13492 KB |
Output is correct |
19 |
Correct |
175 ms |
17260 KB |
Output is correct |
20 |
Correct |
99 ms |
10136 KB |
Output is correct |
21 |
Correct |
178 ms |
17988 KB |
Output is correct |
22 |
Correct |
188 ms |
18692 KB |
Output is correct |
23 |
Correct |
206 ms |
19828 KB |
Output is correct |
24 |
Correct |
201 ms |
19712 KB |
Output is correct |
25 |
Correct |
204 ms |
19736 KB |
Output is correct |
26 |
Correct |
204 ms |
19852 KB |
Output is correct |
27 |
Correct |
229 ms |
19744 KB |
Output is correct |
28 |
Correct |
68 ms |
19736 KB |
Output is correct |
29 |
Correct |
79 ms |
21264 KB |
Output is correct |
30 |
Execution timed out |
3051 ms |
4396 KB |
Time limit exceeded |
31 |
Halted |
0 ms |
0 KB |
- |