Submission #229488

#	Time	Username	Problem	Language	Result	Execution time	Memory
229488		tushar_2658	Wall (IOI14_wall)	C++14	0 / 100	238 ms	71032 KiB

wall

#include "wall.h"
#include "bits/stdc++.h"
using namespace std;

const int maxn = 2000005;
int N, K;
int lazy[maxn << 2][2], t[maxn << 2];

void push_down(int node, int b, int e){
  t[node] = min(lazy[node][0], t[node]);
  t[node] = max(lazy[node][1], t[node]);
  if(b != e){
    lazy[2*node][0] = min(lazy[2*node][0], lazy[node][0]);
    lazy[2*node + 1][0] = min(lazy[2*node + 1][0], lazy[node][0]);
    lazy[2*node][1] = max(lazy[2*node][1], lazy[node][1]);
    lazy[2*node + 1][1] = max(lazy[2*node + 1][1], lazy[node][1]);
  }
  lazy[node][0] = INT_MAX;
  lazy[node][1] = INT_MIN;
}

void upd(int node, int b, int e, int i, int j, int val, int id){
  push_down(node, b, e);
  if(i > e || j < b)return;
  if(b >= i && j >= e){
    if(id == 1){
      t[node] = max(t[node], val);
      if(b != e){
        lazy[2*node][1] = max(lazy[2*node][1], val);
        lazy[2*node + 1][1] = max(lazy[2*node + 1][1], val);
      }
    }else {
      t[node] = min(t[node], val);
      if(b != e){
        lazy[2*node][0] = min(lazy[2*node][0], val);
        lazy[2*node + 1][0] = min(lazy[2*node + 1][0], val);
      }
    }
    return;
  }
  int mid = (b + e) >> 1;
  upd(2*node, b, mid, i, j, val, id);
  upd(2*node + 1, mid + 1, e, i, j, val, id);
}

int query(int node, int b, int e, int i){
  if(b == e){
    push_down(node, b, e);
    return t[node];
  }else {
    push_down(node, b, e);
    int mid = (b + e) >> 1;
    if(i <= mid){
      return query(2*node, b, mid, i);
    }else {
      return query(2*node + 1, mid + 1, e, i);
    }
  }
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  N = n, K = k;
  for(int i = 0; i < (maxn << 2); ++i){
    lazy[i][0] = INT_MAX;
    lazy[i][1] = INT_MIN;
  }
  for(int i = 0; i < K; ++i){
    upd(1, 1, N, left[i] + 1, right[i] + 1, height[i], op[i]);
  }
  for(int i = 1; i <= N; ++i){
    finalHeight[i - 1] = query(1, 1, N, i);
  }

  return;
}

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