Submission #930784

#	Time	Username	Problem	Language	Result	Execution time	Memory
930784		shenfe1	Wall (IOI14_wall)	C++14	100 / 100	1199 ms	106936 KiB

wall

#include<bits/stdc++.h>

#include "wall.h"

using namespace std;

#define F first
#define S second
#define ll long long
#define maksim gay
// #define int ll
#define pb push_back
#define sz(s) (int)s.size()
#define pii pair<int,int>
#define all(v) v.begin(),v.end()
#define mem(a,i) memset(a,i,sizeof(a))
#define in insert
#define lb lower_bound
#define ub upper_bound
#define y1 yy
#define ppb pop_back

const int MAX=2e6+10;
const int inf=2e9;
const int N=2e5;
const int mod=998244353;

int binpow(int a,int n){
  if(n==0)return 1;
  if(n%2)return a*binpow(a,n-1)%mod;
  int k=binpow(a,n/2);
  return k*k%mod;
}

struct DO{
  int t[4*MAX],t1[4*MAX];
  int c[4*MAX],c1[4*MAX];

  void build(int v,int tl,int tr){
    t[v]=0;
    t1[v]=1;
    c[v]=0;
    c1[v]=inf;
    if(tl==tr)return;
    int tm=(tl+tr)/2;
    build(2*v,tl,tm);
    build(2*v+1,tm+1,tr);
  }

  void upd(int v,int op,int x){
    if(t1[v]==op){
      if(!op)c1[v]=max(c1[v],x);
      else c1[v]=min(c1[v],x);
    }
    else{
      if(!op)x=max(x,min(c[v],c1[v]));
      else x=min(x,max(c[v],c1[v]));
      c[v]=c1[v];
      c1[v]=x;
      t[v]^=1;
      t1[v]^=1;
    }
    // cout<<v<<" "<<t[v]<<" "<<c[v]<<" "<<t1[v]<<" "<<c1[v]<<"\n";
  }

  void push(int v){
    // cout<<"!!! "<<v<<" "<<t[v]<<" "<<c[v]<<" "<<t1[v]<<" "<<c1[v]<<"\n";
    upd(2*v,t[v],c[v]);
    upd(2*v,t1[v],c1[v]);
    upd(2*v+1,t[v],c[v]);
    upd(2*v+1,t1[v],c1[v]);
    t[v]=0;
    t1[v]=1;
    c[v]=0;
    c1[v]=inf;
  }

  void update(int v,int tl,int tr,int l,int r,int op,int x){
    if(l>r||tl>r||l>tr)return;
    if(l<=tl&&tr<=r){
      upd(v,op,x);
      return;
    }
    push(v);
    int tm=(tl+tr)/2;
    update(2*v,tl,tm,l,r,op,x);
    update(2*v+1,tm+1,tr,l,r,op,x);
  }

  pair<pii,pii> get(int v,int tl,int tr,int pos){
    if(tl==tr){
      return {{t[v],c[v]},{t1[v],c1[v]}};
    }
    int tm=(tl+tr)/2;
    push(v);
    if(pos<=tm)return get(2*v,tl,tm,pos);
    else return get(2*v+1,tm+1,tr,pos);
  }
}t;

void add(int &x,pii y){
  if(y.F==0)x=max(x,y.S);
  else x=min(x,y.S);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  for(int i=0;i<n;i++)finalHeight[i]=0;
  t.build(1,0,n-1);
  for(int i=0;i<k;i++){
    t.update(1,0,n-1,left[i],right[i],op[i]-1,height[i]);
  } 
  for(int i=0;i<n;i++){
    pair<pii,pii> f=t.get(1,0,n-1,i);
    finalHeight[i]=0;
    add(finalHeight[i],f.F);
    add(finalHeight[i],f.S);
  }
}

• Subtask 1: 8 / 8
• Subtask 2: 24 / 24
• Subtask 3: 29 / 29
• Subtask 4: 39 / 39