Submission #492686

#	Time	Username	Problem	Language	Result	Execution time	Memory
492686		boykut	Wall (IOI14_wall)	C++17	8 / 100	209 ms	12468 KiB

wall

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

using namespace std;

struct SegmentTreeMax {
   int n;
   vector<int> t, lazy;
   SegmentTreeMax(int n) : n(n), t((n << 2) + 1, 0), lazy((n << 2) + 1, -1) {}
   void propogate(int v, int vl, int vr) {
      if (lazy[v] == -1) return;
      t[v] = lazy[v];
      if (vl != vr) {
         lazy[2 * v + 1] = lazy[2 * v + 2] = lazy[v];
      }
      lazy[v] = -1;
   }
   void update(int l, int r, int x, int v, int vl, int vr) {
      propogate(v, vl, vr);
      if (l > vr || vl > r) return;
      else if (l <= vl && vr <= r) {
         lazy[v] = x;
         propogate(v, vl, vr);
      } else {
         int vm = (vl + vr) >> 1;
         update(l, r, x, v << 1, vl, vm);
         update(l, r, x, v << 1 | 1, vm + 1, vr);
         t[v] = max(t[v << 1], t[v << 1 | 1]);
      }
   }
   int query(int l, int r, int v, int vl, int vr) {
      propogate(v, vl, vr);
      if (l > vr || vl > r) return INT_MIN;
      else if (l <= vl && vr <= r) return t[v];
      else {
         int vm = (vl + vr) >> 1;
         int L = query(l, r, v << 1, vl, vm);
         int R = query(l, r, v << 1 | 1, vm + 1, vr);
         t[v] = max(t[v << 1], t[v << 1 | 1]);
         return max(L, R);
      }
   }
   void update(int l, int r, int x) {
      update(l, r, x, 1, 0, n - 1);
   }
   int query(int l, int r) {
      return query(l, r, 1, 0, n - 1);
   }
};

struct SegmentTreeMin {
   int n;
   vector<int> t, lazy;
   SegmentTreeMin(int n) : n(n), t((n << 2) + 1, INT_MAX), lazy((n << 2) + 1, -1) {}
   void propogate(int v, int vl, int vr) {
      if (lazy[v] == -1) return;
      t[v] = lazy[v];
      if (vl != vr) {
         lazy[2 * v + 1] = lazy[2 * v + 2] = lazy[v];
      }
      lazy[v] = -1;
   }
   void update(int l, int r, int x, int v, int vl, int vr) {
      propogate(v, vl, vr);
      if (l > vr || vl > r) return;
      else if (l <= vl && vr <= r) {
         lazy[v] = x;
         propogate(v, vl, vr);
      } else {
         int vm = (vl + vr) >> 1;
         update(l, r, x, v << 1, vl, vm);
         update(l, r, x, v << 1 | 1, vm + 1, vr);
         t[v] = min(t[v << 1], t[v << 1 | 1]);
      }
   }
   int query(int l, int r, int v, int vl, int vr) {
      propogate(v, vl, vr);
      if (l > vr || vl > r) return INT_MAX;
      else if (l <= vl && vr <= r) return t[v];
      else {
         int vm = (vl + vr) >> 1;
         int L = query(l, r, v << 1, vl, vm);
         int R = query(l, r, v << 1 | 1, vm + 1, vr);
         t[v] = min(t[v << 1], t[v << 1 | 1]);
         return min(L, R);
      }
   }
   void update(int l, int r, int x) {
      update(l, r, x, 1, 0, n - 1);
   }
   int query(int l, int r) {
      return query(l, r, 1, 0, n - 1);
   }
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  for (int i = 0; i < n; i++) 
    finalHeight[i] = 0;
  if (n <= 10000 && k <= 5000) {
    for (int i = 0; i < k; i++) {
      for (int j = left[i]; j <= right[i]; j++) {
        if (op[i] == 1) finalHeight[j] = max(finalHeight[j], height[i]);
        else finalHeight[j] = min(finalHeight[j], height[i]);
      }
    }
  } else {
    int m = 0; while (op[m] == 1 && m < k) m++;
    
    SegmentTreeMax mx(n);
    SegmentTreeMin mn(n);

    // #1
    vector<pair<int, int>> q;
    for (int i = 0; i < m; i++) {
      q.push_back({height[i], i});
    }
    sort(q.begin(), q.end());
    for (auto [noneed, i] : q) {
      mx.update(left[i], right[i], height[i]);
    }
    //
    for (int i = 0; i < n; i++) {
      mn.update(i, i, mx.query(i, i));
    }
    // #2
    while (!q.empty()) q.pop_back();
    for (int i = m; i < k; i++) {
      q.push_back({height[i], i});
    }
    sort(q.rbegin(), q.rend());
    for (auto [noneed, i] : q) {
      mn.update(left[i], right[i], height[i]);
    }
    for (int i = 0; i < n; i++) {
      finalHeight[i] = mn.query(i, i);
    }
  }
  return;
}

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