oj.uz

Submission #53990

# Submission time Handle Problem Language Result Execution time Memory
53990 2018-07-02T07:17:18 Z 김세빈(#1455) Pyramid Base (IOI08_pyramid_base) C++11
70 / 100
 5000 ms 77144 KB 
#include <bits/stdc++.h>

using namespace std;

int T[2202020], L[2202020];
vector <int> V[1010101];
int X1[404040], X2[404040], Y1[404040], Y2[404040], C[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;
	
	for(i=1;i<=n-t+1;i++) V[i].clear();
	for(i=1;i<sz+sz;i++) T[i] = L[i] = 0;
	
	for(i=1;i<=k;i++){
		V[max(1, X1[i]-t+1)].push_back(i);
		V[min(n-t+1, X2[i])+1].push_back(-i);
	}
	
	for(i=1;i<=n-t+1;i++){
		for(j=0;j<V[i].size();j++){
			p = V[i][j];
			if(p > 0) add(1, 1, m-t+1, Y1[p]-t+1, Y2[p], C[p]);
			else add(1, 1, m-t+1, Y1[-p]-t+1, Y2[-p], -C[-p]);
		}
		
		if(T[1] + L[1] <= c) return 1;
	}
	
	return 0;
}

int main()
{
//	freopen("input.txt", "r", stdin);
	
	int i, s, e;
	
	scanf("%d%d%d%d", &n, &m, &c, &k);
	
	for(sz=1;sz<=m;sz<<=1);
	
	for(i=1;i<=k;i++){
		scanf("%d%d%d%d%d", X1+i, Y1+i, X2+i, Y2+i, C+i);
	}
	
	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:21:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  add(p<<1, s, s+e>>1, l, r, v);
               ~^~
pyramid_base.cpp:22: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:40:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=0;j<V[i].size();j++){
           ~^~~~~~~~~~~~
pyramid_base.cpp: In function 'int main()':
pyramid_base.cpp:67:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   if(check(s+e>>1)) s = (s+e>>1) + 1;
            ~^~
pyramid_base.cpp:67:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   if(check(s+e>>1)) s = (s+e>>1) + 1;
                          ~^~
pyramid_base.cpp:68:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   else e = (s+e>>1) - 1;
             ~^~
pyramid_base.cpp:58: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:63: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+i, Y1+i, X2+i, Y2+i, C+i);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 24056 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 24292 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 24344 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 24676 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 26600 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 41056 KB Output is correct
2 Correct 334 ms 41180 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 336 ms 41424 KB Output is correct
2 Correct 196 ms 41424 KB Output is correct

Subtask #8
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 41424 KB Output is correct
2 Correct 75 ms 41424 KB Output is correct
3 Correct 63 ms 41424 KB Output is correct

Subtask #9
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 41424 KB Output is correct
2 Correct 355 ms 41424 KB Output is correct
3 Correct 276 ms 41424 KB Output is correct

Subtask #10
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 389 ms 46548 KB Output is correct
2 Correct 99 ms 46548 KB Output is correct
3 Correct 202 ms 46548 KB Output is correct
4 Correct 734 ms 49900 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 667 ms 49900 KB Output is correct
2 Correct 1261 ms 51496 KB Output is correct
3 Correct 275 ms 51496 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 442 ms 51496 KB Output is correct
2 Correct 1631 ms 54284 KB Output is correct
3 Correct 1542 ms 54284 KB Output is correct
4 Correct 1689 ms 54284 KB Output is correct
5 Correct 1767 ms 54296 KB Output is correct
6 Correct 190 ms 54296 KB Output is correct

Subtask #13
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5082 ms 71764 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 5079 ms 75628 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 5104 ms 77144 KB Time limit exceeded
2 Halted 0 ms 0 KB -