Submission #591858

#	Time	Username	Problem	Language	Result	Execution time	Memory
591858		Shreyan_Paliwal	Wall (IOI14_wall)	C++17	100 / 100	760 ms	69468 KiB

wall

#include "wall.h"

#include <bits/stdc++.h>

using namespace std;

#define MAX(a, b) a = max(a, b)
#define MIN(a, b) a = min(a, b)

const int INF  = 2000000000;
const int maxn = 2000000;
const int segn = (1 << 22);

int  seg[segn][2];
void addlower(int p, int l, int r, int k) {
  MAX(seg[p][0], k);
  MAX(seg[p][1], k);
}
void addupper(int p, int l, int r, int k) {
  MIN(seg[p][1], k);
  MIN(seg[p][0], seg[p][1]);
}
void push(int p, int l, int r) {
  if (seg[p][0] == seg[p][1] && seg[p][1] == INF) return;
  if (l == r) return;
  int mid = (l + r) >> 1;
  addlower((p << 1), l, mid, seg[p][0]);
  addlower((p << 1) | 1, mid + 1, r, seg[p][0]);

  addupper((p << 1), l, mid, seg[p][1]);
  addupper((p << 1) | 1, mid + 1, r, seg[p][1]);

  seg[p][0] = 0, seg[p][1] = INF;
}
void upd(int p, int l, int r, int L, int R, int K, char C) {
  push(p, l, r);
  if (r < L || R < l) return;
  if (L <= l && r <= R) {
    (C == 'L' ? addlower(p, l, r, K) : addupper(p, l, r, K));
    return;
  }
  int mid = (l + r) >> 1;
  upd(p << 1, l, mid, L, R, K, C);
  upd((p << 1) | 1, mid + 1, r, L, R, K, C);
}
void finalize(int p, int l, int r, int finalHeight[]) {
  push(p, l, r);
  if (l == r) {
    finalHeight[l] = seg[p][0];
    return;
  }
  int mid = (l + r) >> 1;
  finalize(p << 1, l, mid, finalHeight);
  finalize((p << 1) | 1, mid + 1, r, finalHeight);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
  for (int i = 0; i < segn; i++) seg[i][0] = 0, seg[i][1] = INF;

  for (int i = 0; i < k; i++)
    if (op[i] == 1)
      upd(1, 0, n - 1, left[i], right[i], height[i], 'L');
    else
      upd(1, 0, n - 1, left[i], right[i], height[i], 'U');

  finalize(1, 0, n - 1, finalHeight);
}

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