oj.uz

Submission #794909

# Submission time Handle Problem Language Result Execution time Memory
794909 2023-07-27T03:03:37 Z 79brue Line Town (CCO23_day1problem3) C++17
7 / 25
 331 ms 26084 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const ll INF = 1e18;

struct Fenwick{
    int n;
    int tree[500002];

    void init(int _n){
        n = _n;
        for(int i=1; i<=n; i++) tree[i] = 0;
    }

    void add(int x, int y){
        while(x<=n){
            tree[x] += y;
            x+=x&-x;
        }
    }

    int sum(int x){
        int ret = 0;
        while(x){
            ret += tree[x];
            x-=x&-x;
        }
        return ret;
    }

    int sum(int l, int r){
        if(l>r) return 0;
        return sum(r) - sum(l-1);
    }
} tree, treeL, treeR;

int n;
ll arr[500002];
ll DP[2][2];
ll ld[500002], rd[500002];

void solve();

int main(){
    scanf("%d", &n);
    for(int i=1; i<=n; i++){
        scanf("%lld", &arr[i]);
        if(i%2==0) arr[i] = -arr[i];
    }
    solve();
}

bool impossible(int start0, int start1, int len0, int len1, int cnt0, int cnt1){
    int c0 = 0, c1 = 0;
    c0 += (len0 % 2 && start0 == 0) ? (len0 + 1) / 2 : len0 / 2;
    c1 += (len0 % 2 && start0 == 1) ? (len0 + 1) / 2 : len0 / 2;
    c0 += (len1 % 2 && start1 == 0) ? (len1 + 1) / 2 : len1 / 2;
    c1 += (len1 % 2 && start1 == 1) ? (len1 + 1) / 2 : len1 / 2;
    if(c0 == cnt0 && c1 == cnt1) return false;
    return true;
}

ll inversion = 0;

void addSetLeft(int x){
    inversion += ld[x];
    inversion += treeL.sum(x+1, n);
    inversion += treeR.sum(1, x-1);
    treeL.add(x, 1);
}

void addSetRight(int x){
    inversion += rd[x];
    inversion += treeR.sum(1, x-1);
    inversion += treeL.sum(x+1, n);
    treeR.add(x, 1);
}

void delSetLeft(int x){
    treeL.add(x, -1);
    inversion -= treeR.sum(1, x-1);
    inversion -= treeL.sum(x+1, n);
    inversion -= ld[x];
}

void delSetRight(int x){
    treeR.add(x, -1);
    inversion -= treeL.sum(x+1, n);
    inversion -= treeR.sum(1, x-1);
    inversion -= rd[x];
}

void solve(){
    vector<pair<ll, int> > vec;
    for(int i=1; i<=n; i++) vec.push_back(make_pair(abs(arr[i]), i));
    sort(vec.rbegin(), vec.rend());

    tree.init(n);
    treeL.init(n);
    treeR.init(n);
    for(int i=1; i<=n; i++) tree.add(i, 1);

    /// 부호 관련
    /// 부호는 -가 0, +가 1
    for(int a=0; a<4; a++) DP[(a>>1)&1][a&1] = INF;
    DP[0][0] = 0;

    int usedCnt = 0; /// 지금까지 양쪽으로 보낸 개수
    for(int s=0; s<n; s++){
        if(vec[s].first == 0) break;
        int e = s;
        while(e+1<n && vec[s].first == vec[e+1].first) e++;
        vector<ll> pos[2];
        vector<ll> rpos[2];

        for(int i=s; i<=e; i++) tree.add(vec[i].second, -1);

        for(int i=s; i<=e; i++){
            int x = vec[i].second;
            ld[x] = tree.sum(1, x), rd[x] = tree.sum(x, n);
            if(arr[x] < 0) pos[0].push_back(x); /// 일단 인덱스를 입력함
            else           pos[1].push_back(x); /// 여기도 인덱스를 입력함
        }

        rpos[0] = pos[0];
        rpos[1] = pos[1];
        reverse(rpos[0].begin(), rpos[0].end());
        reverse(rpos[1].begin(), rpos[1].end());

        int L = tree.sum(1, n); /// 현재 수를 제외한 켜져 있는 남은 수의 개수
        int K = (int)pos[0].size() + (int)pos[1].size(); /// 현재 보고 있는 수의 개수

        for(int js=0; js<2; js++){ /// 왼쪽 요구사항 -> 왼쪽은 무엇으로 시작해야 하는가?
            int je = (n%2) ^ ((usedCnt - js) & 1); /// 오른쪽 요구사항 -> 오른쪽은 무엇으로 시작해야 하는가?
            for(int ta=0; ta<2; ta++){ /// 왼쪽에 붙은 개수의 홀짝성을 고정
                int tb = (K+ta)%2; /// 이건 오른쪽에 붙은 개수의 홀짝성
                if(impossible(js, je, ta, K-ta, (int)pos[0].size(), (int)pos[1].size())) continue; /// 홀짝성이 안 맞음

                int l = ta, r = K-ta;
                inversion = 0;
                for(int i=1; i<=l; i++){
                    if(i%2 == 1) addSetLeft(pos[js][i/2]);
                    else         addSetLeft(pos[!js][(i-1)/2]);
                }
                for(int i=1; i<=r; i++){
                    if(i%2 == 1) addSetRight(rpos[je][i/2]);
                    else         addSetRight(rpos[!je][(i-1)/2]);
                }
                DP[1][(js+ta)&1] = min(DP[1][(js+ta)&1], DP[0][js] + inversion);

                while(r>=2){
                    for(int c=0; c<2; c++){
                        if(r%2==1) delSetRight(rpos[je][r/2]);
                        else       delSetRight(rpos[!je][(r-1)/2]);
                        r--, ++l;
                        if(l%2==1) addSetLeft(pos[js][l/2]);
                        else       addSetLeft(pos[!js][(l-1)/2]);
                    }
                    DP[1][(js+ta)&1] = min(DP[1][(js+ta)&1], DP[0][js] + inversion);
                }

                while(l){
                    if(l%2==1) delSetLeft(pos[js][l/2]);
                    else       delSetLeft(pos[!js][(l-1)/2]);
                    l--;
                }
                while(r){
                    if(r%2==1) delSetRight(rpos[je][r/2]);
                    else       delSetRight(rpos[!je][(r-1)/2]);
                    r--;
                }
            }
        }

        s = e;
        for(int a=0; a<2; a++) DP[0][a] = DP[1][a], DP[1][a] = INF;
        usedCnt += K;
    }

    ll ans = min(DP[0][0], DP[0][1]);
    printf("%lld", ans == INF ? -1 : ans);
}

Compilation message

Main.cpp: In function 'void solve()':
Main.cpp:138:21: warning: unused variable 'tb' [-Wunused-variable]
  138 |                 int tb = (K+ta)%2; /// 이건 오른쪽에 붙은 개수의 홀짝성
      |                     ^~
Main.cpp:132:13: warning: unused variable 'L' [-Wunused-variable]
  132 |         int L = tree.sum(1, n); /// 현재 수를 제외한 켜져 있는 남은 수의 개수
      |             ^
Main.cpp: In function 'int main()':
Main.cpp:47:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
Main.cpp:49:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |         scanf("%lld", &arr[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
4.0 / 4.0

# 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 1 ms 464 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 484 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 1 ms 468 KB Output is correct

Subtask #6
3.0 / 3.0

# 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 1 ms 464 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 484 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 195 ms 25964 KB Output is correct
15 Correct 311 ms 26048 KB Output is correct
16 Correct 307 ms 25932 KB Output is correct
17 Correct 322 ms 25892 KB Output is correct
18 Correct 306 ms 25924 KB Output is correct
19 Correct 331 ms 25968 KB Output is correct
20 Correct 0 ms 340 KB Output is correct
21 Correct 0 ms 340 KB Output is correct
22 Correct 230 ms 26048 KB Output is correct
23 Correct 232 ms 26032 KB Output is correct
24 Correct 187 ms 26084 KB Output is correct

Subtask #7
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -