oj.uz

Submission #942926

# Submission time Handle Problem Language Result Execution time Memory
942926 2024-03-11T07:00:16 Z kim Wall (IOI14_wall) C++17
8 / 100
 3000 ms 90412 KB 
#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

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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 2 ms 344 KB Output is correct
3 Correct 4 ms 708 KB Output is correct
4 Correct 92 ms 12732 KB Output is correct
5 Correct 119 ms 12880 KB Output is correct
6 Correct 122 ms 12896 KB Output is correct

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 121 ms 14048 KB Output is correct
3 Correct 590 ms 19428 KB Output is correct
4 Execution timed out 3069 ms 90060 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 4 ms 696 KB Output is correct
4 Correct 98 ms 12832 KB Output is correct
5 Correct 121 ms 12884 KB Output is correct
6 Correct 120 ms 12848 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 118 ms 14040 KB Output is correct
9 Correct 660 ms 20912 KB Output is correct
10 Execution timed out 3065 ms 90412 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 2 ms 600 KB Output is correct
3 Correct 4 ms 604 KB Output is correct
4 Correct 85 ms 12740 KB Output is correct
5 Correct 122 ms 12824 KB Output is correct
6 Correct 121 ms 12804 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 124 ms 14052 KB Output is correct
9 Correct 650 ms 20656 KB Output is correct
10 Execution timed out 3051 ms 90296 KB Time limit exceeded
11 Halted 0 ms 0 KB -