Submission #990087

#	Time	Username	Problem	Language	Result	Execution time	Memory
990087		huutuan	Wall (IOI14_wall)	C++14	100 / 100	377 ms	99568 KiB

wall

#include "wall.h"

#include <bits/stdc++.h>

using namespace std;

const int inf=1e9;

struct SegmentTree{
   int n;
   vector<pair<int, int>> t;
   void init(int _n){
      n=_n;
      t.assign(4*n+1, {-inf, inf});
   }
   void build(int k, int l, int r){
      if (l==r){
         t[k]={0, 0};
         return;
      }
      int mid=(l+r)>>1;
      build(k<<1, l, mid);
      build(k<<1|1, mid+1, r);
   }
   void apply(int k, pair<int, int> val){
      if (t[k].second<val.first) t[k]={val.first, val.first};
      else if (t[k].first>val.second) t[k]={val.second, val.second};
      else t[k]={max(t[k].first, val.first), min(t[k].second, val.second)};
   }
   void push(int k){
      if (t[k]!=pair<int, int>{-inf, inf}){
         apply(k<<1, t[k]);
         apply(k<<1|1, t[k]);
         t[k]={-inf, inf};
      }
   }
   void update(int k, int l, int r, int L, int R, pair<int, int> val){
      if (r<L || R<l) return;
      if (L<=l && r<=R){
         apply(k, val);
         return;
      }
      push(k);
      int mid=(l+r)>>1;
      update(k<<1, l, mid, L, R, val);
      update(k<<1|1, mid+1, r, L, R, val);
   }
   void get_all(int k, int l, int r, int ans[]){
      if (l==r){
         ans[l]=t[k].first;
         return;
      }
      push(k);
      int mid=(l+r)>>1;
      get_all(k<<1, l, mid, ans);
      get_all(k<<1|1, mid+1, r, ans);
   }
} st;

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
   st.init(n);
   st.build(1, 0, n-1);
   for (int i=0; i<k; ++i){
      int l=left[i], r=right[i], h=height[i];
      int lg=__lg(r-l+1);
      if (op[i]==1){
         st.update(1, 0, n-1, l, r, {h, inf});
      }else{
         st.update(1, 0, n-1, l, r, {-inf, h});
      }
   }
   st.get_all(1, 0, n-1, finalHeight);
   return;
}

Compilation message (stderr)

wall.cpp: In function 'void buildWall(int, int, int*, int*, int*, int*, int*)':
wall.cpp:65:11: warning: unused variable 'lg' [-Wunused-variable]
   65 |       int lg=__lg(r-l+1);
      |           ^~

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