Submission #292089

#	Time	Username	Problem	Language	Result	Execution time	Memory
292089		LifeHappen__	Wall (IOI14_wall)	C++14	100 / 100	1491 ms	110328 KiB

wall

#include <bits/stdc++.h>
#include "wall.h"

using namespace std;

#define forinc(a,b,c) for(int a=b, __c=c; a<=__c; ++a)
#define fordec(a,b,c) for(int a=b, __c=c; a>=__c; --a)
#define forv(a,b) for(auto &a:b)
#define forb(a,b) for(int a=b._Find_first(); a<b.size(); a=b._Find_next(a))

#define ii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define all(a) begin(a),end(a)
#define rall(a) rbegin(a),rend(a)
#define reset(f,x) memset(f,x,sizeof(f))
#define fasty ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define gg exit(0);

#define bit(x,i) (x>>(i-1)&1ll)
#define on(x,i) (x|(1ll<<(i-1)))
#define off(x,i) (x&~(1ll<<(i-1)))

typedef int64_t ll;
typedef unsigned long long ull;

const int N=2e6+5;
const int inf=1e9;
int n,k;
int ma[N*4], mi[N*4];
int lzma[N*4], lzmi[N*4];
int ret[N];

void build(int i,int l,int r){
   //ma[i]=inf, mi[i]=inf;
   lzma[i]=-inf;
   lzmi[i]=inf;
   if(l==r) return;
   int mid=l+(r-l)/2;
   build(i<<1,l,mid); build(i<<1|1,mid+1,r);
}

#define lc (i<<1)
#define rc (i<<1|1)

void mx(int &x,int y){x=max(x,y);}
void mn(int &x,int y){x=min(x,y);}

void trans(int i,int l,int r){
   mn(mi[i],lzmi[i]);
   mn(ma[i],lzmi[i]);
   mx(mi[i],lzma[i]);
   mx(ma[i],lzma[i]);
   if(l!=r){
      mx(ma[lc],lzma[i]); mn(ma[lc],lzmi[i]);
      mx(ma[rc],lzma[i]); mn(ma[rc],lzmi[i]);
      mx(lzma[lc],lzma[i]); mn(lzma[lc],lzmi[i]);
      mx(lzma[rc],lzma[i]); mn(lzma[rc],lzmi[i]);
      mx(lzmi[lc],lzma[i]); mn(lzmi[lc],lzmi[i]);
      mx(lzmi[rc],lzma[i]); mn(lzmi[rc],lzmi[i]);
      lzma[i]=-inf; lzmi[i]=inf;
   }
}

void upd(int i,int l,int r,int u,int v,int val,int o){
   trans(i,l,r);
   if(v<l || u>r) return;
   if(u<=l && r<=v){
      if(o==1){
         mx(lzma[i],val);
         mx(lzmi[i],val);
      } else{
         mn(lzma[i],val);
         mn(lzmi[i],val);
      }
      trans(i,l,r);
      return;
   }
   int mid=l+(r-l)/2;
   upd(lc,l,mid,u,v,val,o); upd(rc,mid+1,r,u,v,val,o);
   ma[i]=max(ma[lc],ma[rc]);
   mi[i]=min(mi[lc],mi[rc]);
}
void dfs(int i,int l,int r){
   trans(i,l,r);
   if(l==r){
      ret[l]=ma[i];
      return;
   }
   int mid=l+(r-l)/2;
   dfs(lc,l,mid); dfs(rc,mid+1,r);
}

void buildWall(int _n,int _k,int P[],int L[],int R[],int H[],int ans[]){
   n=_n, k=_k;
   build(1,1,n);
   forinc(i,0,k-1){
      upd(1,1,n,L[i]+1,R[i]+1,H[i],P[i]);
   }
   dfs(1,1,n);
   forinc(i,1,n) ans[i-1]=ret[i];
}
/*
int32_t main(){
   fasty;

   #define task "buildwall"
   if(fopen(task".inp","r")) freopen(task".inp","r",stdin);

   cin>>n>>k;
   forinc(i,0,k-1) cin>>p[i]>>x[i]>>y[i]>>h[i];
   //buildWall(n,k,p,x,y,h,ret);
   build(1,1,n);
   forinc(i,0,k-1){
      upd(1,1,n,x[i]+1,y[i]+1,h[i],p[i]);
   }
   dfs(1,1,n);
   forinc(i,1,n) cout<<ret[i]<<' ';
}
*/

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