Submission #794914

#	Time	Username	Problem	Language	Result	Execution time	Memory
794914		79brue	Line Town (CCO23_day1problem3)	C++17	25 / 25	409 ms	35436 KiB

Main

#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++;
        reverse(vec.begin()+s, vec.begin()+e+1);
        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 (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:139:21: warning: unused variable 'tb' [-Wunused-variable]
  139 |                 int tb = (K+ta)%2; /// 이건 오른쪽에 붙은 개수의 홀짝성
      |                     ^~
Main.cpp:133:13: warning: unused variable 'L' [-Wunused-variable]
  133 |         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: 3 / 3
• Subtask 2: 3 / 3
• Subtask 3: 3 / 3
• Subtask 4: 4 / 4
• Subtask 5: 4 / 4
• Subtask 6: 3 / 3
• Subtask 7: 2 / 2
• Subtask 8: 3 / 3