Submission #1022040

#	Time	Username	Problem	Language	Result	Execution time	Memory
1022040		huutuan	Flooding Wall (BOI24_wall)	C++14	100 / 100	3851 ms	237212 KiB

Main

#include<bits/stdc++.h>

using namespace std;

#define int long long

const int mod=1e9+7, N=1e6+10;
int power2[N], invpower2[N];

struct Node{
   int len, l, r, lr, lazyl, lazyr;
   Node (){
      len=lazyl=lazyr=0;
      l=r=lr=0;
   }
   Node operator+(const Node &b){
      Node ans;
      ans.len=len+b.len;
      ans.l=(l+b.l)%mod;
      ans.r=(r+b.r)%mod;
      ans.lr=(lr+b.lr)%mod;
      return ans;
   }
   int get_l(){
      return (mod-(l-len+mod)%mod)%mod;
   }
   int get_r(){
      return (mod-(r-len+mod)%mod)%mod;
   }
   int get_lr(){
      return (lr-l-r+len+mod+mod)%mod;
   }
};

struct SegmentTree{
   int n;
   vector<Node> t;
   void init(int _n){
      n=_n;
      t.assign(4*n+1, Node());
   }
   void build(int k, int l, int r, const vector<int> &vals){
      if (l==r){
         t[k].len=vals[r]-vals[l-1];
         t[k].l=t[k].len;
         t[k].r=t[k].len;
         t[k].lr=t[k].len;
         return;
      }
      int mid=(l+r)>>1;
      build(k<<1, l, mid, vals);
      build(k<<1|1, mid+1, r, vals);
      t[k]=t[k<<1]+t[k<<1|1];
   }
   void apply(int k, int lazyl, int lazyr){
      if (lazyl){
         int x=lazyl>0?power2[lazyl]:invpower2[-lazyl];
         t[k].l=1ll*t[k].l*x%mod;
         t[k].lr=1ll*t[k].lr*x%mod;
         t[k].lazyl+=lazyl;
      }
      if (lazyr){
         int x=lazyr>0?power2[lazyr]:invpower2[-lazyr];
         t[k].r=1ll*t[k].r*x%mod;
         t[k].lr=1ll*t[k].lr*x%mod;
         t[k].lazyr+=lazyr;
      }
   }
   void push(int k){
      apply(k<<1, t[k].lazyl, t[k].lazyr);
      apply(k<<1|1, t[k].lazyl, t[k].lazyr);
      t[k].lazyl=t[k].lazyr=0;
   }
   void update(int k, int l, int r, int L, int R, int lazyl, int lazyr){
      if (r<L || R<l) return;
      if (L<=l && r<=R){
         apply(k, lazyl, lazyr);
         return;
      }
      push(k);
      int mid=(l+r)>>1;
      update(k<<1, l, mid, L, R, lazyl, lazyr);
      update(k<<1|1, mid+1, r, L, R, lazyl, lazyr);
      t[k]=t[k<<1]+t[k<<1|1];
   }
   Node get(int k, int l, int r, int L, int R){
      if (r<L || R<l) return t[0];
      if (L<=l && r<=R) return t[k];
      push(k);
      int mid=(l+r)>>1;
      return get(k<<1, l, mid, L, R)+get(k<<1|1, mid+1, r, L, R);
   }
} st;

int n, a[N], b[N];
int pf[N], sf[N];

int32_t main(){
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   power2[0]=1;
   for (int i=1; i<N; ++i) power2[i]=power2[i-1]*2%mod;
   invpower2[0]=1;
   invpower2[1]=(mod+1)/2;
   for (int i=2; i<N; ++i) invpower2[i]=invpower2[i-1]*invpower2[1]%mod;
   cin >> n;
   vector<int> vals{0};
   for (int i=1; i<=n; ++i) cin >> a[i], vals.push_back(a[i]);
   for (int i=1; i<=n; ++i) cin >> b[i], vals.push_back(b[i]);
   sort(vals.begin(), vals.end()); vals.resize(unique(vals.begin(), vals.end())-vals.begin());
   st.init((int)vals.size()-1);
   st.build(1, 1, st.n, vals);
   for (int i=1; i<=n; ++i){
      a[i]=lower_bound(vals.begin(), vals.end(), a[i])-vals.begin();
      b[i]=lower_bound(vals.begin(), vals.end(), b[i])-vals.begin();
      st.update(1, 1, st.n, min(a[i], b[i])+1, max(a[i], b[i]), 0, -1);
      pf[i]=max(pf[i-1], min(a[i], b[i]));
   }
   for (int i=n; i>=1; --i) sf[i]=max(sf[i+1], min(a[i], b[i]));
   int ans=0;
   for (int i=1; i<=n; ++i){
      st.update(1, 1, st.n, min(a[i], b[i])+1, max(a[i], b[i]), 0, 1);
      if (i!=1 && i!=n){
         int t1=pf[i-1], t2=sf[i+1];
         {
            int l=a[i], r=min(t1, t2);
            if (l<r){
               ans=(ans+(vals[r]-vals[l])*power2[n-1])%mod;
            }
         }
         {
            int l=max(a[i], t1), r=t2;
            if (l<r){
               ans=(ans+st.get(1, 1, st.n, l+1, r).get_l()*power2[n-1])%mod;
            }
         }
         {
            int l=max(a[i], t2), r=t1;
            if (l<r){
               ans=(ans+st.get(1, 1, st.n, l+1, r).get_r()*power2[n-1])%mod;
            }
         }
         {
            int l=max({a[i], t1, t2}), r=st.n;
            if (l<r){
               ans=(ans+st.get(1, 1, st.n, l+1, r).get_lr()*power2[n-1])%mod;
            }
         }
         {
            int l=b[i], r=min(t1, t2);
            if (l<r){
               ans=(ans+(vals[r]-vals[l])*power2[n-1])%mod;
            }
         }
         {
            int l=max(b[i], t1), r=t2;
            if (l<r){
               ans=(ans+st.get(1, 1, st.n, l+1, r).get_l()*power2[n-1])%mod;
            }
         }
         {
            int l=max(b[i], t2), r=t1;
            if (l<r){
               ans=(ans+st.get(1, 1, st.n, l+1, r).get_r()*power2[n-1])%mod;
            }
         }
         {
            int l=max({b[i], t1, t2}), r=st.n;
            if (l<r){
               ans=(ans+st.get(1, 1, st.n, l+1, r).get_lr()*power2[n-1])%mod;
            }
         }
      }
      st.update(1, 1, st.n, min(a[i], b[i])+1, max(a[i], b[i]), -1, 0);
   }
   cout << ans << '\n';
   return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 17 / 17
• Subtask 3: 19 / 19
• Subtask 4: 14 / 14
• Subtask 5: 12 / 12
• Subtask 6: 30 / 30