제출 #1324007

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1324007		sh_qaxxorov_571	벽 (IOI14_wall)	C++20	100 / 100	395 ms	88928 KiB

wall

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

using namespace std;

const int INF = 1e9;

struct Node {
    int low, high;
};

Node tree[8000005]; // 4 * N o'lchamli segmentlar daraxti

// Yangi cheklovlarni joriy cheklovlarga tatbiq etish
void apply(int node, int op, int h) {
    if (op == 1) { // Add amal (pastdan cheklov)
        tree[node].low = max(tree[node].low, h);
        tree[node].high = max(tree[node].high, h);
    } else { // Remove amal (tepadan cheklov)
        tree[node].low = min(tree[node].low, h);
        tree[node].high = min(tree[node].high, h);
    }
}

// Ota tugun cheklovlarini bola tugunlarga o'tkazish
void push(int node, int l, int r) {
    if (l != r) {
        apply(2 * node, 1, tree[node].low);
        apply(2 * node, 2, tree[node].high);
        apply(2 * node + 1, 1, tree[node].low);
        apply(2 * node + 1, 2, tree[node].high);
        tree[node].low = 0;
        tree[node].high = INF;
    }
}

void update(int node, int l, int r, int ql, int qr, int op, int h) {
    if (ql <= l && r <= qr) {
        apply(node, op, h);
        return;
    }
    push(node, l, r);
    int mid = (l + r) / 2;
    if (ql <= mid) update(2 * node, l, mid, ql, qr, op, h);
    if (qr > mid) update(2 * node + 1, mid + 1, r, ql, qr, op, h);
}

// Yakuniy natijalarni yig'ish
void getFinal(int node, int l, int r, int finalHeight[]) {
    if (l == r) {
        finalHeight[l] = tree[node].low;
        return;
    }
    push(node, l, r);
    int mid = (l + r) / 2;
    getFinal(2 * node, l, mid, finalHeight);
    getFinal(2 * node + 1, mid + 1, r, finalHeight);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
    // Dastlabki holatni sozlash
    for (int i = 0; i < 4 * n + 5; i++) {
        tree[i].low = 0;
        tree[i].high = INF;
    }

    for (int i = 0; i < k; i++) {
        update(1, 0, n - 1, left[i], right[i], op[i], height[i]);
    }

    getFinal(1, 0, n - 1, finalHeight);
}

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