| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 53980 |
2018-07-02T06:50:17 Z |
김세빈(#1455) |
Pyramid Base (IOI08_pyramid_base) |
C++11 |
|
5000 ms |
49188 KB |
#include <bits/stdc++.h>
using namespace std;
struct obstacle{
int x, y1, y2, c;
obstacle() {}
obstacle(int x_, int y1_, int y2_, int c_) { x = x_, y1 = y1_, y2 = y2_, c = c_; }
bool operator < (obstacle& c) { return x < c.x; }
};
int T[2202020], L[2202020];
vector <int> V[1010101];
obstacle K1[404040], K2[404040];
int n, m, c, k, sz;
void add(int p, int s, int e, int l, int r, int v)
{
if(r < s || e < l) return;
if(l <= s && e <= r){
L[p] += v;
return;
}
L[p<<1] += L[p], L[p<<1|1] += L[p];
L[p] = 0;
add(p<<1, s, s+e>>1, l, r, v);
add(p<<1|1, (s+e>>1)+1, e, l, r, v);
T[p] = min(T[p<<1] + L[p<<1], T[p<<1|1] + L[p<<1|1]);
}
bool check(int t)
{
int i, j, p, l, r;
bool f = false;
for(i=j=0;i<k;i++){
for(;j<k && K2[j].x < K1[i].x-t+1;j++){
add(1, 1, m-t+1, K2[j].y1-t+1, K2[j].y2, -1);
l = K2[j].x;
if(j == k-1) r = 1e9;
else r = K2[j+1].x-1;
r = min(r, K1[i].x-t);
if(1 <= r && l <= r && l <= n-t+1) f |= (T[1] + L[1] == 0);
}
add(1, 1, m-t+1, K1[i].y1-t+1, K1[i].y2, 1);
l = K1[i].x-t+1;
if(i == k-1) r = 1e9;
else r = K1[i+1].x-t;
if(j < k) r = min(r, K2[j].x-1);
if(1 <= r && l <= r && l <= n-t+1) f |= (T[1] + L[1] == 0);
}
for(;j<k;j++){
add(1, 1, m-t+1, K2[j].y1-t+1, K2[j].y2, -1);
l = K2[j].x;
if(j == k-1) r = 1e9;
else r = K2[j+1].x-1;
if(1 <= r && l <= r && l <= n-t+1) f |= (T[1] + L[1] == 0);
}
return f;
}
int main()
{
// freopen("input.txt", "r", stdin);
int i, s, e;
int x1, x2, y1, y2, z;
scanf("%d%d%d%d", &n, &m, &c, &k);
for(sz=1;sz<=n && sz<=m;sz<<=1);
for(i=0;i<k;i++){
scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &z);
K1[i] = obstacle(x1, y1, y2, 1);
K2[i] = obstacle(x2, y1, y2, -1);
}
sort(K1, K1+k);
sort(K2, K2+k);
for(s=1,e=min(n,m); s<=e;){
if(check(s+e>>1)) s = (s+e>>1) + 1;
else e = (s+e>>1) - 1;
}
printf("%d\n", s-1);
return 0;
}
Compilation message
pyramid_base.cpp: In function 'void add(int, int, int, int, int, int)':
pyramid_base.cpp:28:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
add(p<<1, s, s+e>>1, l, r, v);
~^~
pyramid_base.cpp:29:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
add(p<<1|1, (s+e>>1)+1, e, l, r, v);
~^~
pyramid_base.cpp: In function 'bool check(int)':
pyramid_base.cpp:36:12: warning: unused variable 'p' [-Wunused-variable]
int i, j, p, l, r;
^
pyramid_base.cpp: In function 'int main()':
pyramid_base.cpp:94:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
if(check(s+e>>1)) s = (s+e>>1) + 1;
~^~
pyramid_base.cpp:94:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
if(check(s+e>>1)) s = (s+e>>1) + 1;
~^~
pyramid_base.cpp:95:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
else e = (s+e>>1) - 1;
~^~
pyramid_base.cpp:80:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d%d", &n, &m, &c, &k);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
pyramid_base.cpp:85:8: 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, &z);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
25 ms |
24056 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
24168 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
24244 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
37 ms |
24580 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
42 ms |
25764 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
33 ms |
28836 KB |
Output is correct |
| 2 |
Incorrect |
64 ms |
36676 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
60 ms |
36676 KB |
Output is correct |
| 2 |
Correct |
49 ms |
36676 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
70 ms |
36676 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
270 ms |
36676 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
715 ms |
37360 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
865 ms |
37484 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1383 ms |
37732 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5017 ms |
42828 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5015 ms |
46060 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5028 ms |
49188 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
