oj.uz

Submission #169424

# Submission time Handle Problem Language Result Execution time Memory
169424 2019-12-20T10:12:32 Z AlexLuchianov Wall (IOI14_wall) C++14
100 / 100
 1182 ms 89272 KB 
#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

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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 4 ms 376 KB Output is correct
3 Correct 4 ms 376 KB Output is correct
4 Correct 11 ms 760 KB Output is correct
5 Correct 8 ms 888 KB Output is correct
6 Correct 8 ms 760 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 182 ms 14072 KB Output is correct
3 Correct 208 ms 8008 KB Output is correct
4 Correct 631 ms 21264 KB Output is correct
5 Correct 334 ms 21928 KB Output is correct
6 Correct 325 ms 20348 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 4 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 10 ms 888 KB Output is correct
5 Correct 8 ms 760 KB Output is correct
6 Correct 8 ms 760 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 178 ms 14016 KB Output is correct
9 Correct 208 ms 8056 KB Output is correct
10 Correct 595 ms 21388 KB Output is correct
11 Correct 334 ms 21904 KB Output is correct
12 Correct 325 ms 20344 KB Output is correct
13 Correct 2 ms 256 KB Output is correct
14 Correct 178 ms 14028 KB Output is correct
15 Correct 49 ms 2040 KB Output is correct
16 Correct 865 ms 21276 KB Output is correct
17 Correct 346 ms 20828 KB Output is correct
18 Correct 341 ms 20856 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 4 ms 376 KB Output is correct
3 Correct 3 ms 380 KB Output is correct
4 Correct 10 ms 760 KB Output is correct
5 Correct 8 ms 888 KB Output is correct
6 Correct 8 ms 760 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 176 ms 14040 KB Output is correct
9 Correct 208 ms 8124 KB Output is correct
10 Correct 596 ms 21464 KB Output is correct
11 Correct 338 ms 21956 KB Output is correct
12 Correct 325 ms 20320 KB Output is correct
13 Correct 2 ms 256 KB Output is correct
14 Correct 184 ms 14044 KB Output is correct
15 Correct 48 ms 2168 KB Output is correct
16 Correct 863 ms 21496 KB Output is correct
17 Correct 344 ms 20800 KB Output is correct
18 Correct 340 ms 20724 KB Output is correct
19 Correct 1159 ms 89188 KB Output is correct
20 Correct 1133 ms 89124 KB Output is correct
21 Correct 1145 ms 89248 KB Output is correct
22 Correct 1136 ms 89200 KB Output is correct
23 Correct 1138 ms 89100 KB Output is correct
24 Correct 1165 ms 89272 KB Output is correct
25 Correct 1137 ms 89204 KB Output is correct
26 Correct 1182 ms 89156 KB Output is correct
27 Correct 1146 ms 89228 KB Output is correct
28 Correct 1134 ms 89200 KB Output is correct
29 Correct 1132 ms 89136 KB Output is correct
30 Correct 1135 ms 89196 KB Output is correct