Submission #1096281

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096281		epicci23	Flooding Wall (BOI24_wall)	C++17	12 / 100	2274 ms	100276 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){
      //cout << "actim: " << l << ' ' << u << ' ' << lazy[rt] << '\n';
      acik[l]=1;
      sum[rt]=u;
      push(rt,l,r);
      //cout << "l: " << l << ' ' << sum[rt] << '\n';
      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;
  for(int i=1;i<=n;i++)
  	for(int j=0;j<2;j++)
  	  mp[-ar[i][j]].push_back(i);

  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(auto x:mp){
    for(int& i:x.second){
      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,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(auto x:mp){
    for(int& i:x.second){
      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,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: 0 / 8
• Subtask 2: 0 / 17
• Subtask 3: 0 / 19
• Subtask 4: 0 / 14
• Subtask 5: 12 / 12
• Subtask 6: 0 / 30