Submission #1009193

#	Time	Username	Problem	Language	Result	Execution time	Memory
1009193		SonicML	Wall (IOI14_wall)	C++14	0 / 100	3066 ms	14048 KiB

wall

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

using namespace std;

int const INF = 1e5;

struct Node {
  int minn;
  int maxx;
};

Node combineNode(Node a, Node b) {
  Node c;
  c.minn = min(b.maxx, max(a.minn, b.minn));
  c.maxx = max(b.minn, min(a.maxx, b.maxx));
  return c;
}

struct SegmentTree {
  vector <Node> seg;

  SegmentTree(int n) {
    seg.resize(1 + 4 * n);
    for(int i = 1;i <= 4 * n;i++) {
      seg[i] = {0, INF};
    }
  }

  void cleanNode(int node, int from, int to) {
    if(from != to) {
      seg[node * 2] = combineNode(seg[node * 2], seg[node]);
      seg[node * 2 + 1] = combineNode(seg[node * 2 + 1], seg[node]);
      seg[node] = {0, INF};
    }
  }

  void update(int node, int from, int to, int x, int y, Node add) {
    if(from == x && to == y) {
      seg[node] = combineNode(seg[node], add);
      cleanNode(node, from, to);
    } else {
      int mid = (from + to) / 2;
      cleanNode(node * 2, from, mid);
      cleanNode(node * 2 + 1, mid+1, to);
      if(y <= mid) {
        update(node * 2, from, mid, x, y, add);
      } else if(mid < x) {
        update(node * 2 + 1, mid+1, to, x, y, add);
      } else {
        update(node * 2, from, mid, x, mid, add);
        update(node * 2 + 1, mid+1, to, mid+1, y, add);
      }
    }
  }

  Node query(int node, int from, int to, int x) {
    cleanNode(node, from, to);
    if(from == to) {
      return seg[node];
    } else {
      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); 
      }
    }
  }
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
  SegmentTree seg(n);
  seg.update(1, 1, n, 1, n, {0, 0});
  for(int j = 1;j <= n;j++) {
    Node print = seg.query(1, 1, n, j);
  }
  for(int i = 0;i < k;i++) {
    int x = left[i]+1, y = right[i]+1;
    Node add;
    if(op[i] == 1) {
      add = {height[i], INF};
    } else {
      add = {0, height[i]};
    }
    seg.update(1, 1, n, x, y, add);
    for(int j = 1;j <= n;j++) {
      Node print = seg.query(1, 1, n, j);
    }
  }
  for(int i = 0;i < n;i++) {
    finalHeight[i] = seg.query(1, 1, n, i+1).minn;
  }
  return;
}
  

Compilation message (stderr)

wall.cpp: In function 'void buildWall(int, int, int*, int*, int*, int*, int*)':
wall.cpp:77:10: warning: variable 'print' set but not used [-Wunused-but-set-variable]
   77 |     Node print = seg.query(1, 1, n, j);
      |          ^~~~~
wall.cpp:89:12: warning: variable 'print' set but not used [-Wunused-but-set-variable]
   89 |       Node print = seg.query(1, 1, n, j);
      |            ^~~~~

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