oj.uz

Submission #53971

# Submission time Handle Problem Language Result Execution time Memory
53971 2018-07-02T06:33:18 Z 강태규(#1453) Pyramid Base (IOI08_pyramid_base) C++11
32 / 100
 5000 ms 40652 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[800000];

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

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

int find(int x) {
    return lower_bound(comp, comp + sz, x) - comp;
}

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, y2, st[i].c };
        ls[i << 1 | 1] = { x2 + 1, y1, y2, -st[i].c };
        comp[i << 1 | 0] = y1;
        comp[i << 1 | 1] = y2;
    }
    sort(ls, ls + (p << 1));
    sort(comp, comp + (p << 1));
    sz = unique(comp, comp + (p << 1)) - comp;
    if (1 < comp[0] || comp[sz - 1] < my) return 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, find(ls[i].y1), find(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 = 0, e = min(m, n);
    while (s < e) {
        int m = (s + e + 1) / 2;
        if (check(m)) s = m;
        else e = m - 1;
    }
    printf("%d\n", s);
	return 0;
}

Compilation message

pyramid_base.cpp: In function 'int check(int)':
pyramid_base.cpp:76:38: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (px != ls[i].x) if (mn[1] <= b) ret = 1;
                                ~~~~~~^~~~
pyramid_base.cpp: In function 'int main()':
pyramid_base.cpp:85: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 3 ms 376 KB Output is correct

Subtask #2
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 436 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 620 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 620 KB Output is correct

Subtask #6
0 / 5.0

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

Subtask #7
0 / 5.0

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

Subtask #8
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 1056 KB Output is correct
2 Correct 80 ms 1104 KB Output is correct
3 Correct 68 ms 1276 KB Output is correct

Subtask #9
0 / 7.0

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

Subtask #10
0 / 7.0

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

Subtask #11
0 / 7.0

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

Subtask #12
0 / 7.0

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

Subtask #13
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5048 ms 20844 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 5064 ms 26840 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 5078 ms 40652 KB Time limit exceeded
2 Halted 0 ms 0 KB -