oj.uz

Submission #1103980

# Submission time Handle Problem Language Result Execution time Memory
1103980 2024-10-22T14:06:24 Z vjudge1 Wall (IOI14_wall) C++17
0 / 100
 102 ms 70772 KB 
#include "wall.h";
#include <bits/stdc++.h>
using namespace std;

using pii = pair<int, int>;
const int inf = 1e9;
const int N = 2e6 + 10;
int n, k;

struct LazyTree {
    pii lz[4 * N];
    void init() {
        for (int i = 0; i < 4 * N; i++) lz[i] = pii(inf, inf);
    }
    void push(int i, int b, int e) {
        if (lz[i] == pii(inf, inf)) return;
        if (b < e) {
            if (lz[i * 2].first == inf) lz[i * 2] = lz[i];
            else if (lz[i].second == 2) lz[i * 2] = min(lz[i * 2], lz[i]);
            else lz[i * 2] = max(lz[i * 2], lz[i]);
            lz[i * 2].second = lz[i].second;
            if (lz[i * 2 + 1].first == inf) lz[i * 2 + 1] = lz[i];
            else if (lz[i].second == 2) lz[i * 2 + 1] = min(lz[i * 2 + 1], lz[i]);
            else lz[i * 2 + 1] = max(lz[i * 2 + 1], lz[i]);
            lz[i * 2 + 1].second = lz[i].second;
            lz[i] = pii(inf, inf);
        }
    }
    void update(int i, int b, int e, int l, int r, int v, int op) {
        push(i, b, e);
        if (r < b || e < l) return;
        if (l <= b && e <= r) {
            lz[i] = pii(v, op);
            push(i, b, e);
            return;
        }
        int mid = (b + e) / 2;
        update(i * 2, b, mid, l, r, v, op);
        update(i * 2 + 1, mid + 1, e, l, r, v, op);
    }
    void update(int l, int r, int v, int op) {
        update(1, 0, n - 1, l, r, v, op);
    }
    int query(int i, int b, int e, int x) {
        push(i, b, e);
        if (b == e) return lz[i].first;
        int mid = (b + e) / 2;
        if (x <= mid) return query(i * 2, b, mid, x);
        else return query(i * 2 + 1, mid + 1, e, x);
    }
    int query(int x) {
        return query(1, 0, n - 1, x);
    }
}
st;

void buildWall(int N, int K, int op[], int left[], int right[], int height[], int finalHeight[]) {
    n = N, k = K;
    st.init();
    st.update(0, n - 1, 0, 1);
    for (int i = 0; i < k; i++) {
        st.update(left[i], right[i], height[i], op[i]);
        //cout << i + 1 << " -> ";
        //for (int i = 0; i < n; i++) cout << st.query(i) << " "; cout << "\n";
    }
    for (int i = 0; i < n; i++) {
        finalHeight[i] = st.query(i);
    }
}

Compilation message

wall.cpp:1:18: warning: extra tokens at end of #include directive
    1 | #include "wall.h";
      |                  ^

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 63056 KB Output is correct
2 Incorrect 14 ms 63056 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 63056 KB Output is correct
2 Incorrect 102 ms 70772 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 63056 KB Output is correct
2 Incorrect 12 ms 63056 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 63228 KB Output is correct
2 Incorrect 11 ms 63056 KB Output isn't correct
3 Halted 0 ms 0 KB -