oj.uz

Submission #54083

# Submission time Handle Problem Language Result Execution time Memory
54083 2018-07-02T09:51:04 Z imeimi2000 Pyramid Base (IOI08_pyramid_base) C++17
100 / 100
 1659 ms 98560 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23800 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 23908 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 23984 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 24148 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 24224 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 24300 KB Output is correct
2 Correct 34 ms 24304 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 24304 KB Output is correct
2 Correct 30 ms 24304 KB Output is correct

Subtask #8
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 24552 KB Output is correct
2 Correct 112 ms 24684 KB Output is correct
3 Correct 79 ms 24684 KB Output is correct

Subtask #9
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 275 ms 25964 KB Output is correct
2 Correct 364 ms 25964 KB Output is correct
3 Correct 281 ms 26092 KB Output is correct

Subtask #10
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 272 ms 26348 KB Output is correct
2 Correct 63 ms 26348 KB Output is correct
3 Correct 220 ms 27372 KB Output is correct
4 Correct 550 ms 27372 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 593 ms 27756 KB Output is correct
2 Correct 674 ms 27756 KB Output is correct
3 Correct 144 ms 27756 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 345 ms 27756 KB Output is correct
2 Correct 876 ms 27884 KB Output is correct
3 Correct 836 ms 28028 KB Output is correct
4 Correct 838 ms 28028 KB Output is correct
5 Correct 888 ms 28148 KB Output is correct
6 Correct 112 ms 28148 KB Output is correct

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 992 ms 65836 KB Output is correct
2 Correct 441 ms 65836 KB Output is correct

Subtask #14
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1200 ms 73148 KB Output is correct
2 Correct 1056 ms 73148 KB Output is correct
3 Correct 685 ms 73148 KB Output is correct

Subtask #15
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1464 ms 98560 KB Output is correct
2 Correct 1589 ms 98560 KB Output is correct
3 Correct 1659 ms 98560 KB Output is correct
4 Correct 1464 ms 98560 KB Output is correct
5 Correct 980 ms 98560 KB Output is correct