Submission #1284048

#	Time	Username	Problem	Language	Result	Execution time	Memory
1284048		trandangquang	Line Town (CCO23_day1problem3)	C++20	0 / 25	1 ms	572 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;
    vector<pair<int, int>> history;

    void upd(int id, int val){
        history.emplace_back(id,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);
    }
    void reset(){
        for(auto [id,val]:history) upd(id,-val);
        history.clear();
    }
} 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);
    }
    fw1.reset();

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

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;

        vector<int> sign[2];
        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);
                }
            }
            fw1.reset();

            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);
                }
            }

            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);
                    }
                }
                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);
                }
            }
            fw1.reset(); fw2.reset();
        }
        i=r;
    }

    cout<<((min(DP[0],DP[1])==(ll)1e18)?-1:min(DP[0],DP[1]))<<'\n';
}

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

int main(){
    init();
    solve();
}

• Subtask 1: 0 / 3
• Subtask 2: 0 / 3
• Subtask 3: 0 / 3
• Subtask 4: 0 / 4
• Subtask 5: 0 / 4
• Subtask 6: 0 / 3
• Subtask 7: 0 / 2
• Subtask 8: 0 / 3