제출 #1284066

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1284066		trandangquang	Line Town (CCO23_day1problem3)	C++20	25 / 25	494 ms	38416 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define foru(i,a,b) for(int i=(a); i<=(b); ++i)
#define ford(i,a,b) for(int i=(a); i>=(b); --i)
#define sz(a) (int)(a).size()
#define ll long long
#define _ << " " <<

template <class X, class Y> bool mini(X &x, Y y){return x>y?x=y,true:false;}

const int N=5e5+5;

int numTown,town[N];
void init(){
    cin>>numTown;
    foru(i,1,numTown) cin>>town[i];
}

vector<int> rar;
void compress(){
    foru(i,1,numTown) rar.emplace_back(abs(town[i]));
    rar.emplace_back(0);

    sort(rar.begin(),rar.end());
    rar.erase(unique(rar.begin(),rar.end()),rar.end());

    foru(i,1,numTown){
        int tmp=town[i]<0 ? -1 : 1;
        town[i]=tmp * (lower_bound(rar.begin(),rar.end(),abs(town[i]))-rar.begin());
    }
}

struct FenwickTree{
    int f[N],tot;

    FenwickTree(){
        tot=0;
        memset(f,0,sizeof(f));
    }

    void upd(int id, int val){
        tot+=val;
        for(++id; id<N; id+=id&-id) f[id]+=val;
    }
    int getSmaller(int id){ /// or equal
        int res=0;
        for(++id; id>0; id-=id&-id) res+=f[id];
        return res;
    }
    int getLarger(int id){
        return tot-getSmaller(id);
    }
} fw1,fw2;

int smallLeft[N],smallRight[N];
void countSmall(){
    foru(i,1,numTown){
        fw1.upd(abs(town[i]),1);
        smallLeft[i]=fw1.getSmaller(abs(town[i])-1);
    }
    foru(i,1,numTown) fw1.upd(abs(town[i]),-1);

    ford(i,numTown,1){
        fw1.upd(abs(town[i]),1);
        smallRight[i]=fw1.getSmaller(abs(town[i])-1);
    }
    foru(i,1,numTown) fw1.upd(abs(town[i]),-1);
}

ll lastDP[2], DP[2], ansLeft[N], ansRight[N];
int id[N], signAtEven[N], useLeft[N][2], useRight[N][2];

void countAnswer(){
    iota(id+1, id+1+numTown, 1);
    sort(id+1, id+1+numTown, [](int x, int y){return abs(town[x]) > abs(town[y]);});

    foru(i,1,numTown){
        signAtEven[i]=(town[i]>0 && i%2==0) || (town[i]<0 && i%2==1);
        /// signAtEven[i] = 1 -> > 0
    }

    DP[0]=0; DP[1]=1e18;
    foru(i,1,numTown){
        int l=i, r=i;
        while(r<=numTown && abs(town[id[r]]) == abs(town[id[l]])) ++r;
        --r;

        if(abs(town[id[r]]) == 0){
            break;
        }

        vector<int> sign[2], updated;
        foru(j,l,r) sign[signAtEven[id[j]]].emplace_back(id[j]);
        foru(j,0,1) sort(sign[j].begin(),sign[j].end());

        lastDP[0]=DP[0], lastDP[1]=DP[1];
        DP[0]=DP[1]=1e18;

        foru(leftP,0,1){
            int rightP=(numTown+i+leftP)&1;

            useLeft[0][0]=useLeft[0][1]=ansLeft[0]=0;
            foru(j,1,r-l+1){
                useLeft[j][0]=useLeft[j-1][0];
                useLeft[j][1]=useLeft[j-1][1];

                int curUse=(leftP+j)&1;
                useLeft[j][curUse]++;

                if(useLeft[j][0]>sz(sign[0]) || useLeft[j][1] > sz(sign[1])){
                    ansLeft[j] = 1e18;
                } else{
                    ansLeft[j]=ansLeft[j-1];
                    int pos=sign[curUse][useLeft[j][curUse]-1];
                    ansLeft[j]+=fw1.getLarger(pos)+smallLeft[pos];
                    fw1.upd(pos, 1);
                    updated.emplace_back(pos);
                }
            }
            for(int p:updated) fw1.upd(p, -1);
            updated.clear();

            useRight[r-l+2][0]=useRight[r-l+2][1]=ansRight[r-l+2]=0;
            ford(j,r-l+1,1){
                useRight[j][0]=useRight[j+1][0];
                useRight[j][1]=useRight[j+1][1];

                int curUse=(rightP+(r-l+1-j))&1;
                useRight[j][curUse]++;

                if(useRight[j][0]>sz(sign[0]) || useRight[j][1] > sz(sign[1])){
                    ansRight[j] = 1e18;
                } else{
                    ansRight[j]=ansRight[j+1];
                    int pos=sign[curUse][sz(sign[curUse])-useRight[j][curUse]];
                    ansRight[j]+=fw2.getSmaller(pos)+smallRight[pos];
                    fw2.upd(pos, 1);
                    updated.emplace_back(pos);
                }
            }
            for(int p:updated) fw2.upd(p, -1);
            updated.clear();

            foru(j,0,1){
                for(int p:sign[j]) fw2.upd(p,1);
            }

            ll cur=0;
            foru(j,0,r-l+1){
                if(j>=1){
                    int curUse=(leftP+j)&1;
                    if(useLeft[j][curUse] <= sz(sign[curUse])){
                        int pos = sign[curUse][useLeft[j][curUse]-1];

                        cur -= fw1.getLarger(pos);
                        fw2.upd(pos, -1);

                        cur += fw2.getSmaller(pos);
                        fw1.upd(pos, 1);

                        updated.emplace_back(pos);
                    }
                }
                if(useLeft[j][0]+useRight[j+1][0]==sz(sign[0]) && useLeft[j][1]+useRight[j+1][1]==sz(sign[1])){
                    ///ansLeft[j], ansRight[j+1]
                    mini(DP[(leftP+j)&1], lastDP[leftP] + ansLeft[j]+ansRight[j+1]+cur);
                }
            }

            for(int p:updated){
                fw1.upd(p, -1);
                fw2.upd(p, 1);
            }
            updated.clear();

            foru(j,0,1){
                for(int p:sign[j]) fw2.upd(p,-1);
            }
        }
        i=r;
    }
    cout<<((min(DP[0],DP[1])==(ll)1e18) ? -1 : min(DP[0],DP[1]))<<'\n';
}

void solve(){
    compress();
    countSmall();
    countAnswer();
}

int main(){
    #ifdef doramii
        freopen("test.inp","r",stdin);
        freopen("test.out","w",stdout);
    #endif // doramii

    cin.tie(0)->sync_with_stdio(0);

    init();
    solve();
}

• 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