Submission #54083

#	Time	Username	Problem	Language	Result	Execution time	Memory
54083		imeimi2000	Pyramid Base (IOI08_pyramid_base)	C++17	100 / 100	1659 ms	98560 KiB

pyramid_base

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <functional>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cstdlib>

using namespace std;
typedef unsigned int uint;
typedef long long llong;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<llong, llong> pll;

int m, n, b, p, sz;
struct stone {
    int x1, y1, x2, y2, c;
    void scan() {
        scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &c);
    }
} st[400000];

struct line {
    int x, y1, y2, c;
    bool operator<(const line &p) const {
        return x < p.x;
    }
} ls[60000];

int comp[800002];
llong ad[1 << 18];
llong mn[1 << 21];

void update(int i, int s, int e, int x, int y, llong v) {
    if (comp[e] <= x || y <= comp[s]) return;
    if (x <= comp[s] && comp[e] <= y) {
        ad[i] += v;
        mn[i] += v;
        return;
    }
    int m = (s + e) >> 1;
    update(i << 1, s, m, x, y, v);
    update(i << 1 | 1, m, e, x, y, v);
    mn[i] = min(mn[i << 1], mn[i << 1 | 1]) + ad[i];
}

int check(int x) {
    int mx = m - x + 1, my = n - x + 1;
    for (int i = 0; i < p; ++i) {
        int x1 = max(1, st[i].x1 - x + 1);
        int y1 = max(1, st[i].y1 - x + 1);
        int x2 = min(st[i].x2, mx);
        int y2 = min(st[i].y2, my);
        ls[i << 1 | 0] = { x1, y1 - 1, y2, st[i].c };
        ls[i << 1 | 1] = { x2 + 1, y1 - 1, y2, -st[i].c };
        comp[i << 1 | 0] = y1 - 1;
        comp[i << 1 | 1] = y2;
    }
    sort(comp, comp + (p << 1));
    sz = unique(comp, comp + (p << 1)) - comp;
    if (0 < comp[0] || comp[sz - 1] < my) return 1;
    sort(ls, ls + (p << 1));
    int px = 1, ret = 0;
    for (int i = 0; i < (p << 1); ++i) {
        if (px != ls[i].x) if (mn[1] <= b) ret = 1;
        update(1, 0, sz - 1, ls[i].y1, ls[i].y2, ls[i].c);
        px = ls[i].x;
    }
    if (px <= mx) return 1;
    return ret;
}

struct _seg {
    int lt, rt, mx, ln;
    _seg operator+(const _seg &p) const {
        _seg ret;
        ret.lt = lt;
        if (lt == ln) ret.lt += p.lt;
        ret.rt = p.rt;
        if (p.rt == p.ln) ret.rt += rt;
        ret.mx = max(mx, p.mx);
        ret.mx = max(ret.mx, rt + p.lt);
        ret.ln = ln + p.ln;
        return ret;
    }
} seg[1 << 21];

void init2(int i, int s, int e) {
    int l = comp[e] - comp[s];
    seg[i] = { l, l, l, l };
    if (s + 1 < e) {
        int m = (s + e) / 2;
        init2(i << 1, s, m);
        init2(i << 1 | 1, m, e);
    }
}

void update2(int i, int s, int e, int x, int y, int v) {
    if (comp[e] <= x || y <= comp[s]) return;
    int l = comp[e] - comp[s];
    if (x <= comp[s] && comp[e] <= y) {
        if (mn[i] == 0)
            seg[i] = { 0, 0, 0, l };
        mn[i] += v;
        if (mn[i] == 0) {
            if (s + 1 < e) seg[i] = seg[i << 1] + seg[i << 1 | 1];
            else seg[i] = { l, l, l, l };
        }
        return;
    }
    int m = (s + e) / 2;
    update2(i << 1, s, m, x, y, v);
    update2(i << 1 | 1, m, e, x, y, v);
    if (mn[i] == 0) seg[i] = seg[i << 1] + seg[i << 1 | 1];
}
vector<line> vt[1000001];

int solve() {
    for (int i = 0; i < p; ++i) {
        vt[st[i].x1].push_back({ 0, st[i].y1 - 1, st[i].y2, 1 });
        vt[st[i].x2].push_back({ 0, st[i].y1 - 1, st[i].y2, -1 });
        comp[i << 1 | 0] = st[i].y1 - 1;
        comp[i << 1 | 1] = st[i].y2;
    }
    comp[p << 1 | 0] = 0;
    comp[p << 1 | 1] = n;
    sort(comp, comp + ((p + 1) << 1));
    sz = unique(comp, comp + ((p + 1) << 1)) - comp;
    int ret = 0;
    init2(1, 0, sz - 1);
    for (int i = 1, j = 1; i <= m; ++i) {
        while (j <= m + 1 && j - i <= seg[1].mx) {
            ret = max(ret, j - i);
            for (line k : vt[j]) {
                if (k.c == 1) update2(1, 0, sz - 1, k.y1, k.y2, 1);
            }
            ++j;
        }
        for (line k : vt[i]) {
            if (k.c == -1) update2(1, 0, sz - 1, k.y1, k.y2, -1);
        }
    }
    return ret;
}

int main() {
    scanf("%d%d%d%d", &m, &n, &b, &p);
    for (int i = 0; i < p; ++i) {
        st[i].scan();
    }
    if (b == 0) {
        printf("%d\n", solve());
        return 0;
    }
    int s = 1, e = min(m, n), ans = 0;
    while (s <= e) {
        int m = (s + e) >> 1;
        if (check(m)) s = m + 1, ans = m;
        else e = m - 1;
    }
    printf("%d\n", ans);
	return 0;
}

Compilation message (stderr)

pyramid_base.cpp: In function 'int main()':
pyramid_base.cpp:154:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d%d", &m, &n, &b, &p);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
pyramid_base.cpp: In member function 'void stone::scan()':
pyramid_base.cpp:26:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &c);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 5 / 5
• Subtask 8: 7 / 7
• Subtask 9: 7 / 7
• Subtask 10: 7 / 7
• Subtask 11: 7 / 7
• Subtask 12: 7 / 7
• Subtask 13: 10 / 10
• Subtask 14: 10 / 10
• Subtask 15: 10 / 10