Submission #24156

#	Time	Username	Problem	Language	Result	Execution time	Memory
24156		Nirjhor	Wall (IOI14_wall)	C++14	100 / 100	959 ms	80160 KiB

wall

// IOI 2014 - Wall

#include <bits/stdc++.h>
#include "wall.h"

using namespace std;

typedef pair <int, int> node;

#define Min first
#define Max second

const int N = 2000010;
const int INF = 1e9 + 10;

node tree[4 * N];

void push (int u, int b, int e) {
  if (b == e) return;
  int l = u << 1, r = l | 1;
  tree[l].Min = min(tree[l].Min, tree[u].Min);
  tree[l].Min = max(tree[l].Min, tree[u].Max);
  tree[l].Max = min(tree[l].Max, tree[u].Min);
  tree[l].Max = max(tree[l].Max, tree[u].Max);
  tree[r].Min = min(tree[r].Min, tree[u].Min);
  tree[r].Min = max(tree[r].Min, tree[u].Max);
  tree[r].Max = min(tree[r].Max, tree[u].Min);
  tree[r].Max = max(tree[r].Max, tree[u].Max);
}

void update (int u, int b, int e, int from, int to, int v, int type) {
  push(u, b, e);
  if (b > to or e < from) return;
  if (b >= from and e <= to) {
    if (type) {
      tree[u].Min = min(tree[u].Min, v);
      tree[u].Max = min(tree[u].Max, v);
    } else {
      tree[u].Min = max(tree[u].Min, v);
      tree[u].Max = max(tree[u].Max, v);
    }
    return;
  }
  tree[u].Min = INF, tree[u].Max = -INF;
  int l = u << 1, r = l | 1, m = b + e >> 1;
  update(l, b, m, from, to, v, type);
  update(r, m + 1, e, from, to, v, type);
}

void traverse (int u, int b, int e, int res[]) {
  if (b == e) {
    res[b - 1] = tree[u].Min;
    return;
  }
  push(u, b, e);
  int l = u << 1, r = l | 1, m = b + e >> 1;
  traverse(l, b, m, res), traverse(r, m + 1, e, res);
}

void buildWall (int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
  for (int i = 0; i < k; ++i) {
    update(1, 1, n, left[i] + 1, right[i] + 1, height[i], op[i] - 1);
  }
  traverse(1, 1, n, finalHeight);
  return;
}

Compilation message (stderr)

wall.cpp: In function 'void update(int, int, int, int, int, int, int)':
wall.cpp:45:36: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int l = u << 1, r = l | 1, m = b + e >> 1;
                                    ^
wall.cpp: In function 'void traverse(int, int, int, int*)':
wall.cpp:56:36: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int l = u << 1, r = l | 1, m = b + e >> 1;
                                    ^

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