oj.uz

Submission #635792

# Submission time Handle Problem Language Result Execution time Memory
635792 2022-08-27T01:01:59 Z skittles1412 Pyramid Base (IOI08_pyramid_base) C++17
0 / 100
 1136 ms 187232 KB 
#include "bits/extc++.h"

using namespace std;

template <typename T>
void dbgh(const T& t) {
    cerr << t << endl;
}

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
    cerr << t << " | ";
    dbgh(u...);
}

#ifdef DEBUG
#define dbg(...)                                           \
    cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]" \
         << ": ";                                          \
    dbgh(__VA_ARGS__)
#else
#define cerr   \
    if (false) \
    cerr
#define dbg(...)
#endif

#define endl "\n"
#define long int64_t
#define sz(x) int(size(x))

struct Node {
    int len;
    pair<int, int> mn, suff, pref;

    static pair<int, int> mx(const pair<int, int>& a, const pair<int, int>& b) {
        if (a.first == b.first) {
            if (a.second >= b.second) {
                return a;
            } else {
                return b;
            }
        }
        return min(a, b);
    }

    static pair<int, int> merge(const pair<int, int>& a,
                                const pair<int, int>& b) {
        if (a.first == b.first) {
            return {a.first, a.second + b.second};
        }
        return min(a, b);
    }

    Node operator+(const Node& n) const {
        return {len + n.len, mx(mx(mn, n.mn), merge(suff, n.pref)),
                pref.second == len ? merge(pref, n.pref) : pref,
                n.suff.second == n.len ? merge(suff, n.suff) : n.suff};
    }

    void apply_lazy(int x) {
        mn.first += x;
        suff.first += x;
        pref.first += x;
    }

    static Node zero() {
        return {1, {0, 1}, {0, 1}, {0, 1}};
    }
};

struct ST {
    int n;
    vector<Node> v;
    vector<int> lazy;

    ST(int n) : n(n), v(4 * n, Node::zero()), lazy(4 * n) {}

    void update(int o, int l, int r, int ql, int qr, int x) {
        if (ql <= l && r <= qr) {
            lazy[o] += x;
            v[o].apply_lazy(x);
            return;
        }
        int mid = (l + r) / 2, lc = o * 2, rc = lc + 1;
        if (ql <= mid) {
            update(lc, l, mid, ql, qr, x);
        }
        if (mid < qr) {
            update(rc, mid + 1, r, ql, qr, x);
        }
        v[o] = v[lc] + v[rc];
        v[o].apply_lazy(lazy[o]);
    }

    void update(int l, int r, int x) {
        update(1, 0, n - 1, l, r, x);
    }

    int query() const {
        auto& [mn, mn_cnt] = v[1].mn;
        return !mn ? mn_cnt : 0;
    }
};

void solve() {
    int n, m, _b, k;
    cin >> n >> m >> _b >> k;
    int arr[k][5];
    for (auto& a : arr) {
        for (auto& b : a) {
            cin >> b;
            b--;
        }
    }
    vector<array<int, 3>> upds[n + 1];
    for (auto& [x1, x2, y1, y2, _] : arr) {
        upds[x1].push_back({y1, y2, +1});
        upds[x2 + 1].push_back({y1, y2, -1});
    }
    ST st(m);
    int ans = 0;
    for (int i = 0, j = 0; i < n; i++) {
        while (j < n) {
            ans = max(ans, j - i);
            for (auto& [l, r, x] : upds[j]) {
                if (x > 0) {
                    st.update(l, r, x);
                }
            }
            if (st.query() < j - i) {
                break;
            }
            j++;
        }
        for (auto& [l, r, x] : upds[i]) {
            if (x < 0) {
                st.update(l, r, x);
            }
        }
    }
    cout << ans << endl;
}

int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cin.exceptions(ios::failbit);
    solve();
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 456 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 1876 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 15188 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 138 ms 149092 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 125 ms 149128 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 2120 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 40 ms 16620 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 202 ms 151272 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 207 ms 151744 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 213 ms 152328 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #13
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 664 ms 169392 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #14
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 865 ms 178468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #15
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1136 ms 187232 KB Output isn't correct
2 Halted 0 ms 0 KB -