Submission #635792

#	Time	Username	Problem	Language	Result	Execution time	Memory
635792		skittles1412	Pyramid Base (IOI08_pyramid_base)	C++17	0 / 100	1136 ms	187232 KiB

pyramid_base

#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
• Subtask 2: 0 / 5
• Subtask 3: 0 / 5
• Subtask 4: 0 / 5
• Subtask 5: 0 / 5
• Subtask 6: 0 / 5
• Subtask 7: 0 / 5
• Subtask 8: 0 / 7
• Subtask 9: 0 / 7
• Subtask 10: 0 / 7
• Subtask 11: 0 / 7
• Subtask 12: 0 / 7
• Subtask 13: 0 / 10
• Subtask 14: 0 / 10
• Subtask 15: 0 / 10