提出 #60158324

---

ソースコード 拡げる

#include<bits/stdc++.h>
#define lc(x) (x<<1)
#define rc(x) (lc(x)|1)
using namespace std;
typedef long long ll;
const ll N = 18,M = 1<<N,INF = 1e18;
template<typename T>void tomin(T& x,T y){x = min(x,y);}
template<typename T>void tomax(T& x,T y){x = max(x,y);}
//
int n,U,s[M],t[M];

ll vs[M<<2],vt[M<<2],lim[M<<2],ans;
void dfs(int x,int L,int R){
    if(L == R-1){
        vs[x] = s[L],vt[x] = t[L]; lim[x] = 1;
        return;
    }
    int mid = (L+R)/2;
    int p = lc(x),q = rc(x);
    dfs(p,L,mid); dfs(q,mid,R);
    if(max(vs[p],vs[q]) <= min(vt[p],vt[q])){
        vs[x] = max(vs[p],vs[q]),vt[x] = max(vt[p],vt[q]);
        lim[x] = max(lim[p],lim[q]); tomax(lim[x],min(vs[p],vs[q]));
    }else{
        ans += max(vs[p],vs[q]) - min(vt[p],vt[q]);
        vs[x] = min(vt[p],vt[q]),vt[x] = max(vt[p],vt[q]);
        tomax(vs[x],max(lim[p],lim[q]));
        lim[x] = max(lim[p],lim[q]); tomax(lim[x],min(vs[p],vs[q]));
    }
}

int main(){
    ios::sync_with_stdio(false); cin.tie(0);
    cin>>n; U = (1<<n);
    for(int i=0;i<U;i++)cin>>s[i]>>t[i];
    dfs(1,0,U);
    cout<<ans<<endl;
    return 0;
}

提出情報

ジャッジ結果