Submission #492665

#	Time	Username	Problem	Language	Result	Execution time	Memory
492665		boykut	Wall (IOI14_wall)	C++17	8 / 100	201 ms	14384 KiB

wall

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

using namespace std;

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 {
    struct query {
      int l, r, h;
    };
    int sq = sqrt(n);
    vector<query> q;

    // OPERATION 1
    int i = 0;
    for (; i < k; i++) {
      if (op[i] == 2) break;
      q.push_back({left[i], right[i], height[i]});
    }
    sort(q.begin(), q.end(), [&](query a, query b) {
      if (a.l / sq == b.l / sq) return a.r < b.r;
      return a.l / sq < b.l / sq;
    });
    int l = 0, r = 0;
    for (auto [vl, vr, vh] : q) {
      while (r < vr) {
        r++;
        finalHeight[r] = max(finalHeight[r], vh);
      }
      while (l > vl) {
        l--;
        finalHeight[l] = max(finalHeight[l], vh);
      }
      while (r > vr) {
        r--;
      }
      while (l < vl) {
        l++;
      }
    }

    // OPERATION 2
    while (!q.empty()) q.pop_back();
    for (; i < k; i++) {
      q.push_back({left[i], right[i], height[i]});
    }
    sort(q.begin(), q.end(), [&](query a, query b) {
      if (a.l / sq == b.l / sq) return a.r < b.r;
      return a.l / sq < b.l / sq;
    });
    l = 0, r = 0;
    for (auto [vl, vr, vh] : q) {
      while (r < vr) {
        r++;
        finalHeight[r] = min(finalHeight[r], vh);
      }
      while (l > vl) {
        l--;
        finalHeight[l] = min(finalHeight[l], vh);
      }
      while (r > vr) {
        r--;
      }
      while (l < vl) {
        l++;
      }
    }
  }
  return;
}

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