Submission #754431

#	Time	Username	Problem	Language	Result	Execution time	Memory
754431		A_D	Wall (IOI14_wall)	C++17	0 / 100	1 ms	256 KiB

wall

    #include "wall.h"
    #include <bits/stdc++.h>
    #define ii pair<int,int>
    #define F first
    #define S second
    using namespace std;
    const int N=2e6+100;
    int mn[4*N];
    int mx[4*N];
    int seg[4*N];
     
    ii com(ii a, ii b,int&u,int h)
    {
      if(a.S<b.F){
        u=a.S;
        return {a.S,a.S};
      }
      if(b.S<a.F){
        u=a.F;
        return {a.F,a.F};
      }
      if(a.F<=b.F&&b.S<=a.S){
        return b;
      }
      if(b.F<=a.F&&a.S<=b.S){
        u=h;
        return a;
      }
      u=min({u,a.S,b.S});
      u=max({u,a.F,b.F});
      return make_pair(max(a.F,b.F),min(a.S,b.S));
    }
      
    void update(int p,int s,int e,int a,int b,int h,int t,ii v,int par)
    {
      ii r;
      r.F=mn[p];
      r.S=mx[p];
      v=com(v,r,seg[p],par);
      mn[p]=v.F;
      mx[p]=v.S;
      if(a<=s&&e<=b){
        if(t==1){
          mn[p]=max(mn[p],h);
          if(mn[p]>mx[p]){
            mx[p]=h;
          }
        }
        else{
          mx[p]=min(mx[p],h);
          if(mx[p]<mn[p]){
            mn[p]=h;
          }
        }
        seg[p]=min(seg[p],mn[p]);
        seg[p]=max(seg[p],mx[p]);
        return;
      }
      if(a>e || b<s){
        return;
      }
      mn[p]=0;
      mx[p]=1e5;
      int mid=(s+e)/2;
      update(p*2,s,mid,a,b,h,t,v,seg[p]);
      update(p*2+1,mid+1,e,a,b,h,t,v,seg[p]);
    }
    int get(int p,int s,int e,int i,ii v,int par)
    {
      v=com(v,{mn[p],mx[p]},seg[p],par);
      if(s==e){
        return seg[p];
      }
      int mid=(s+e)/2;
      if(i<=mid){
        return get(p*2,s,mid,i,v,seg[p]);
      }
      else{
        return get(p*2+1,mid+1,e,i,v,seg[p]);
      }
    }
      
    void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
    {
        for(int i=1;i<=4*n;i++){
          mn[i]=0;
          mx[i]=1e5;
          seg[i]=0;
        }
        for(int i=0;i<k;i++){
          assert(height[i]>=0 && height[i]<=(int)1e5);
          update(1,0,n-1,left[i],right[i],height[i],op[i],make_pair(0,1e5),0);
        }
        for(int i=0;i<n;i++){
          finalHeight[i]=get(1,0,n-1,i,{0,1e5},0);
        }
        //cout<<"\n";
    }		

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