Submission #576081

#	Time	Username	Problem	Language	Result	Execution time	Memory
576081		SSRS	Wall (IOI14_wall)	C++14	24 / 100	302 ms	21412 KiB

wall

#include <bits/stdc++.h>
using namespace std;
const int INF = 100000;
struct dual_segment_tree_chmax{
  int N;
  vector<int> ST;
  dual_segment_tree_chmax(vector<int> A){
    int N2 = A.size();
    N = 1;
    while (N < N2){
      N *= 2;
    }
    ST = vector<int>(N * 2 - 1, 0);
    for (int i = 0; i < N2; i++){
      ST[N - 1 + i] = A[i];
    }
  }
  void range_chmax(int L, int R, int x, int i, int l, int r){
    if (r <= L || R <= l){
      return;
    } else if (L <= l && r <= R){
      ST[i] = max(ST[i], x);
    } 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);
  }
  int operator [](int i){
    i += N - 1;
    int ans = ST[i];
    while (i > 0){
      i = (i - 1) / 2;
      ans = max(ans, ST[i]);
    }
    return ans;
  }
};
struct dual_segment_tree_chmin{
  int N;
  vector<int> ST;
  dual_segment_tree_chmin(vector<int> A){
    int N2 = A.size();
    N = 1;
    while (N < N2){
      N *= 2;
    }
    ST = vector<int>(N * 2 - 1, INF);
    for (int i = 0; i < N2; i++){
      ST[N - 1 + i] = A[i];
    }
  }
  void range_chmin(int L, int R, int x, int i, int l, int r){
    if (r <= L || R <= l){
      return;
    } else if (L <= l && r <= R){
      ST[i] = min(ST[i], x);
    } 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;
    int ans = ST[i];
    while (i > 0){
      i = (i - 1) / 2;
      ans = min(ans, ST[i]);
    }
    return ans;
  }
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  for (int i = 0; i < k; i++){
    right[i]++;
  }
  vector<int> A(n, 0);
  dual_segment_tree_chmax ST1(A);
  for (int i = 0; i < k; i++){
    if (op[i] == 1){
      ST1.range_chmax(left[i], right[i], height[i]);
    }
  }
  for (int i = 0; i < n; i++){
    A[i] = ST1[i];
  }
  dual_segment_tree_chmin ST2(A);
  for (int i = 0; i < k; i++){
    if (op[i] == 2){
      ST2.range_chmin(left[i], right[i], height[i]);
    }
  }
  for (int i = 0; i < n; i++){
    finalHeight[i] = ST2[i];
  }
}

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