#938272 (C++17) No.2478 Disjoint-Sparse-Table Optimization

提出ソース
結果

問題	No.2478 Disjoint-Sparse-Table Optimization
ユーザー	tko919
提出日時	2023-12-14 14:54:52
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	5 ms / 2,000 ms
コード長	13,777 bytes
コンパイル時間	3,301 ms
コンパイル使用メモリ	241,908 KB
実行使用メモリ	5,376 KB
最終ジャッジ日時	2024-09-27 05:43:30
合計ジャッジ時間	3,878 ms
ジャッジサーバーID （参考情報）	judge3 / judge1
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,376 KB
testcase_02	AC	1 ms 5,376 KB
testcase_03	AC	3 ms 5,376 KB
testcase_04	AC	4 ms 5,376 KB
testcase_05	AC	3 ms 5,376 KB
testcase_06	AC	4 ms 5,376 KB
testcase_07	AC	4 ms 5,376 KB
testcase_08	AC	4 ms 5,376 KB
testcase_09	AC	4 ms 5,376 KB
testcase_10	AC	4 ms 5,376 KB
testcase_11	AC	5 ms 5,376 KB
testcase_12	AC	2 ms 5,376 KB
testcase_13	AC	5 ms 5,376 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
#line 1 "library/Template/template.hpp"
#include <bits/stdc++.h>
using namespace std;

#define rep(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define ALL(v) (v).begin(),(v).end()
#define UNIQUE(v) sort(ALL(v)),(v).erase(unique(ALL(v)),(v).end())
#define SZ(v) (int)v.size()
#define MIN(v) *min_element(ALL(v))
#define MAX(v) *max_element(ALL(v))
#define LB(v,x) int(lower_bound(ALL(v),(x))-(v).begin())
#define UB(v,x) int(upper_bound(ALL(v),(x))-(v).begin())

using ll=long long int;
using ull=unsigned long long;
const int inf = 0x3fffffff;
const ll INF = 0x1fffffffffffffff;

template<typename T>inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<typename T>inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<typename T,typename U>T ceil(T x,U y){assert(y!=0); if(y<0)x=-x,y=-y; return (x>0?(x+y-1)/y:x/y);}
template<typename T,typename U>T floor(T x,U y){assert(y!=0); if(y<0)x=-x,y=-y; return (x>0?x/y:(x-y+1)/y);}
template<typename T>int popcnt(T x){return __builtin_popcountll(x);}
template<typename T>int topbit(T x){return (x==0?-1:63-__builtin_clzll(x));}
template<typename T>int lowbit(T x){return (x==0?-1:__builtin_ctzll(x));}
#line 2 "library/Utility/fastio.hpp"
#include <unistd.h>

class FastIO{
    static constexpr int L=1<<16;
    char rdbuf[L];
    int rdLeft=0,rdRight=0;
    inline void reload(){
        int len=rdRight-rdLeft;
        memmove(rdbuf,rdbuf+rdLeft,len);
        rdLeft=0,rdRight=len;
        rdRight+=fread(rdbuf+len,1,L-len,stdin);
    }
    inline bool skip(){
        for(;;){
            while(rdLeft!=rdRight and rdbuf[rdLeft]<=' ')rdLeft++;
            if(rdLeft==rdRight){
                reload();
                if(rdLeft==rdRight)return false;
            }
            else break;
        }
        return true;
    }
    template<typename T,enable_if_t<is_integral<T>::value,int> =0>inline bool _read(T& x){
        if(!skip())return false;
        if(rdLeft+20>=rdRight)reload();
        bool neg=false;
        if(rdbuf[rdLeft]=='-'){
            neg=true;
            rdLeft++;
        }
        x=0;
        while(rdbuf[rdLeft]>='0' and rdLeft<rdRight){
            x=x*10+(neg?-(rdbuf[rdLeft++]^48):(rdbuf[rdLeft++]^48));
        }
        return true;
    }
    inline bool _read(__int128_t& x){
        if(!skip())return false;
        if(rdLeft+40>=rdRight)reload();
        bool neg=false;
        if(rdbuf[rdLeft]=='-'){
            neg=true;
            rdLeft++;
        }
        x=0;
        while(rdbuf[rdLeft]>='0' and rdLeft<rdRight){
            x=x*10+(neg?-(rdbuf[rdLeft++]^48):(rdbuf[rdLeft++]^48));
        }
        return true;
    }
    inline bool _read(__uint128_t& x){
        if(!skip())return false;
        if(rdLeft+40>=rdRight)reload();
        x=0;
        while(rdbuf[rdLeft]>='0' and rdLeft<rdRight){
            x=x*10+(rdbuf[rdLeft++]^48);
        }
        return true;
    }
    template<typename T,enable_if_t<is_floating_point<T>::value,int> =0>inline bool _read(T& x){
        if(!skip())return false;
        if(rdLeft+20>=rdRight)reload();
        bool neg=false;
        if(rdbuf[rdLeft]=='-'){
            neg=true;
            rdLeft++;
        }
        x=0;
        while(rdbuf[rdLeft]>='0' and rdbuf[rdLeft]<='9' and rdLeft<rdRight){
            x=x*10+(rdbuf[rdLeft++]^48);
        }
        if(rdbuf[rdLeft]!='.')return true;
        rdLeft++;
        T base=.1;
        while(rdbuf[rdLeft]>='0' and rdbuf[rdLeft]<='9' and rdLeft<rdRight){
            x+=base*(rdbuf[rdLeft++]^48);
            base*=.1;
        }
        if(neg)x=-x;
        return true;
    }
    inline bool _read(char& x){
        if(!skip())return false;
        if(rdLeft+1>=rdRight)reload();
        x=rdbuf[rdLeft++];
        return true;
    }
    inline bool _read(string& x){
        if(!skip())return false;
        for(;;){
            int pos=rdLeft;
            while(pos<rdRight and rdbuf[pos]>' ')pos++;
            x.append(rdbuf+rdLeft,pos-rdLeft);
            if(rdLeft==pos)break;
            rdLeft=pos;
            if(rdLeft==rdRight)reload();
            else break;
        }
        return true;
    }
    template<typename T>inline bool _read(vector<T>& v){
        for(auto& x:v){
            if(!_read(x))return false;
        }
        return true;
    }

    char wtbuf[L],tmp[50];
    int wtRight=0;
    inline void _write(const char& x){
        if(wtRight>L-32)flush();
        wtbuf[wtRight++]=x;
    }
    inline void _write(const string& x){
        for(auto& c:x)_write(c);
    }
    template<typename T,enable_if_t<is_integral<T>::value,int> =0>inline void _write(T x){
        if(wtRight>L-32)flush();
        if(x==0){
            _write('0');
            return;
        }
        else if(x<0){
            _write('-');
            if (__builtin_expect(x == std::numeric_limits<T>::min(), 0)) {
                switch (sizeof(x)) {
                case 2: _write("32768"); return;
                case 4: _write("2147483648"); return;
                case 8: _write("9223372036854775808"); return;
                }
            }
            x=-x;
        }
        int pos=0;
        while(x!=0){
            tmp[pos++]=char((x%10)|48);
            x/=10;
        }
        rep(i,0,pos)wtbuf[wtRight+i]=tmp[pos-1-i];
        wtRight+=pos;
    }
    inline void _write(__int128_t x){
        if(wtRight>L-40)flush();
        if(x==0){
            _write('0');
            return;
        }
        else if(x<0){
            _write('-');
            x=-x;
        }
        int pos=0;
        while(x!=0){
            tmp[pos++]=char((x%10)|48);
            x/=10;
        }
        rep(i,0,pos)wtbuf[wtRight+i]=tmp[pos-1-i];
        wtRight+=pos;
    }
    inline void _write(__uint128_t x){
        if(wtRight>L-40)flush();
        if(x==0){
            _write('0');
            return;
        }
        int pos=0;
        while(x!=0){
            tmp[pos++]=char((x%10)|48);
            x/=10;
        }
        rep(i,0,pos)wtbuf[wtRight+i]=tmp[pos-1-i];
        wtRight+=pos;
    }
    inline void _write(double x){
        ostringstream oss;
        oss << fixed << setprecision(15) << double(x);
        string s = oss.str();
        _write(s);
    }
    template<typename T>inline void _write(const vector<T>& v){
        rep(i,0,v.size()){
            if(i)_write(' ');
            _write(v[i]);
        }
    }
public:
    FastIO(){}
    ~FastIO(){flush();}
    inline void read(){}
    template <typename Head, typename... Tail>inline void read(Head& head,Tail&... tail){
        assert(_read(head));
        read(tail...); 
    }
    template<bool ln=true,bool space=false>inline void write(){if(ln)_write('\n');}
    template <bool ln=true,bool space=false,typename Head, typename... Tail>inline void write(const Head& head,const Tail&... tail){
        _write(head);
        write<ln,true>(tail...); 
        if(space)_write(' ');
    }
    inline void flush(){
        fwrite(wtbuf,1,wtRight,stdout);
        wtRight=0;
    }
};

/**
 * @brief Fast IO
 */
#line 3 "sol.cpp"
class GeneralWeightedMatching{
    struct E{int u,v; ll w;};
    int n,m,in;
    vector<vector<E>> G;
    vector<int> mate,slack,root,par,isS,used;
    vector<vector<int>> flower,belong;
    vector<ll> dual;
    queue<int> que;
    
    ll dist(const E& e){return dual[e.u]+dual[e.v]-e.w;}
    void update(int u,int v){
        if(!slack[v] or dist(G[u][v])<dist(G[slack[v]][v]))slack[v]=u;
    }
    void recalc(int v){
        slack[v]=0;
        rep(i,1,n+1)if(G[i][v].w and root[i]!=v and isS[root[i]]==1)update(i,v);
    }
    void push(int v){
        if(v<=n)que.push(v);
        else for(auto& nxt:flower[v])push(nxt);
    }
    void set(int v,int rt){
        root[v]=rt;
        if(v>n)for(auto& nxt:flower[v])set(nxt,rt);
    }
    int findeven(int b,int v){
        int pos=find(ALL(flower[b]),v)-flower[b].begin();
        if(pos&1){
            reverse(flower[b].begin()+1,flower[b].end());
            pos=flower[b].size()-pos;
        }
        return pos;
    }
    void match(int u,int v){
        mate[u]=G[u][v].v;
        if(u>n){
            int x=belong[u][G[u][v].u];
            int pos=findeven(u,x);
            rep(i,0,pos)match(flower[u][i],flower[u][i^1]);
            match(x,v);
            rotate(flower[u].begin(),flower[u].begin()+pos,flower[u].end());
        }
    }
    void link(int u,int v){
        for(;;){
            int nv=root[mate[u]];
            match(u,v);
            if(!nv)break;
            v=nv,u=root[par[nv]];
            match(v,u);
        }
    }
    void make(int u,int v,int lca){
        int id=n+1;
        while(id<=m and root[id])id++;
        if(id>m)m++;
        flower[id].clear();
        rep(i,1,m+1)G[id][i].w=G[i][id].w=0;
        rep(i,1,n+1)belong[id][i]=0;
        isS[id]=1,dual[id]=0,mate[id]=mate[lca];
        while(u!=lca){
            flower[id].push_back(u);
            u=root[mate[u]];
            push(u);
            flower[id].push_back(u);
            u=root[par[u]];
        }
        flower[id].push_back(lca);
        reverse(ALL(flower[id]));
        while(v!=lca){
            flower[id].push_back(v);
            v=root[mate[v]];
            push(v);
            flower[id].push_back(v);
            v=root[par[v]];
        }
        set(id,id);
        for(auto& c:flower[id]){
            rep(i,1,m+1)if(!G[id][i].w or dist(G[c][i])<dist(G[id][i])){
                G[id][i]=G[c][i],G[i][id]=G[i][c];
            }
            rep(i,1,n+1)if(belong[c][i])belong[id][i]=c;
        }
        recalc(id);
    }
    void expand(int b){
        for(auto& c:flower[b])set(c,c);
        int x=belong[b][G[b][par[b]].u];
        isS[x]=2,par[x]=par[b];
        int pos=findeven(b,x);
        for(int i=0;i<pos;i+=2){
            int T=flower[b][i],S=flower[b][i+1];
            isS[S]=1,isS[T]=2;
            par[T]=G[S][T].u;
            slack[S]=slack[T]=0;
            push(S);
        }
        rep(i,pos+1,flower[b].size()){
            isS[flower[b][i]]=0;
            recalc(flower[b][i]);
        }
        flower[b].clear();
        root[b]=0;
    }
    bool path(const E& e){
        int u=root[e.u],v=root[e.v];
        if(!isS[v]){
            par[v]=e.u;
            isS[v]=2;
            int nu=root[mate[v]];
            slack[v]=slack[nu]=0;
            isS[nu]=1;
            push(nu);
        }
        else if(isS[v]==1){
            int lca=0,bu=u,bv=v;
            in++;
            while(bu){
                used[bu]=in;
                bu=root[mate[bu]];
                if(bu)bu=root[par[bu]];
            }
            while(bv){
                if(used[bv]==in){
                    lca=bv;
                    break;
                }
                bv=root[mate[bv]];
                if(bv)bv=root[par[bv]];
            }
            if(lca)make(u,v,lca);
            else{
                link(u,v),link(v,u);
                return true;
            }
        }
        return false;
    }
    bool augment(){
        isS=slack=par=vector<int>(n*2);
        que=queue<int>();
        rep(i,1,m+1)if(root[i]==i and !mate[i]){
            isS[i]=1;
            push(i);
        }
        if(que.empty())return false;
        for(;;){
            while(!que.empty()){
                int v=que.front();
                que.pop();
                rep(i,1,n+1)if(G[v][i].w and root[i]!=root[v]){
                    if(!dist(G[v][i])){
                        if(path(G[v][i]))return true;
                    }
                    else if(isS[root[i]]!=2)update(v,root[i]);
                }
            }
            ll delta=INF;
            rep(i,n+1,m+1)if(root[i]==i and isS[i]==2)chmin(delta,dual[i]/2);
            rep(i,1,m+1)if(root[i]==i and slack[i] and isS[i]!=2){
                if(!isS[i])chmin(delta,dist(G[slack[i]][i]));
                else chmin(delta,dist(G[slack[i]][i])/2);
            }
            rep(i,1,n+1){
                if(isS[root[i]]==1){
                    dual[i]-=delta;
                    if(dual[i]<=0)return false;
                }
                else if(isS[root[i]]==2)dual[i]+=delta;
            }
            rep(i,n+1,m+1)if(root[i]==i and isS[i]){
                if(isS[i]==1)dual[i]+=delta*2;
                else dual[i]-=delta*2;
            }
            rep(i,1,m+1)if(root[i]==i and slack[i] and root[slack[i]]!=i){
                if(dist(G[slack[i]][i])==0 and path(G[slack[i]][i]))return true;
            }
            rep(i,n+1,m+1)if(root[i]==i and isS[i]==2 and dual[i]==0)expand(i);
        }
    }
public:
    GeneralWeightedMatching(int _n):n(_n),m(n),in(0),G(n*2,vector<E>(n*2)),
        mate(n*2),root(n*2),used(n*2),flower(n*2),belong(n*2,vector<int>(n*2)),dual(n*2){
        rep(i,0,n+1){
            root[i]=i;
            belong[i][i]=i;
            if(i)dual[i]=INF;
            rep(j,0,n+1)G[i][j]=E{i,j,0};
        }
    }
    void add_edge(int u,int v,ll w){
        u++,v++;
        chmax(G[u][v].w,w*2);
        chmax(G[v][u].w,w*2);
    }
    vector<int> run(){
        while(augment());
        vector<int> res(n,-1);
        rep(i,1,n+1)if(mate[i])res[i-1]=mate[i]-1;
        return res;
    }
};

FastIO io;
int main(){
    int n;
    io.read(n);
    vector<int> L(n),R(n);
    rep(i,0,n)io.read(L[i],R[i]),L[i]--,R[i]--;
    vector<ll> a(n*2-1);
    io.read(a);
    vector<ll> rui(n*2);
    rep(i,0,n*2-1)rui[i+1]=rui[i]+a[i];

    ll ret=0;
    rep(i,0,n)ret+=rui[R[i]]-rui[L[i]];

    GeneralWeightedMatching buf(n);
    vector W(n,vector<ll>(n));
    rep(i,0,n)rep(j,0,n){
        if(L[i]<L[j] and L[j]<R[i] and R[i]<R[j]){
            W[i][j]=W[j][i]=rui[R[i]]-rui[L[j]];
            buf.add_edge(i,j,W[i][j]);
        }
    }
    auto mate=buf.run();
    rep(i,0,n)if(i<mate[i])ret-=W[i][mate[i]];
    io.write(ret);
    return 0;
}
yukicoder

結果

テストケース

ソースコード
