Submission #576095

#	Time	Username	Problem	Language	Result	Execution time	Memory
576095		SSRS	Wall (IOI14_wall)	C++14	100 / 100	795 ms	50264 KiB

wall

#include <bits/stdc++.h>
using namespace std;
const int INF = 100000;
struct monoid{
  int mn, mx;
  monoid(): mn(0), mx(INF){
  }
  monoid(int mn, int mx): mn(mn), mx(mx){
  }
};
monoid f(monoid B, monoid A){
  if (A.mx < B.mn){
    A.mn = B.mn;
    A.mx = B.mn;
  } else if (A.mn > B.mx){
    A.mn = B.mx;
    A.mx = B.mx;
  } else {
    A.mn = max(A.mn, B.mn);
    A.mx = min(A.mx, B.mx);
  }
  return A;
}
struct dual_segment_tree{
  int N;
  vector<monoid> ST;
  dual_segment_tree(int N2){
    N = 1;
    while (N < N2){
      N *= 2;
    }
    ST = vector<monoid>(N * 2 - 1);
    for (int i = 0; i < N2; i++){
      ST[N - 1 + i] = monoid(0, 0);
    }
  }
  void eval(int i){
    if (i < N - 1){
      ST[i * 2 + 1] = f(ST[i], ST[i * 2 + 1]);
      ST[i * 2 + 2] = f(ST[i], ST[i * 2 + 2]);
      ST[i] = monoid();
    }
  }
  void range_chmax(int L, int R, int x, int i, int l, int r){
    eval(i);
    if (r <= L || R <= l){
      return;
    } else if (L <= l && r <= R){
      ST[i] = f(monoid(x, INF), ST[i]);
    } else {
      int m = (l + r) / 2;
      range_chmax(L, R, x, i * 2 + 1, l, m);
      range_chmax(L, R, x, i * 2 + 2, m, r);
    }
  }
  void range_chmax(int L, int R, int x){
    range_chmax(L, R, x, 0, 0, N);
  }
  void range_chmin(int L, int R, int x, int i, int l, int r){
    eval(i);
    if (r <= L || R <= l){
      return;
    } else if (L <= l && r <= R){
      ST[i] = f(monoid(0, x), ST[i]);
    } else {
      int m = (l + r) / 2;
      range_chmin(L, R, x, i * 2 + 1, l, m);
      range_chmin(L, R, x, i * 2 + 2, m, r);
    }
  }
  void range_chmin(int L, int R, int x){
    range_chmin(L, R, x, 0, 0, N);
  }
  int operator [](int i){
    i += N - 1;
    monoid ans = ST[i];
    while (i > 0){
      i = (i - 1) / 2;
      ans = f(ST[i], ans);
    }
    assert(ans.mn == ans.mx);
    return ans.mn;
  }
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  dual_segment_tree ST(n);
  for (int i = 0; i < k; i++){
    right[i]++;
    if (op[i] == 1){
      ST.range_chmax(left[i], right[i], height[i]);
    }
    if (op[i] == 2){
      ST.range_chmin(left[i], right[i], height[i]);
    }
  }
  for (int i = 0; i < n; i++){
    finalHeight[i] = ST[i];
  }
}

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