Submission #52259

#	Time	Username	Problem	Language	Result	Execution time	Memory
52259		rondojim	Wall (IOI14_wall)	C++17	32 / 100	921 ms	153872 KiB

wall

#include "wall.h"
 
#include <bits/stdc++.h>
 
#define pb push_back
#define fr first
#define sc second
#define mk make_pair
 
using namespace std;
 
const int N = (int) 2e5 + 6;
 
int nn;
vector <pair<int,pair<int,int> > > add,cut;
vector <int> mx,mn;
 
struct node {
      int c,a;
      node () {
            c = 0,a = -1;
      }
}t[N * 4],tt[N * 4];
 
void push (int v,int tl,int tr) {
      if (t[v].a != -1 && tl < tr) {
            if (t[v + v].a == -1) t[v + v].a = t[v].a;
            if (t[v + v + 1].a == -1) t[v + v + 1].a = t[v].a;
            t[v].a = -1;
      }
}
void update (int l,int r,int h,int v = 1,int tl = 0,int tr = nn - 1) {
      push(v,tl,tr);
      if (tl > r || tr < l || t[v].a != -1)
            return;
      if (l <= tl && tr <= r) {
            t[v].a = h;
            push(v,tl,tr);
      }
      else {
            int tm = (tl + tr) >> 1;
            update (l,r,h,v + v,tl,tm);
            update (l,r,h,v + v + 1,tm + 1,tr);
 
            push(v,tl,tr);
            push(v + v,tl,tm);
            push(v + v + 1,tm + 1,tr);
      }
}
void push1(int v,int tl,int tr) {
      if (tt[v].a != -1 && tl < tr) {
            if (tt[v + v].a == -1) tt[v + v].a = tt[v].a;
            if (tt[v + v + 1].a == -1) tt[v + v + 1].a = tt[v].a;
            tt[v].a = -1;
      }
}
void update1 (int l,int r,int h,int v = 1,int tl = 0,int tr = nn - 1) {
      push1(v,tl,tr);
      if (tl > r || tr < l || tt[v].a != -1)
            return;
      if (l <= tl && tr <= r) {
            tt[v].a = h;
            push1(v,tl,tr);
      }
      else {
            int tm = (tl + tr) >> 1;
            update1 (l,r,h,v + v,tl,tm);
            update1 (l,r,h,v + v + 1,tm + 1,tr);
 
            push1(v,tl,tr);
            push1(v + v,tl,tm);
            push1(v + v + 1,tm + 1,tr);
      }
}
void init (int v = 1,int tl = 0,int tr = nn - 1) {
            push(v,tl,tr);
      if (tl == tr) {
            mx.pb(t[v].a);
      }
      else {
            int tm = (tl + tr) >> 1;
            init(v + v,tl,tm);
            init(v + v + 1,tm + 1,tr);
      }
}
void init1 (int v = 1,int tl = 0,int tr = nn - 1) {
      push1(v,tl,tr);
      if (tl == tr) {
            mn.pb(tt[v].a);
      }
      else {
            int tm = (tl + tr) >> 1;
            init1(v + v,tl,tm);
            init1(v + v + 1,tm + 1,tr);
      }
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
      nn = n;
      if (n <= 10000 && k <= 5000) {
            for (int i = 0; i < k; i ++) {
                  int type = op[i];
                  int l = left[i];
                  int r = right[i];
                  int h = height[i];
 
                  if (type == 1) {
                        for (int j = l; j <= r; j ++)
                              finalHeight[j] = max(finalHeight[j],h);
                  }
                  else {
                        for (int j = l; j <= r; j ++)
                              finalHeight[j] = min(finalHeight[j],h);
                  }
            }
      }
      else {
            for (int i = 0; i < k; i ++) {
                  int type = op[i];
                  int l = left[i];
                  int r = right[i];
                  int h = height[i];
                  if (type == 1) add.pb({h,{l,r}});
                  else cut.pb({h,{l,r}});
            }
            sort (add.rbegin(),add.rend());
            sort (cut.begin(),cut.end());
 
            for (auto to : add)
                  update (to.sc.fr,to.sc.sc,to.fr);
            for (auto to : cut)
                  update1 (to.sc.fr,to.sc.sc,to.fr);
 
            init();
            init1();
 
            for (int i = 0; i < nn; i ++) {
                  finalHeight[i] = 0;
                  if (mx[i] != -1) finalHeight[i] = mx[i];
                  if (mn[i] != -1) finalHeight[i] = min(mn[i],finalHeight[i]);
            }
      }
}

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