oj.uz

Submission #1009199

# Submission time Handle Problem Language Result Execution time Memory
1009199 2024-06-27T09:57:24 Z SonicML Wall (IOI14_wall) C++14
100 / 100
 701 ms 89088 KB 
#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 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 i = 0;i < n;i++) {
    finalHeight[i] = seg.query(1, 1, n, i+1).minn;
  }
  return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 372 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 4 ms 860 KB Output is correct
5 Correct 4 ms 860 KB Output is correct
6 Correct 4 ms 1112 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 76 ms 8260 KB Output is correct
3 Correct 113 ms 4308 KB Output is correct
4 Correct 305 ms 21264 KB Output is correct
5 Correct 191 ms 21748 KB Output is correct
6 Correct 182 ms 20308 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 4 ms 860 KB Output is correct
5 Correct 4 ms 860 KB Output is correct
6 Correct 4 ms 860 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 79 ms 13824 KB Output is correct
9 Correct 105 ms 8024 KB Output is correct
10 Correct 305 ms 21348 KB Output is correct
11 Correct 174 ms 21844 KB Output is correct
12 Correct 197 ms 20208 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 83 ms 13964 KB Output is correct
15 Correct 19 ms 1880 KB Output is correct
16 Correct 309 ms 21256 KB Output is correct
17 Correct 201 ms 20756 KB Output is correct
18 Correct 192 ms 20816 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 4 ms 860 KB Output is correct
5 Correct 4 ms 860 KB Output is correct
6 Correct 4 ms 860 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 80 ms 13964 KB Output is correct
9 Correct 120 ms 8016 KB Output is correct
10 Correct 329 ms 21304 KB Output is correct
11 Correct 189 ms 21840 KB Output is correct
12 Correct 188 ms 20308 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 86 ms 13908 KB Output is correct
15 Correct 19 ms 1880 KB Output is correct
16 Correct 312 ms 21328 KB Output is correct
17 Correct 209 ms 20816 KB Output is correct
18 Correct 206 ms 20644 KB Output is correct
19 Correct 701 ms 89088 KB Output is correct
20 Correct 664 ms 88996 KB Output is correct
21 Correct 676 ms 88912 KB Output is correct
22 Correct 659 ms 88908 KB Output is correct
23 Correct 666 ms 88916 KB Output is correct
24 Correct 652 ms 88916 KB Output is correct
25 Correct 659 ms 88916 KB Output is correct
26 Correct 688 ms 88916 KB Output is correct
27 Correct 675 ms 89032 KB Output is correct
28 Correct 621 ms 89084 KB Output is correct
29 Correct 631 ms 89036 KB Output is correct
30 Correct 614 ms 88996 KB Output is correct