oj.uz

Submission #54067

# Submission time Handle Problem Language Result Execution time Memory
54067 2018-07-02T09:37:46 Z sebinkim Pyramid Base (IOI08_pyramid_base) C++14
0 / 100
 5000 ms 41908 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

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; }
};

ll T[2202020], L[2202020];
obstacle K1[404040], K2[404040];
int n, m, c, k, sz;

char in[1<<22];
char const*o;

void init_in()
{ 
    o = in; 
    in[fread(in,1,sizeof(in)-4,stdin)]=0;
}

int readInt(){ 
   unsigned u = 0, s = 0;
   while(*o && *o <= 32)++o;
   if (*o == '-')s = ~s, ++o; else if (*o == '+')++o;
   while(*o>='0' && *o<='9') u = (u<<3) + (u << 1) + (*o++ - '0');
   return static_cast<int>( (u^s) + !!s) ;
}

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;
	bool f = false;
	
	if(K1[0].x-t+1 > 1) return 1;
	
	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, -K2[j].c);
			if(0 < K1[i].x-t && K2[j].x < K2[j+1].x && K2[j].x < K1[i].x-t) f |= (T[1] + L[1] <= c);
		}
		add(1, 1, m-t+1, K1[i].y1-t+1, K1[i].y2, K1[i].c);
		if(K1[i].x < K1[i+1].x && K1[i].x-t < K2[j].x && 0 < K1[i+1].x-t) f |= (T[1] + L[1] <= c);
	}
	for(;j<k;j++){
		add(1, 1, m-t+1, K2[j].y1-t+1, K2[j].y2, -K2[j].c);
		if(K2[j].x < K2[j+1].x && K2[j].x <= n-t) f |= (T[1] + L[1] <= c);
	}
	
	return f;
}

int main()
{
	//freopen("input.txt", "r", stdin);
	init_in();
	
	int i, s, e;
	int x1, x2, y1, y2, z;
	
	n = readInt();
	m = readInt();
	c = readInt();
	k = readInt();
	
	for(sz=1;sz<=m;sz<<=1);
	
	for(i=0;i<k;i++){
		x1 = readInt();
		y1 = readInt();
		x2 = readInt();
		y2 = readInt();
		z = readInt();
		
		K1[i] = obstacle(x1, y1, y2, z);
		K2[i] = obstacle(x2, y1, y2, -z);
	}
	
	sort(K1, K1+k);
	sort(K2, K2+k);
	
	K1[k] = K2[k] = obstacle(1e9, 0, 0, 0);
	
	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:46:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  add(p<<1, s, s+e>>1, l, r, v);
               ~^~
pyramid_base.cpp:47: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:54:12: warning: unused variable 'p' [-Wunused-variable]
  int i, j, p;
            ^
pyramid_base.cpp: In function 'int main()':
pyramid_base.cpp:107:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   if(check(s+e>>1)) s = (s+e>>1) + 1;
            ~^~
pyramid_base.cpp:107:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   if(check(s+e>>1)) s = (s+e>>1) + 1;
                          ~^~
pyramid_base.cpp:108:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   else e = (s+e>>1) - 1;
             ~^~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 252 KB Output isn't correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 484 KB Output isn't correct

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 484 KB Output isn't correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 984 KB Output isn't correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 3740 KB Output isn't correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 46 ms 24144 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 48 ms 25088 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 30 ms 25088 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 231 ms 25088 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 397 ms 25088 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 824 ms 26776 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 589 ms 26776 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #13
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 4918 ms 35624 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #14
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5003 ms 38752 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 5008 ms 41908 KB Time limit exceeded
2 Halted 0 ms 0 KB -