oj.uz

Submission #366829

# Submission time Handle Problem Language Result Execution time Memory
366829 2021-02-15T10:50:25 Z KoD Wall (IOI14_wall) C++17
100 / 100
 1095 ms 89324 KB 
#ifndef __APPLE__
#include "wall.h"
#endif
#include <bits/stdc++.h>

template <class T>
using Vec = std::vector<T>;

constexpr int INF = 1000000;

struct SegBeats {
    struct Node {
        int max, smax;
        int min, smin;
        Node(): max(0), smax(-INF), min(0), smin(INF) { }
    };

    Vec<Node> data;
    SegBeats(const int size): data(size * 2) { }

    void fetch(const int k) {
        int l = k * 2;
        int r = k * 2 + 1;
        if (data[l].max < data[r].max) {
            std::swap(l, r);
        }
        data[k].max = data[l].max;
        data[k].smax = std::max(data[l].smax, (data[l].max == data[r].max ? data[r].smax : data[r].max));
        if (data[l].min > data[r].min) {
            std::swap(l, r);
        }
        data[k].min = data[l].min;
        data[k].smin = std::min(data[l].smin, (data[l].min == data[r].min ? data[r].smin : data[r].min));
    }

    void chmax(const int k, const int x) {
        if (x <= data[k].min) {
            return;
        }
        if (data[k].smin <= x) {
            flush(k);
            chmax(k * 2, x);
            chmax(k * 2 + 1, x);
            fetch(k);
        } 
        else {
            upd_min(k, x);
        }
    }

    void chmin(const int k, const int x) {
        if (data[k].max <= x) {
            return;
        }
        if (x <= data[k].smax) {
            flush(k);
            chmin(k * 2, x);
            chmin(k * 2 + 1, x);
            fetch(k);
        }
        else {
            upd_max(k, x);
        }
    }

    void upd_max(const int k, const int x) {
        if (data[k].min == data[k].max) {
            data[k].min = x;
        }
        else if (data[k].smin == data[k].max) {
            data[k].smin = x;
        }
        data[k].max = x;
    }

    void upd_min(const int k, const int x) {
        if (data[k].max == data[k].min) {
            data[k].max = x;
        }
        else if (data[k].smax == data[k].min) {
            data[k].smax = x;
        }
        data[k].min = x;
    }

    void flush(const int k) {
        if (data[k * 2].max > data[k].max) {
            upd_max(k * 2, data[k].max);
        }
        if (data[k * 2 + 1].max > data[k].max) {
            upd_max(k * 2 + 1, data[k].max);
        }
        if (data[k * 2].min < data[k].min) {
            upd_min(k * 2, data[k].min);
        }
        if (data[k * 2 + 1].min < data[k].min) {
            upd_min(k * 2 + 1, data[k].min);
        }
    }

    void push(const int k) {
        const auto lsb = __builtin_ctz(k);
        for (int d = 31 - __builtin_clz(k); d != lsb; --d) {
            flush(k >> d);
        }
    }

    void pull(int k) {
        k >>= __builtin_ctz(k);
        while (k > 1) {
            k >>= 1;
            fetch(k);
        }
    }

    void chmax(int l, int r, const int x) {
        l += size();
        r += size();
        push(l);
        push(r);
        const auto lc = l;
        const auto rc = r;
        while (l < r) {
            if (l & 1) {
                chmax(l, x);
                l += 1;
            }
            if (r & 1) {
                r -= 1;
                chmax(r, x);
            }   
            l >>= 1;
            r >>= 1;
        }
        pull(lc);
        pull(rc);
    }

    void chmin(int l, int r, const int x) {
        l += size();
        r += size();
        push(l);
        push(r);
        const auto lc = l;
        const auto rc = r;
        while (l < r) {
            if (l & 1) {
                chmin(l, x);
                l += 1;
            }
            if (r & 1) {
                r -= 1;
                chmin(r, x);
            }   
            l >>= 1;
            r >>= 1;
        }
        pull(lc);
        pull(rc);
    }

    int get(int i) {
        i += size();
        push(i);
        push(i + 1);
        return data[i].max;
    }

    int size() const {
        return (int) data.size() / 2;
    }
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
    SegBeats seg(n);
    for (int i = 0; i < k; ++i) {
        right[i] += 1;
        if (op[i] == 1) {
            seg.chmax(left[i], right[i], height[i]);
        }
        else {
            seg.chmin(left[i], right[i], height[i]);
        }
    }
    for (int i = 0; i < n; ++i) {
        finalHeight[i] = seg.get(i);
    }
}

#ifdef __APPLE__
int op[100];
int left[100];
int right[100];
int height[100];
int finalHeight[100];

int main() {
    int n, k;
    std::cin >> n >> k;
    for (int i = 0; i < k; ++i) {
        std::cin >> op[i] >> left[i] >> right[i] >> height[i];
    }
    buildWall(n, k, op, left, right, height, finalHeight);
    for (int i = 0; i < n; ++i) {
        std::cout << finalHeight[i] << " \n"[i + 1 == n];
    }
    return 0;
}
#endif

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 2 ms 492 KB Output is correct
3 Correct 3 ms 364 KB Output is correct
4 Correct 10 ms 876 KB Output is correct
5 Correct 9 ms 876 KB Output is correct
6 Correct 7 ms 876 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 164 ms 13164 KB Output is correct
3 Correct 164 ms 8044 KB Output is correct
4 Correct 466 ms 21532 KB Output is correct
5 Correct 353 ms 21996 KB Output is correct
6 Correct 349 ms 20324 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 2 ms 492 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 10 ms 876 KB Output is correct
5 Correct 7 ms 876 KB Output is correct
6 Correct 7 ms 876 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 162 ms 14060 KB Output is correct
9 Correct 166 ms 8044 KB Output is correct
10 Correct 468 ms 21416 KB Output is correct
11 Correct 364 ms 21868 KB Output is correct
12 Correct 349 ms 20204 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 166 ms 13932 KB Output is correct
15 Correct 49 ms 1900 KB Output is correct
16 Correct 868 ms 21484 KB Output is correct
17 Correct 375 ms 20844 KB Output is correct
18 Correct 383 ms 20844 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 2 ms 492 KB Output is correct
3 Correct 3 ms 364 KB Output is correct
4 Correct 10 ms 876 KB Output is correct
5 Correct 7 ms 876 KB Output is correct
6 Correct 7 ms 876 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 163 ms 14060 KB Output is correct
9 Correct 168 ms 8044 KB Output is correct
10 Correct 467 ms 21356 KB Output is correct
11 Correct 360 ms 21868 KB Output is correct
12 Correct 350 ms 20332 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 168 ms 13920 KB Output is correct
15 Correct 49 ms 1900 KB Output is correct
16 Correct 864 ms 21228 KB Output is correct
17 Correct 379 ms 20844 KB Output is correct
18 Correct 386 ms 20716 KB Output is correct
19 Correct 1095 ms 89156 KB Output is correct
20 Correct 1062 ms 89196 KB Output is correct
21 Correct 1084 ms 89220 KB Output is correct
22 Correct 1078 ms 89196 KB Output is correct
23 Correct 1070 ms 89068 KB Output is correct
24 Correct 1055 ms 89196 KB Output is correct
25 Correct 1061 ms 89032 KB Output is correct
26 Correct 1073 ms 89068 KB Output is correct
27 Correct 1063 ms 89324 KB Output is correct
28 Correct 1058 ms 89228 KB Output is correct
29 Correct 1073 ms 89204 KB Output is correct
30 Correct 1088 ms 89220 KB Output is correct