Submission #959634

#	Time	Username	Problem	Language	Result	Execution time	Memory
959634		vjudge1	Wall (IOI14_wall)	C++17	32 / 100	3086 ms	21472 KiB

wall

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

const int N = 2e6+6, inf = INT_MAX;

struct node {
  int mx, mn;
};

int n, lazMx[N*4], lazMn[N*4];
node seg[N*4];

void build(int p=1, int l=0, int r=n-1) {
  //lazMx[p] = -inf;
  //lazMn[p] = inf;
  if (l == r) {
    seg[p].mx = 0;
    seg[p].mn = 0;
    return;
  }
  int mid = (l+r) >> 1;
  seg[p].mx = seg[p].mn = 0;
}

/*
void pushDown(int p) {
  for (int h : {p*2, p*2+1}) {
    if (lazMx[p] != -inf) {
      seg[h].mx = max(seg[h].mx, lazMx[p]);
      seg[h].mn = max(seg[h].mn, lazMx[p]);
      lazMx[h] = max(lazMx[h], lazMx[p]);
      if (lazMn[h] <= lazMx[p]) lazMn[h] = inf;
    }

    if (lazMn[p] != inf) {
      seg[h].mx = min(seg[h].mx, lazMn[p]);
      seg[h].mn = min(seg[h].mn, lazMn[p]);
      lazMn[h] = min(lazMn[h], lazMn[p]);
      if (lazMx[h] >= lazMn[p]) lazMx[h] = -inf;
    }
  }
  lazMx[p] = -inf;
  lazMn[p] = inf;
}
*/

void updateMx(int a, int b, int c, int p=1, int l=0, int r=n-1) {
  if (seg[p].mn >= c) return;
  else if (a <= l && r <= b) {
    seg[p].mx = max(seg[p].mx, c);
    seg[p].mn = max(seg[p].mn, c); 
    //lazMx[p] = max(lazMx[p], c);
    //if (lazMn[p] <= lazMx[p]) lazMn[p] = inf;
    if (l == r) return;
  }
  //pushDown(p);
  int mid = (l+r) >> 1;
  if (a <= mid) updateMx(a, b, c, p*2, l, mid);
  if (mid+1 <= b) updateMx(a, b, c, p*2+1, mid+1, r);
  seg[p].mx = max(seg[p*2].mx, seg[p*2+1].mx);
  seg[p].mn = min(seg[p*2].mn, seg[p*2+1].mn);
}

void updateMn(int a, int b, int c, int p=1, int l=0, int r=n-1) {
  if (seg[p].mx <= c) return;
  else if (a <= l && r <= b) {
    seg[p].mx = min(seg[p].mx, c);
    seg[p].mn = min(seg[p].mn, c); 
    //lazMn[p] = min(lazMn[p], c);
    //if (lazMx[p] >= lazMn[p]) lazMx[p] = -inf;
    if (l == r) return;
  }
  //pushDown(p);
  int mid = (l+r) >> 1;
  if (a <= mid) updateMn(a, b, c, p*2, l, mid);
  if (mid+1 <= b) updateMn(a, b, c, p*2+1, mid+1, r);
  seg[p].mx = max(seg[p*2].mx, seg[p*2+1].mx);
  seg[p].mn = min(seg[p*2].mn, seg[p*2+1].mn);
}

int query(int a, int p=1, int l=0, int r=n-1) {
  if (l == r) {
    return seg[p].mx;
  }
  //pushDown(p);
  int mid = (l+r) >> 1;
  if (a <= mid) return query(a, p*2, l, mid);
  else return query(a, p*2+1, mid+1, r);
}

void buildWall(int NN, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  n = NN;

  build();
  for (int i = 0; i < k; i++) {
    if (op[i] == 1) updateMx(left[i], right[i], height[i]);
    else updateMn(left[i], right[i], height[i]);
  }

  for (int i = 0; i < n; i++) {
    finalHeight[i] = query(i);
  }
}

Compilation message (stderr)

wall.cpp: In function 'void build(int, int, int)':
wall.cpp:22:7: warning: unused variable 'mid' [-Wunused-variable]
   22 |   int mid = (l+r) >> 1;
      |       ^~~

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