Submission #1089195

#	Time	Username	Problem	Language	Result	Execution time	Memory
1089195		LucasLe	Wall (IOI14_wall)	C++17	100 / 100	1786 ms	44624 KiB

wall

#pragma GCC optimize("O3,unroll-loops")

#include <bits/stdc++.h>
 
#define                pii  pair<int, int>
#define                 fi  first
#define                 se  second
#define                 ld  long double
#define                 vi  vector<int>
#define                vii  vector<vector<int>>
#define             all(v)  (v).begin(), (v).end()
#define       rep(i, a, b)  for (int i = (a), _b = (b); i <= _b; ++i)
#define       per(i, b, a)  for (int i = (b), _a = (a); i >= _a; --i)
 
using namespace std;
 
const int MOD = 1e9 + 7;
 
int add(int a, int b) {
  a += b;
  if (a >= MOD) a -= MOD;
  return a;
}
 
int mul(int a, int b) {
  (a *= b) %= MOD;
  return a;
}
 
int ceil(int x, int y) {
  return (x + y - 1) / y;
}
 
int bin_pow(int x, int y) {
  int res = 1;
  while (y) {
    if (y & 1) res = res * x % MOD;
    x = x * x % MOD;
    y >>= 1;
  }
  return res;
}
 
template<class T> bool minimize(T& a, T b) {
  if (a > b) return a = b, true;
  return false;
}
 
template<class T> bool maximize(T& a, T b) {
  if (a < b) return a = b, true;
  return false;
}
 
const int maxn = 2e6 + 5;
const int SIZE = 1415;
 
int n, q;
int a[maxn + 5];
int left_bound[SIZE + 5], right_bound[SIZE + 5];
int moonx[SIZE + 5], moony[SIZE + 5];
 
void updatefull(int t, int x, int h) {
  if (t == 1) {
    moony[x] = max(moony[x], h);
    moonx[x] = max(moonx[x], h);
  } else {
    moonx[x] = min(moonx[x], h);
    moony[x] = min(moony[x], h);
  }
}
 
void updatemanual(int t, int x, int l, int r, int h) {
  for (int i = left_bound[x]; i <= right_bound[x]; ++i) {
    a[i] = min(a[i], moonx[x]);
    a[i] = max(a[i], moony[x]);
  }
  for (int i = l; i <= r; ++i) {
    if (t == 1) {
      a[i] = max(a[i], h);
    } else {
      a[i] = min(a[i], h);
    }
  }
  moonx[x] = (moony[x] = a[left_bound[x]]);
  for (int i = left_bound[x]; i <= right_bound[x]; ++i) {
    moonx[x] = max(a[i], moonx[x]);
    moony[x] = min(a[i], moony[x]);
  }
}
 
void buildWall(int N, int K, int op[], int left[], int right[], int height[], int finalHeight[]) {
  n = N, q = K;
  for (int i = 1; i <= n; ++i) {
    int x = ceil(i, SIZE);
    left_bound[x] = n + 1;
  }
  for (int i = 1; i <= n; ++i) {
    int x = ceil(i, SIZE);
    left_bound[x] = min(left_bound[x], i);
    right_bound[x] = i;
  }
  for (int _ = 0; _ < q; ++_) {
    int t, l, r, h;
    t = op[_];
    l = left[_] + 1;
    r = right[_] + 1;
    h = height[_];
    int block_l = ceil(l, SIZE);
    int block_r = ceil(r, SIZE);
    for (int i = block_l + 1; i <= block_r - 1; ++i)
      updatefull(t, i, h);
    if (block_l == block_r) { 
      updatemanual(t, block_l, l, r, h);
    } else {
      updatemanual(t, block_l, l, right_bound[block_l], h);
      updatemanual(t, block_r, left_bound[block_r], r, h);
    }
  }
  for (int i = 1; i <= n; ++i) {
    int x = ceil(i, SIZE);
    if (moonx[x] != -1 && a[i] > moonx[x]) a[i] = moonx[x];
    if (moony[x] != -1 && a[i] < moony[x]) a[i] = moony[x];
    finalHeight[i - 1] = a[i];
  }
}

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