Submission #713026

#	Time	Username	Problem	Language	Result	Execution time	Memory
713026		garyye	Wall (IOI14_wall)	C++14	100 / 100	1262 ms	84504 KiB

wall

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

typedef pair<int, int> pii;
#define fi first
#define se second

const int ADD = 1;
const int DEL = 2;
const int N = 2e6 + 5;
const int INF = 1e9+10;

int mn[N * 4], mx[N * 4];
int* H;

// i <= j 
int clamp(int x, int i, int j) {
  return min(max(x, i), j);
}

void pull(int u) {
  int p = u >> 1;
  mx[u] = clamp(mx[u], mn[p], mx[p]);
  mn[u] = clamp(mn[u], mn[p], mx[p]);
}

void update(int u, int L, int R, int i, int j, int op, int x) {
  if(j < L || R < i) {
    return;
  }

  if(i <= L && R <= j) {
    if(op == ADD) {
      mn[u] = max(mn[u], x);
      mx[u] = max(mx[u], mn[u]);
    } else {
      mx[u] = min(mx[u], x);
      mn[u] = min(mn[u], mx[u]);
    }
    if(L == R) {
      H[L] = clamp(0, mn[u], mx[u]);
    }
  } else {
    int mid = (L + R) >> 1;

    pull(u * 2);
    pull(u * 2 + 1);
    mn[u] = 0, mx[u] = INF;

    update(u * 2, L, mid, i, j, op, x);
    update(u * 2 + 1, mid + 1, R, i, j, op, x);
  }
}



void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  fill(mx, mx + N * 4, 1e9 + 10);
  H = finalHeight;
  for(int i = 0; i < k; ++i) {
    update(1, 0, n - 1, left[i], right[i], op[i], height[i]);
  }
  for(int i = 0; i < n; ++i) {
    update(1, 0, n - 1, i, i, ADD, 0);
  }

}

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