| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 792713 |
2023-07-25T08:13:56 Z |
박상훈(#10052) |
Line Town (CCO23_day1problem3) |
C++17 |
|
1 ms |
340 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr ll INF = 4e18;
struct Seg{
int tree[2002000];
int sz;
void init(int n){
sz = n;
fill(tree, tree+sz*2, 0);
}
void update(int p, ll x){
p += sz;
tree[p] = x;
for (p>>=1;p;p>>=1) tree[p] = tree[p<<1] + tree[p<<1|1];
}
int query(int l, int r){
++r;
int ret = 0;
for (l+=sz, r+=sz;l<r;l>>=1, r>>=1){
if (l&1) ret += tree[l++];
if (r&1) ret += tree[--r];
}
return ret;
}
}tree;
int a[500500], I[500500];
ll dp[2][500500];
int cnt2[2], col_b[500500], col_f[500500], col[500500];
int f(int s, int e, int val){
if ((e-s)%2 == 0) return val;
return -val;
}
int main(){
int n;
scanf("%d", &n);
for (int i=1;i<=n;i++) scanf("%d", a+i);
for (int i=1;i<=n;i++){
if (f(i, 0, a[i]) == -abs(a[i])) col[i] = 0;
else col[i] = 1;
}
for (int i=1;i<=n;i++) I[i] = i;
sort(I+1, I+n+1, [&](int i, int j){return abs(a[i]) < abs(a[j]);});
tree.init(n+1);
for (int i=1,r;i<=n;i=r+1){
r = i;
while(r+1<=n && abs(a[I[i]]) == abs(a[I[r+1]])) r++;
for (int t=i;t<=r;t++) tree.update(I[t], 1);
for (int z=0;z<2;z++){
int len = r;
int cnt = r-i+1;
dp[z][len] = INF;
for (int s=0;s<2;s++){
// init here
vector<int> V[2];
cnt2[0] = cnt2[1] = 0;
for (int t=i;t<=r;t++){
int idx = I[t];
V[col[idx]].push_back(tree.query(1, idx));
}
col_f[0] = z^1;
for (int i=1;i<=cnt;i++){
col_f[i] = col_f[i-1] ^ 1;
if (i<=s) cnt2[col_f[i]]++;
}
col_b[len] = ((z+len-1)&1) ^ 1;
if (len >= len-(cnt-s)+1) cnt2[col_b[len]]++;
for (int i=len-1;i>=len-(cnt-s)+1;i--){
col_b[i] = col_b[i+1] ^ 1;
cnt2[col_b[i]]++;
}
// printf("\ni = %d, z = %d, s = %d -> cnt = (%d, %d) / sz = (%d, %d)\n", i, z, s, cnt2[0], cnt2[1], (int)V[0].size(), (int)V[1].size());
if (cnt2[0]!=(int)V[0].size() || cnt2[1]!=(int)V[1].size()) continue;
int cp[2] = {col_f[s+1], col_f[s+2]};
int cq[2] = {col_b[len - (cnt-s) + 1], col_b[len - (cnt-s) + 2]};
int pp[2] = {0, 0}, pq[2] = {0, 0};
if (s==1) {
pp[1] = 1;
if (cq[0]==z) pq[0]++;
else pq[1]++;
}
ll cst = 0;
cnt2[0] = cnt2[1] = 0;
for (int i=1;i<=s;i++){
cst += abs(V[col_f[i]][cnt2[col_f[i]]] - i);
cnt2[col_f[i]]++;
}
for (int i=len-(cnt-s)+1;i<=len;i++){
cst += abs(V[col_b[i]][cnt2[col_b[i]]] - i);
cnt2[col_b[i]]++;
}
int nz = z ^ s;
// printf("i = %d, z = %d, s = %d -> cst = %lld\n", i, z, s, cst);
for (int k=s;k<=cnt;k+=2){
dp[z][len] = min(dp[z][len], dp[nz][i-1] + cst/2);
if (k+2 > cnt) break;
cst -= abs(V[cq[0]][pq[0]] - (len - (cnt-k) + 1));
cst -= abs(V[cq[1]][pq[1]] - (len - (cnt-k) + 2));
pq[0]++, pq[1]++;
cst += abs(V[cp[0]][pp[0]] - (k+1));
cst += abs(V[cp[1]][pp[1]] - (k+2));
pp[0]++, pp[1]++;
}
}
// printf("%d %d -> %lld\n", i, z, dp[z][i]);
}
// assert(i==r);
// // abs distinct
// int pos = I[i];
// for (int z=0;z<2;z++){
// dp[z][i] = INF;
// if (f(pos, z, a[pos]) == -abs(a[pos])) dp[z][i] = min(dp[z][i], dp[z^1][i-1] + tree.query(1, pos-1));
// if (f(pos, z+i-1, a[pos]) == abs(a[pos])) dp[z][i] = min(dp[z][i], dp[z][i-1] + tree.query(pos+1, n));
// if (i==1) dp[z][i] = 0;
// // printf("%d %d -> %lld\n", z, i, dp[z][i]);
// }
// tree.update(pos, 1);
}
if (dp[1][n]==INF) printf("-1\n");
else printf("%lld\n", dp[1][n]);
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:47:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
47 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
Main.cpp:48:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
48 | for (int i=1;i<=n;i++) scanf("%d", a+i);
| ~~~~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
