oj.uz

Submission #384411

# Submission time Handle Problem Language Result Execution time Memory
384411 2021-04-01T15:45:15 Z apostoldaniel854 Wall (IOI14_wall) C++14
100 / 100
 960 ms 118252 KB 
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define dbg(x) cerr << #x << " " << x << "\n"


//#define HOME

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

**/
#ifndef HOME
    #include "wall.h"
#endif // HOME

const int ADD = 1, REMOVE = 2;

struct node_t {
    int low;
    int high;
};
struct event_t {
    int pos;
    node_t value;
};

node_t join (node_t left_node, node_t right_node) {
    return {max (left_node.low, right_node.low), min (left_node.high, right_node.high)};
}
const int MX = 1e5;
struct segment_tree {
    vector <node_t> seg;
    segment_tree (int n) {
        seg.resize (1 + 4 * n, {0, MX});
    }
    void update (int node, int lb, int rb, int pos, node_t value) {
        if (lb == rb) {
            seg[node] = value;
            return;
        }
        int mid = (lb + rb) / 2, left_node = node * 2, right_node = node * 2 + 1;
        if (pos <= mid)
            update (left_node, lb, mid, pos, value);
        else
            update (right_node, mid + 1, rb, pos, value);
        seg[node] = join (seg[left_node], seg[right_node]);
    }
    int query (int node, int lb, int rb, node_t &cur) {
        if (lb == rb)
            return lb;
        int mid = (lb + rb) / 2, left_node = node * 2, right_node = node * 2 + 1;
        node_t take = join (cur, seg[right_node]);
        if (take.low <= take.high) {
            cur = take;
            return query (left_node, lb, mid, cur);
        }
        else {
            return query (right_node, mid + 1, rb, cur);
        }
    }
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    vector <vector <event_t>> events (1 + n);
    for (int i = 0; i < k; i++) {
        if (op[i] == ADD)
            events[left[i]].push_back ({i, {height[i], MX}});
        else
            events[left[i]].push_back ({i, {0, height[i]}});
        events[right[i] + 1].push_back ({i, {0, MX}});
    }
    vector <node_t> h (k);
    segment_tree aint (k);
    int ans = 0;
    for (int i = 0; i < n; i++) {
        for (event_t event : events[i]) {
            aint.update (1, 0, k - 1, event.pos, event.value);
            h[event.pos] = event.value;
        }
        node_t cur = {0, MX};
        int best = aint.query (1, 0, k - 1, cur);
        if (join (cur, h[best]).low <= cur.high)
            ans = join (cur, h[best]).low;
        else if (join (cur, h[best]).low > cur.high)
            ans = join (cur, h[best]).high;
        else
            ans = cur.low;
        finalHeight[i] = ans;
    }
    return;
}



#ifdef HOME
int main()
{
  int n;
  int k;

  int i, j;
  int status = 0;

  status = scanf("%d%d", &n, &k);
  assert(status == 2);

  int* op = (int*)calloc(sizeof(int), k);
  int* left = (int*)calloc(sizeof(int), k);
  int* right = (int*)calloc(sizeof(int), k);
  int* height = (int*)calloc(sizeof(int), k);
  int* finalHeight = (int*)calloc(sizeof(int), n);

  for (i = 0; i < k; i++){
    status = scanf("%d%d%d%d", &op[i], &left[i], &right[i], &height[i]);
    assert(status == 4);
  }

  buildWall(n, k, op, left, right, height, finalHeight);

  for (j = 0; j < n; j++)
    printf("%d\n", finalHeight[j]);

  return 0;
}
#endif // HOME

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 4 ms 876 KB Output is correct
3 Correct 2 ms 620 KB Output is correct
4 Correct 9 ms 1132 KB Output is correct
5 Correct 7 ms 1132 KB Output is correct
6 Correct 7 ms 1132 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 300 ms 45380 KB Output is correct
3 Correct 235 ms 23788 KB Output is correct
4 Correct 818 ms 60112 KB Output is correct
5 Correct 429 ms 58092 KB Output is correct
6 Correct 451 ms 55404 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 3 ms 876 KB Output is correct
3 Correct 2 ms 620 KB Output is correct
4 Correct 7 ms 1132 KB Output is correct
5 Correct 7 ms 1132 KB Output is correct
6 Correct 7 ms 1132 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 290 ms 45508 KB Output is correct
9 Correct 273 ms 23916 KB Output is correct
10 Correct 782 ms 60036 KB Output is correct
11 Correct 433 ms 57836 KB Output is correct
12 Correct 435 ms 55532 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 299 ms 45380 KB Output is correct
15 Correct 33 ms 4332 KB Output is correct
16 Correct 768 ms 60012 KB Output is correct
17 Correct 422 ms 55916 KB Output is correct
18 Correct 424 ms 55204 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 4 ms 876 KB Output is correct
3 Correct 3 ms 620 KB Output is correct
4 Correct 7 ms 1132 KB Output is correct
5 Correct 7 ms 1260 KB Output is correct
6 Correct 7 ms 1132 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 282 ms 45380 KB Output is correct
9 Correct 265 ms 23808 KB Output is correct
10 Correct 832 ms 60012 KB Output is correct
11 Correct 428 ms 58012 KB Output is correct
12 Correct 429 ms 55532 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 289 ms 45508 KB Output is correct
15 Correct 33 ms 4332 KB Output is correct
16 Correct 798 ms 60128 KB Output is correct
17 Correct 454 ms 55788 KB Output is correct
18 Correct 448 ms 55252 KB Output is correct
19 Correct 960 ms 118088 KB Output is correct
20 Correct 923 ms 118124 KB Output is correct
21 Correct 895 ms 118124 KB Output is correct
22 Correct 898 ms 118252 KB Output is correct
23 Correct 895 ms 118124 KB Output is correct
24 Correct 896 ms 118072 KB Output is correct
25 Correct 904 ms 118124 KB Output is correct
26 Correct 899 ms 118124 KB Output is correct
27 Correct 912 ms 117996 KB Output is correct
28 Correct 898 ms 118224 KB Output is correct
29 Correct 895 ms 118124 KB Output is correct
30 Correct 896 ms 117996 KB Output is correct