Submission #942926

#	Time	Username	Problem	Language	Result	Execution time	Memory
942926		kim	Wall (IOI14_wall)	C++17	8 / 100	3069 ms	90412 KiB

wall

#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
#define eb emplace_back
using pii=pair<int,int>;
#define f first
#define s second

mt19937 rng(time(0));

struct treap{
  struct node{
    int h,sz,prio;
    deque<pii> lz;
    node *l,*r;
    node(int h):h(h),sz(1),prio(rng()),l(nullptr),r(nullptr){}
    void add(int opr,int h2){
      while(lz.size()&&lz.back().f==opr){
        if(opr==1&&h2<=lz.back().s || opr==2&&h2>=lz.back().s) return;
        lz.pop_back();
      }
      lz.eb(opr,h2);
    }
  };
  using pnode=node*;
  pnode rt;
  treap():rt(nullptr){}
  int sz(pnode t){return t?t->sz:0;}
  void flush(pnode t){
    if(!t||t->lz.empty()) return;
    while(t->lz.size()){
      auto [opr,h]=t->lz.front();
      t->lz.pop_front();
      if(opr==1) t->h=max(t->h,h);
      else t->h=min(t->h,h);
      if(t->l) t->l->add(opr,h);
      if(t->r) t->r->add(opr,h);
    }
  }
  void upd(pnode t){
    if(!t) return;
    flush(t->l), flush(t->r);
    t->sz=sz(t->l)+1+sz(t->r);
  }
  void split(pnode t,pnode &l,pnode &r,int x){
    flush(t);
    if(!t) return void(l=r=nullptr);
    if(sz(t->l)>=x) split(t->l,l,t->l,x),r=t;
    else split(t->r,t->r,r,x-sz(t->l)-1),l=t;
    upd(t);
  }
  void merge(pnode &t,pnode l,pnode r){
    flush(l), flush(r);
    if(!l||!r) return void(t=l?l:r);
    if(l->prio>r->prio) merge(l->r,l->r,r),t=l;
    else merge(r->l,l,r->l),t=r;
    upd(t);
  }
  void insert(int h){merge(rt,rt,new node(h));}
  void upd(int l,int r,int opr,int h){
    pnode t1,t2,t3;
    split(rt,t1,t2,l-1);
    split(t2,t2,t3,r-l+1);
    t2->add(opr,h);
    flush(t2);
    merge(rt,t1,t2);
    merge(rt,rt,t3);
  }
  void print(int *itr){
    function<void(pnode)> dfs=[&](pnode t){
      flush(t);
      if(!t) return;
      dfs(t->l);
      *itr=t->h;
      ++itr;
      dfs(t->r);
    };
    dfs(rt);
  }
}t;

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  for(int i=0;i<n;++i) t.insert(0);
  for(int i=0;i<k;++i) t.upd(left[i]+1,right[i]+1,op[i],height[i]);
  t.print(finalHeight);
}

Compilation message (stderr)

wall.cpp: In member function 'void treap::node::add(int, int)':
wall.cpp:19:18: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   19 |         if(opr==1&&h2<=lz.back().s || opr==2&&h2>=lz.back().s) return;
      |                  ^

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