結果
| 問題 | No.2478 Disjoint-Sparse-Table Optimization |
| ユーザー |
 tko919
|
| 提出日時 | 2023-12-14 14:54:52 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 5 ms / 2,000 ms |
| コード長 | 13,777 bytes |
| コンパイル時間 | 3,381 ms |
| コンパイル使用メモリ | 233,388 KB |
| 最終ジャッジ日時 | 2025-02-18 10:54:21 |
|
ジャッジサーバーID （参考情報） |
judge3 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 12 |
ソースコード
#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;}