oj.uz

Submission #834884

# Submission time Handle Problem Language Result Execution time Memory
834884 2023-08-22T22:05:15 Z sadsa Wall (IOI14_wall) C++17
8 / 100
 3000 ms 79616 KB 
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;

using vi = vector<int>;
using ii = pair<int, int>;
using vii = vector<ii>;

using i64 = int64_t;
using vl = vector<i64>;
using ll = pair<i64, i64>;
using vll = vector<ll>;

constexpr int iINF = numeric_limits<int>::max();
constexpr i64 lINF = numeric_limits<i64>::max();

#define RANGE(x) begin(x), end(x)

template <typename... T>
void DBG(T&&... args) {
    //((cerr << args << ' '), ...) << '\n';
}

template <typename T>
ostream &operator<<(ostream &out, const vector<T> &vec) {
    out << '{';
    for (size_t i = 0; i < vec.size()-1; ++i)
        out << vec[i] << ", ";
    out << vec.back() << '}';
    return out;
}

template <typename T1, typename T2>
ostream &operator<<(ostream &out, const pair<T1, T2> &pr) {
    out << '(' << pr.first << ", " << pr.second << ')';
    return out;
}

struct Node {
    int mi{}, ma{};
    int ladd = -1;
    int lrem = -1;

    bool cpy(const Node &n) {
        if (ladd != -1 || lrem != -1) return true;

        ladd = n.ladd;
        lrem = n.lrem;

        return false;
    }

    void prop() {
        if (ladd!=-1) {
            if (ladd > mi) mi = ladd;
            if (ladd > ma) ma = ladd;
        }

        if (lrem!=-1) {
            if (lrem < ma) ma = lrem;
            if (lrem < mi) mi = lrem;
        }

        tie(mi, ma) = minmax(mi, ma);
    }

    void reset() {
        ladd = -1;
        lrem = -1;
    }
};

static constexpr int N = 1 << 21;
struct Seg {
    vector<Node> seg = vector<Node>(N * 2);

    void prop(int p) {
        seg[p].prop();
        if (p < N) {
            if (seg[p*2].cpy(seg[p])) {
                prop(p*2);
                seg[p*2].cpy(seg[p]);
            }
            if (seg[p*2+1].cpy(seg[p])) {
                prop(p*2+1);
                seg[p*2+1].cpy(seg[p]);
            }
        }
        if (seg[p].ladd != -1) DBG("PROP ADD", p, seg[p].ladd);
        if (seg[p].lrem != -1) DBG("PROP REM", p, seg[p].lrem);
        seg[p].reset();
    }

    void update(int l, int r, int ladd, int lrem, int vl=0, int vr=N-1, int p=1) {
        prop(p);
        if (l > vr || r < vl) return;

        DBG(l, r, vl, vr, p, ladd, lrem);
        if (l <= vl && vr <= r) {
            seg[p].lrem = lrem;
            seg[p].ladd = ladd;
            DBG("endnode");
            return;
        }

        int mid = (vl+vr)/2;

        update(l, r, ladd, lrem, vl, mid, p*2);
        update(l, r, ladd, lrem, mid+1, vr, p*2+1);
    }

    void prop_rec(int p=1) {
        prop(p);

        if (p < N) {
            prop_rec(p*2);
            prop_rec(p*2+1);
        } else {
            prop(p);
        }
    }
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    Seg seg;
    seg.prop_rec();
    DBG("START");

    for (int i = 0; i < k; ++i) {
        DBG("-----------UPDATE", i);
        seg.update(left[i], right[i], op[i] == 1? height[i]: -1, op[i] == 2? height[i]: -1);
    }

    DBG("DONE");
    seg.prop_rec();
    for (int i = 0; i < n; ++i)
        finalHeight[i] = seg.seg[i + N].mi;
        
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 65992 KB Output is correct
2 Correct 98 ms 66004 KB Output is correct
3 Correct 101 ms 65876 KB Output is correct
4 Correct 316 ms 66124 KB Output is correct
5 Correct 284 ms 66124 KB Output is correct
6 Correct 291 ms 66160 KB Output is correct

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 65876 KB Output is correct
2 Correct 360 ms 73796 KB Output is correct
3 Execution timed out 3023 ms 69380 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 65876 KB Output is correct
2 Correct 98 ms 66004 KB Output is correct
3 Correct 103 ms 65988 KB Output is correct
4 Correct 312 ms 66124 KB Output is correct
5 Correct 289 ms 66160 KB Output is correct
6 Correct 288 ms 66124 KB Output is correct
7 Correct 97 ms 65868 KB Output is correct
8 Correct 364 ms 79616 KB Output is correct
9 Execution timed out 3036 ms 73036 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 65868 KB Output is correct
2 Correct 99 ms 65996 KB Output is correct
3 Correct 111 ms 66004 KB Output is correct
4 Correct 313 ms 66132 KB Output is correct
5 Correct 293 ms 66120 KB Output is correct
6 Correct 288 ms 66124 KB Output is correct
7 Correct 97 ms 65876 KB Output is correct
8 Correct 353 ms 79616 KB Output is correct
9 Execution timed out 3012 ms 73120 KB Time limit exceeded
10 Halted 0 ms 0 KB -