답안 #53980 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
53980	2018-07-02T06:50:17 Z	김세빈(#1455)	Pyramid Base (IOI08_pyramid_base)	C++11	20 / 100	5000 ms	49188 KB

pyramid_base

#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);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	25 ms	24056 KB	Output isn't correct

Subtask #2
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	24 ms	24168 KB	Output is correct

Subtask #3
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	30 ms	24244 KB	Output is correct

Subtask #4
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	37 ms	24580 KB	Output is correct

Subtask #5
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	42 ms	25764 KB	Output isn't correct

Subtask #6
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	33 ms	28836 KB	Output is correct
2	Incorrect	64 ms	36676 KB	Output isn't correct

Subtask #7
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	60 ms	36676 KB	Output is correct
2	Correct	49 ms	36676 KB	Output is correct

Subtask #8
0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	70 ms	36676 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #9
0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	270 ms	36676 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #10
0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	715 ms	37360 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #11
0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	865 ms	37484 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #12
0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	1383 ms	37732 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #13
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	5017 ms	42828 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #14
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	5015 ms	46060 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #15
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	5028 ms	49188 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-