Submission #1320291

#	Time	Username	Problem	Language	Result	Execution time	Memory
1320291		tsetsenbileg	Wall (IOI14_wall)	C++20	100 / 100	368 ms	86384 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
using pr = pair<int, int>;
const int INF = 1e9+7, MOD = 1e9+7;
vector<int> a;

struct segtree{
  vector<int> st, up, down;
  int n;
  void init(int N) {
    n = N;
    // st.assign(4*n, 0); 
    down.assign(4*n, 1e9 + 1);
    up.assign(4*n, -1);
  }
  int L(int i) {return i << 1;}
  int R(int i) {return i << 1 | 1;}

  void merge(int i, int op, int h) {
    if (op == 1) {
      if (up[i] < h) {
        up[i] = h;
        down[i] = max(down[i], h);
      }
    } else {
      if (down[i] > h) {
        down[i] = h;
        up[i] = min(up[i], h);
      }
    }
  }
  
  void push(int i, int l, int r) {
    if (up[i] == -1 && down[i] == 1e9 + 1) return;
    if (up[i] != -1) {
      merge(L(i), 1, up[i]);
      merge(R(i), 1, up[i]);
    }
    if (down[i] != 1e9 + 1) {
      merge(L(i), 2, down[i]);
      merge(R(i), 2, down[i]);
    }
    down[i] = 1e9 + 1;
    up[i] = -1;
  }

  void update(int i, int l, int r, int ll, int rr, int op, int h) {
    if (ll == l && r == rr) {
      merge(i, op, h);
      return;
    }

    push(i, l, r);

    int m = (l + r) >> 1;
    if (rr <= m) update(L(i), l, m, ll, rr, op, h);
    else if (m + 1 <= ll) update(R(i), m+1, r, ll, rr, op, h);
    else {
      update(L(i), l, m, ll, m, op, h);
      update(R(i), m+1, r, m + 1, rr, op, h);
    }
  }

  void query(int i, int l, int r) {
    if (l == r) {
      a[l] = down[i];
      return;
    }
    push(i, l, r);
    int m = (l + r) >> 1;
    query(L(i), l, m);
    query(R(i), m + 1, r);
  }
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  segtree seg;
  a.resize(n+1);
  seg.init(n);
  seg.update(1, 1, n, 1, n, 1, 0);
  seg.update(1, 1, n, 1, n, 2, 0);
  for (int i = 0; i < k; i++) {
    seg.update(1, 1, n, left[i]+1, right[i]+1, op[i], height[i]);
    // seg.query(1, 1, n);
  // for (int j = 0; j < n; j++) {
  //   finalHeight[j] = a[j+1];
  // }
  // for (int j = 1; j <= n; j++)
  //   cout << j << ' ' << a[j] << '\n';
  }
  seg.query(1, 1, n);
  for (int i = 0; i < n; i++) {
    finalHeight[i] = a[i+1];
  }
  return;
}

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