Submission #1096295

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096295		epicci23	Flooding Wall (BOI24_wall)	C++17	100 / 100	4110 ms	213456 KiB

Main

#include "bits/stdc++.h"
#define int long long
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
using namespace std;

const int MOD = 1000000007;
const int N = 5e5 + 5;
const int INV = 5e8 + 4;

inline int add(int a,int b){
 return (a+b)%MOD;
}

inline int eks(int a,int b){
  return (a-b+MOD)%MOD;
}

inline int mult(int a,int b){
  return (a*b)%MOD;
}

int Pw[N];

struct SegT{
  int n;
  vector<int> lazy,sum,acik;
  SegT(int _n){
    n=_n;
    lazy.assign(4*n+5,1);
    sum.assign(4*n+5,0);
    acik.assign(n+5,0);
  }

  void push(int rt,int l,int r){
    if(l==r && !acik[l]) return;
    int u=lazy[rt];
    lazy[rt]=1;
    sum[rt]=mult(sum[rt],u);
    if(l==r) return;
    lazy[rt*2]=mult(lazy[rt*2],u);
    lazy[rt*2+1]=mult(lazy[rt*2+1],u);
  }

  void set(int rt,int l,int r,int ind,int u){
  	push(rt,l,r);
    if(r<ind || l>ind) return;
    if(l==r){
      acik[l]=1;
      sum[rt]=u;
      push(rt,l,r);
      return;
    }
    int m=(l+r)/2;
    set(rt*2,l,m,ind,u),set(rt*2+1,m+1,r,ind,u);
    sum[rt]=add(sum[rt*2],sum[rt*2+1]);
  }

  void update(int rt,int l,int r,int gl,int gr,int c){
    if(gl>gr) return;
  	push(rt,l,r);
    if(r<gl || l>gr) return;
    if(l>=gl && r<=gr){
      lazy[rt]=mult(lazy[rt],c);
      push(rt,l,r);
      return;
    }
    int m=(l+r)/2;
    update(rt*2,l,m,gl,gr,c),update(rt*2+1,m+1,r,gl,gr,c);
    sum[rt]=add(sum[rt*2],sum[rt*2+1]);
  }
};

void _(){
  int n;cin >> n;
  int ar[n+5][2];
  for(int i=1;i<=n;i++) cin >> ar[i][0];
  for(int i=1;i<=n;i++) cin >> ar[i][1];
  
  int ans=0;
  for(int i=1;i<=n;i++) ans=eks(ans,mult(Pw[n-1],ar[i][0]));
  for(int i=1;i<=n;i++) ans=eks(ans,mult(Pw[n-1],ar[i][1]));
 
  map<int,vector<int>> mp;
  vector<int> zip;
  zip.push_back(0);
  for(int i=1;i<=n;i++)
  	for(int j=0;j<2;j++){
  	  mp[ar[i][j]].push_back(i);
      zip.push_back(ar[i][j]);
    }
  sort(all(zip));
  zip.erase(unique(all(zip)),zip.end());
  reverse(all(zip));

  SegT R(n+5);
  vector<int> T(n+5,0);
  
  for(int i=1;i<=n;i++) R.update(1,1,n,1,i-1,2);
  for(int z=0;z<sz(zip)-1;z++){
    for(int& i:mp[zip[z]]){
      T[i]++;
      if(T[i]==1){
        R.set(1,1,n,i,mult(i,Pw[i-1]));
        R.update(1,1,n,1,i-1,INV);
      }
      else{
        R.update(1,1,n,i,i,2);
        R.update(1,1,n,1,i-1,0);
      }
    }
    ans=add(ans,mult(eks(zip[z],zip[z+1]),R.sum[1]));
  }
  
  SegT L(n+5);
  T.assign(n+5,0);
  for(int i=0;i<n;i++) L.update(1,0,n-1,i+1,n-1,2);
  for(int z=0;z<sz(zip)-1;z++){
    for(int& i:mp[zip[z]]){
      i--;
      T[i]++;
      if(T[i]==1){
        L.set(1,0,n-1,i,mult(i,Pw[n-1-i]));
        L.update(1,0,n-1,i+1,n-1,INV);
      }
      else{
        L.update(1,0,n-1,i,i,2);
        L.update(1,0,n-1,i+1,n-1,0);
      }
    }
    ans=eks(ans,mult(eks(zip[z],zip[z+1]),L.sum[1]));
  }

  cout << ans << '\n';
}

int32_t main(){
  cin.tie(0); ios::sync_with_stdio(0);
  Pw[0]=1;
  for(int i=1;i<N;i++) Pw[i]=add(Pw[i-1],Pw[i-1]);
  int tc=1;//cin >> tc;
  while(tc--) _();
  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