Submission #169424

#	Time	Username	Problem	Language	Result	Execution time	Memory
169424		AlexLuchianov	Wall (IOI14_wall)	C++14	100 / 100	1182 ms	89272 KiB

wall

#include "wall.h"
#include <vector>

using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

int const nmax = 100000;
int const inf = 1000000000;

struct Node{
  int from;
  int to;
  Node(int from = 0, int to = inf){
    this->from = from;
    this->to = to;
  }
  Node operator + (Node const &a) const{
    Node result;
    if(a.to <= from)
      return {from, from};
    else if(to <= a.from)
      return {to, to};
    else
      return {MAX(from, a.from), MIN(to, a.to)};
  }
};

class SegmentTree{
private:
  std::vector<Node> aint;
public:
  SegmentTree(int n){
    aint.resize(4 * n);
  }
  void cleannode(int node, int from, int to){
    if(from < to){
      int mid = (from + to) / 2;
      aint[node * 2] = aint[node] + aint[node * 2];
      aint[node * 2 + 1] = aint[node] + aint[node * 2 + 1];
      aint[node] = {0, inf};
    }
  }

  void build(int node, int from, int to){
    if(from < to){
      int mid = (from + to) / 2;
      build(node * 2, from, mid);
      build(node * 2 + 1, mid + 1, to);
    } else
      aint[node] = {0, 0};
  }

  void update(int node, int from, int to, int x, int y, Node val){
    cleannode(node, from, to);
    if(from == x && to == y)
      aint[node] = val + aint[node];
    else {
      int mid = (from + to) / 2;
      if(x <= mid)
        update(node * 2, from, mid, x, MIN(mid, y), val);
      if(mid + 1 <= y)
        update(node * 2 + 1, mid + 1, to, MAX(mid + 1, x), y, val);
    }
  }
  Node query(int node, int from, int to, int x){
    cleannode(node, from, to);
    if(from < to){
      int mid = (from + to) / 2;
      if(x <= mid)
        return query(node * 2, from, mid, x);
      else
        return query(node * 2 + 1, mid + 1, to, x);
    } else
      return aint[node];
  }
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  SegmentTree aint(n);
  aint.build(1, 0, n - 1);
  for(int i = 0; i < k; i++)
    if(op[i] == 1)
      aint.update(1, 0, n - 1, left[i], right[i], {height[i], inf});
    else
      aint.update(1, 0, n - 1, left[i], right[i], {0, height[i]});
  for(int i = 0; i < n; i++)
    finalHeight[i] = aint.query(1, 0, n - 1, i).from;
  return;
}

/*
10 3
1 3 4 91220
1 5 9 48623
2 3 5 39412
*/

Compilation message (stderr)

wall.cpp: In member function 'void SegmentTree::cleannode(int, int, int)':
wall.cpp:38:11: warning: unused variable 'mid' [-Wunused-variable]
       int mid = (from + to) / 2;
           ^~~

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