# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
53999 |
2018-07-02T07:39:39 Z |
강태규(#1453) |
Pyramid Base (IOI08_pyramid_base) |
C++11 |
|
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);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
392 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
520 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
568 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
620 KB |
Output is correct |
2 |
Correct |
14 ms |
644 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
792 KB |
Output is correct |
2 |
Correct |
8 ms |
792 KB |
Output is correct |
# |
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 |
# |
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 |
# |
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 |
# |
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 |
# |
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 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
5008 ms |
28824 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
5060 ms |
34804 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
5019 ms |
57048 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |