Submission #1062863

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062863		uacoder123	Wall (IOI14_wall)	C++14	100 / 100	920 ms	161992 KiB

wall

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define F first
#define S second
#define FOR(i,a,b) for (auto i = (a); i <= (b); ++i)
#define NFOR(i,a,b) for(auto i = (a); i >= (b); --i)
#define all(x) (x).begin(), (x).end()
#define sz(x) lli(x.size())
#define mp(i,a) make_pair(i,a)
#define pb(a) push_back(a)
#define bit(x,b) (x&(1LL<<b))
typedef int lli;
typedef pair <lli,lli> ii;
typedef pair <ii,lli> iii;
typedef pair <ii,ii> iiii;
typedef vector <lli> vi;
typedef tree<lli,null_type,less<lli>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
ii ra[4*2000001],lazy[4*2000001];
ii m(ii in,int s,int e)
{
  if(in.S<s)
    return mp(s,s);
  if(in.F>e)
    return mp(e,e);
  return mp(max(in.F,s),min(in.S,e));
}
void up(int node,int l,int r,int s,int e,int vs,int ve)
{
  if(r<s|l>e)
    return;
  ra[node]=m(ra[node],lazy[node].F,lazy[node].S);
    lazy[2*node+1]=m(lazy[2*node+1],lazy[node].F,lazy[node].S);
    lazy[2*node+2]=m(lazy[2*node+2],lazy[node].F,lazy[node].S);
  lazy[node]=mp(0,1000000);
  if(l>=s&&r<=e)
  {
    ra[node]=m(ra[node],vs,ve);
    lazy[2*node+1]=m(lazy[2*node+1],vs,ve);
    lazy[2*node+2]=m(lazy[2*node+2],vs,ve);
    return;
  }
  int m=(l+r)/2;
  up(2*node+1,l,m,s,e,vs,ve);
  up(2*node+2,m+1,r,s,e,vs,ve);
  ra[node].F=min(ra[2*node+1].F,ra[2*node+2].F);
  ra[node].S=max(ra[2*node+1].S,ra[2*node+2].S);
}
ii qu(int node,int l,int r,int i)
{
  ra[node]=m(ra[node],lazy[node].F,lazy[node].S);
  if(l!=r)
  {
    lazy[2*node+1]=m(lazy[2*node+1],lazy[node].F,lazy[node].S);
    lazy[2*node+2]=m(lazy[2*node+2],lazy[node].F,lazy[node].S);
  }
  lazy[node]=mp(0,1000000);
  if(l==r)
    return ra[node];
  int m=(l+r)/2;
  ii sa;
  if(i<=m)
    return qu(2*node+1,l,m,i);
  else
    return qu(2*node+2,m+1,r,i);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
  for(int i=0;i<4*n+1;++i)
  {
    lazy[i]=mp(0,1000000);
    ra[i]=mp(0,0);
  }
  for(int i=0;i<k;++i)
  {
    if(op[i]==1)
    up(0,0,n,left[i],right[i],height[i],1000000);
  else 
    up(0,0,n,left[i],right[i],0,height[i]);
  }
  for(int i=0;i<n;++i)
    finalHeight[i]=qu(0,0,n,i).F;
}

Compilation message (stderr)

wall.cpp: In function 'void up(int, int, int, int, int, int, int)':
wall.cpp:31:7: warning: suggest parentheses around comparison in operand of '|' [-Wparentheses]
   31 |   if(r<s|l>e)
      |      ~^~

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