Submission #1307251

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307251		Leyna	Wall (IOI14_wall)	C++20	24 / 100	151 ms	10288 KiB

wall

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

using namespace std;

vector<int> segtree;

void add(int l, int r, int val){
  while (l <= r){
    if (l%2 == 1) {
      segtree[l] = max(val, segtree[l]);
      l++;
    }
    if (r%2 == 0){
      segtree[r] = max(val, segtree[r]);
      r--;
    }
    l /= 2;
    r /= 2;
  }
}

void remove(int l, int r, int val){
  while (l <= r){
    if (l%2 == 1) {
      segtree[l] = min(val, segtree[l]);
      l++;
    }
    if (r%2 == 0){
      segtree[r] = min(val, segtree[r]);
      r--;
    }
    l /= 2;
    r /= 2;
  }
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  int zp = (int)(1 << (int)ceil(log2(n)));
  //cerr << zp << endl;
  segtree.resize(2*zp);
  int i;
  for (i=0; i<k; i++){
    if (op[i] == 2) break;
    add(left[i]+zp, right[i]+zp, height[i]);
  }
  for (int j=1; j<zp; j++){
    segtree[j*2] = max(segtree[j*2], segtree[j]);
    segtree[j*2+1] = max(segtree[j*2+1], segtree[j]);
    segtree[j] = 1e9;
  }
  for (;i<k; i++){
    remove(left[i]+zp, right[i]+zp, height[i]);
  }
  for (int j=1; j<zp; j++){
    segtree[j*2] = min(segtree[j*2], segtree[j]);
    segtree[j*2+1] = min(segtree[j*2+1], segtree[j]);
    segtree[j] = 0;
  }
  for (int j=0; j<n; j++){
    finalHeight[j] = segtree[j+zp];
  }

  return;
}

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