oj.uz

Submission #53977

# Submission time Handle Problem Language Result Execution time Memory
53977 2018-07-02T06:43:52 Z 강태규(#1453) Pyramid Base (IOI08_pyramid_base) C++11
70 / 100
 5000 ms 52896 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];
llong ad[1 << 21];
llong mn[1 << 21];

void update(int i, int s, int e, int x, int y, llong 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, 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 - 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, 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 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 2 ms 380 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 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 596 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 672 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 672 KB Output is correct
2 Correct 18 ms 696 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 708 KB Output is correct
2 Correct 10 ms 708 KB Output is correct

Subtask #8
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 952 KB Output is correct
2 Correct 83 ms 1080 KB Output is correct
3 Correct 69 ms 1080 KB Output is correct

Subtask #9
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 297 ms 2508 KB Output is correct
2 Correct 415 ms 3064 KB Output is correct
3 Correct 338 ms 3068 KB Output is correct

Subtask #10
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 404 ms 3324 KB Output is correct
2 Correct 48 ms 3324 KB Output is correct
3 Correct 247 ms 4224 KB Output is correct
4 Correct 602 ms 4296 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 524 ms 4608 KB Output is correct
2 Correct 718 ms 4608 KB Output is correct
3 Correct 188 ms 4608 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 428 ms 4608 KB Output is correct
2 Correct 1130 ms 4872 KB Output is correct
3 Correct 1014 ms 4872 KB Output is correct
4 Correct 981 ms 4872 KB Output is correct
5 Correct 995 ms 4872 KB Output is correct
6 Correct 122 ms 4872 KB Output is correct

Subtask #13
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5031 ms 29268 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 5048 ms 35076 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 52896 KB Time limit exceeded
2 Halted 0 ms 0 KB -