Submission #923829

#	Time	Username	Problem	Language	Result	Execution time	Memory
923829		myst6	Wall (IOI14_wall)	C++14	100 / 100	936 ms	151848 KiB

wall

#include <bits/stdc++.h>

using namespace std;

#include "wall.h"

const int maxh = 500'005; 

struct Tag {
  int lo, hi;
  Tag(int _lo, int _hi) : lo(_lo), hi(_hi) {}
  Tag() : lo(0), hi(maxh) {}
  void apply(Tag &tag) {
    int newlo = min(max(lo, tag.lo), tag.hi);
    int newhi = max(min(hi, tag.hi), tag.lo);
    lo = newlo;
    hi = newhi;
  }
};

struct Tree {
  vector<Tag> tag, info;
  Tree(int size) { tag.resize(size*4); info.resize(size*4); }
  void pushdown(int x) {
    info[x].apply(tag[x]);
    if (x*2 < tag.size()) tag[x*2].apply(tag[x]);
    if (x*2+1 < tag.size()) tag[x*2+1].apply(tag[x]);
    tag[x] = {};
  }
  void update(int l, int r, int x, int xl, int xr, Tag delta) {
    if (l > r) return;
    pushdown(x); // order matters
    if (l == xl && r == xr) {
      tag[x].apply(delta);
    } else {
      int xm = (xl + xr) / 2;
      update(l, min(r, xm), x*2, xl, xm, delta);
      update(max(l, xm+1), r, x*2+1, xm+1, xr, delta);
      // there is no merging
    }
  }
  Tag query(int v, int x, int xl, int xr) {
    pushdown(x);
    if (xl == xr) {
      return info[x];
    } else {
      int xm = (xl + xr) / 2;
      if (v <= xm) return query(v, x*2, xl, xm);
      else return query(v, x*2+1, xm+1, xr);
    }
  }
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
  Tree tree(n);
  for (int i=0; i<k; i++) {
    if (op[i] == 1) {
      // adding phase
      tree.update(left[i], right[i], 1, 0, n-1, {height[i], maxh});
    } else {
      // removing phase
      tree.update(left[i], right[i], 1, 0, n-1, {0, height[i]});
    }
  }
  for (int i=0; i<n; i++) {
    Tag tag = tree.query(i, 1, 0, n-1);
    finalHeight[i] = tag.lo;
  }
}

Compilation message (stderr)

wall.cpp: In member function 'void Tree::pushdown(int)':
wall.cpp:26:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Tag>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     if (x*2 < tag.size()) tag[x*2].apply(tag[x]);
      |         ~~~~^~~~~~~~~~~~
wall.cpp:27:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Tag>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     if (x*2+1 < tag.size()) tag[x*2+1].apply(tag[x]);
      |         ~~~~~~^~~~~~~~~~~~

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