제출 #384411

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
384411		apostoldaniel854	벽 (IOI14_wall)	C++14	100 / 100	960 ms	118252 KiB

wall

#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 / 8
• Subtask 2: 24 / 24
• Subtask 3: 29 / 29
• Subtask 4: 39 / 39