oj.uz

Submission #53999

# Submission time Handle Problem Language Result Execution time Memory
53999 2018-07-02T07:39:39 Z 강태규(#1453) Pyramid Base (IOI08_pyramid_base) C++11
70 / 100
 5000 ms 57048 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;

const int bsz = 1;
char getChar() {
    static char buf[bsz];
    static int seek = bsz;
    if (seek == bsz) {
        fread(buf, 1, bsz, stdin);
        seek = 0;
    }
    return buf[seek++];
}

int getInt() {
    char c;
    while ((c = getChar()) < '0' || '9' < c);
    int ret = c - '0';
    while ('0' <= (c = getChar()) && c <= '9') {
        ret = (ret << 3) + (ret << 1);
        ret += c - '0';
    }
    return ret;
}

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[800000];

int comp[800000];
llong ad[1 << 21];
llong mn[1 << 21];

llong imin(llong x, llong y) {
    return x < y ? x : y;
}

int imin(int x, int y) {
    return x < y ? x : y;
}

int imax(int x, int y) {
    return x < y ? y : x;
}

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] = imin(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 = imax(1, st[i].x1 - x + 1);
        int y1 = imax(1, st[i].y1 - x + 1);
        int x2 = imin(st[i].x2, mx);
        int y2 = imin(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;
}

int main() {
    scanf("%d%d%d%d", &m, &n, &b, &p);
    for (int i = 0; i < p; ++i) {
        st[i].scan();
    }
    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 'char getChar()':
pyramid_base.cpp:27:14: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         fread(buf, 1, bsz, stdin);
         ~~~~~^~~~~~~~~~~~~~~~~~~~
pyramid_base.cpp: In function 'int main()':
pyramid_base.cpp:115: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:48: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 2 ms 376 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 392 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 520 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 568 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 620 KB Output is correct
2 Correct 14 ms 644 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 792 KB Output is correct
2 Correct 8 ms 792 KB Output is correct

Subtask #8
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 932 KB Output is correct
2 Correct 64 ms 1140 KB Output is correct
3 Correct 54 ms 1140 KB Output is correct

Subtask #9
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 238 ms 2624 KB Output is correct
2 Correct 310 ms 2624 KB Output is correct
3 Correct 239 ms 2668 KB Output is correct

Subtask #10
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 2844 KB Output is correct
2 Correct 43 ms 2844 KB Output is correct
3 Correct 186 ms 3948 KB Output is correct
4 Correct 443 ms 3964 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 417 ms 4220 KB Output is correct
2 Correct 531 ms 4220 KB Output is correct
3 Correct 114 ms 4220 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 334 ms 4220 KB Output is correct
2 Correct 840 ms 4476 KB Output is correct
3 Correct 779 ms 4476 KB Output is correct
4 Correct 868 ms 4476 KB Output is correct
5 Correct 756 ms 4476 KB Output is correct
6 Correct 91 ms 4476 KB Output is correct

Subtask #13
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5008 ms 28824 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #14
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5060 ms 34804 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #15
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5019 ms 57048 KB Time limit exceeded
2 Halted 0 ms 0 KB -