Submission #1207475

#	Time	Username	Problem	Language	Result	Execution time	Memory
1207475		kilikuma	Wall (IOI14_wall)	C++20	0 / 100	358 ms	10672 KiB

wall

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

using namespace std; 

const int INF = (int) (1e5); 

pair<int, int> neutre() {
  return {0, INF}; 
}

pair<int, int> composi(pair<int, int> a, pair<int, int> b) {
  if (b.first == b.second) {
    int ham = max(min(b.first, a.second), a.first); 
    return {ham, ham}; 
  }
  if (a.first == a.second) {
    return a; 
  }
  if (b.first > a.second) {
    auto brr = neutre(); 
    brr.first = a.first; 
    return composi(brr, {a.second, a.second}); 
  }
  return {max(a.first, b.first), min(a.second, b.second)}; 
}

vector<pair<int, int>> seg; 

vector<int> sus; 

void apply(int node, int l, int r, int tl, int tr, pair<int, int> poudre) {

  if (l == r) 
    sus[l] = node; 
  if (l > r) 
    return; 
  if (tl > tr)
    return; 
  if (! ((l <= tl) && (tr <= r))) 
    return; 
  if ((l == tl) && (r == tr)) {
    seg[node] = composi(poudre, seg[node]); 
    return; 
  }
  int mid = (l + r) / 2; 
  seg[2 * node] = composi(seg[node], seg[2 * node]); 
  seg[2 * node + 1] = composi(seg[node], seg[2 * node + 1]); 
  seg[node] = neutre(); 
  apply(2 * node, l, mid, tl, min(mid, tr), poudre); 
  apply(2 * node + 1, mid + 1, r, max(mid + 1, tl), tr, poudre); 
  return; 

}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {

  

  seg.assign(2 * n + 1, neutre()); 

  sus.assign(n, 0); 

  for (int i = 0; i < n; i ++) 
    apply(1, 0, n - 1, i, i, {0, 0}); 

  for (int i = 0; i < k; i ++) {
    auto brr = neutre(); 
    if (op[i] == 1) 
      brr.first = height[i]; 
    else 
      brr.second = height[i]; 
    apply(1, 0, n - 1, left[i], right[i], brr);
  }

  for (int i = 0; i < n; i ++) 
    apply(1, 0, n - 1, i, i, neutre()); 

  for (int i = 0; i < n; i ++) 
    finalHeight[i] = seg[sus[i]].first; 

  return;
}

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