oj.uz

Submission #217868

# Submission time Handle Problem Language Result Execution time Memory
217868 2020-03-31T05:22:19 Z arnold518 Pyramid Base (IOI08_pyramid_base) C++14
70 / 100
 5000 ms 100012 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e6;
const int MAXP = 4e5;
const ll INF = 1e18;

struct Rect
{
	int x1, y1, x2, y2, w;
};

struct Line
{
	int x, y1, y2, w;
	bool operator < (const Line &p) const { return x<p.x; }
};

int N, M, P;
ll B;
Rect A[MAXP+10];

struct SEG
{
	ll tree[MAXN*4+10], lazy[MAXN*4+10];
	void init()
	{
		memset(tree, 0, sizeof(tree));
		memset(lazy, 0, sizeof(lazy));
	}
	void busy(int node, int tl, int tr)
	{
		tree[node]+=lazy[node];
		if(tl!=tr) lazy[node*2]+=lazy[node], lazy[node*2+1]+=lazy[node];
		lazy[node]=0;
	}
	void update(int node, int tl, int tr, int l, int r, ll v)
	{
		busy(node, tl, tr);
		if(r<tl || tr<l) return;
		if(l<=tl && tr<=r)
		{
			lazy[node]+=v;
			busy(node, tl, tr);
			return;
		}
		int mid=tl+tr>>1;
		update(node*2, tl, mid, l, r, v);
		update(node*2+1, mid+1, tr, l, r, v);
		tree[node]=min(tree[node*2], tree[node*2+1]);
	}
}seg;

bool solve(int d)
{
	int i, j;
	vector<Line> V;
	ll val=INF;
	for(i=1; i<=P; i++)
	{
		V.push_back({A[i].x1, A[i].y1, A[i].y2+d-1, A[i].w});
		V.push_back({A[i].x2+d, A[i].y1, A[i].y2+d-1, -A[i].w});
	}
	sort(V.begin(), V.end());
	seg.init();

	for(i=0; i<V.size();)
	{
		int x=V[i].x;
		seg.busy(1, d, N);
		if(d<=x-1) val=min(val, seg.tree[1]);
		if(x>M) break;
		for(; i<V.size() && V[i].x==x; i++)
		{
			seg.update(1, d, N, V[i].y1, V[i].y2, V[i].w);
		}
	}
	seg.busy(1, d, N);
	val=min(val, seg.tree[1]);
	if(val<=B) return true;
	return false;
}

int main()
{
	int i, j;

	scanf("%d%d%lld%d", &M, &N, &B, &P);
	for(i=1; i<=P; i++) scanf("%d%d%d%d%d", &A[i].x1, &A[i].y1, &A[i].x2, &A[i].y2, &A[i].w);

	int lo=0, hi=min(N, M)+1;
	while(lo+1<hi)
	{
		int mid=lo+hi>>1;
		if(solve(mid)) lo=mid;
		else hi=mid;
	}
	printf("%d\n", lo);
}

Compilation message

pyramid_base.cpp: In member function 'void SEG::update(int, int, int, int, int, ll)':
pyramid_base.cpp:51:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid=tl+tr>>1;
           ~~^~~
pyramid_base.cpp: In function 'bool solve(int)':
pyramid_base.cpp:71:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0; i<V.size();)
           ~^~~~~~~~~
pyramid_base.cpp:77:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(; i<V.size() && V[i].x==x; i++)
         ~^~~~~~~~~
pyramid_base.cpp:60:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^
pyramid_base.cpp: In function 'int main()':
pyramid_base.cpp:98:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid=lo+hi>>1;
           ~~^~~
pyramid_base.cpp:90:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^
pyramid_base.cpp:92:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%lld%d", &M, &N, &B, &P);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
pyramid_base.cpp:93:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(i=1; i<=P; i++) scanf("%d%d%d%d%d", &A[i].x1, &A[i].y1, &A[i].x2, &A[i].y2, &A[i].w);
                      ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 62976 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 62840 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 62968 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 63096 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 63188 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 187 ms 62976 KB Output is correct
2 Correct 204 ms 63104 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 218 ms 63104 KB Output is correct
2 Correct 191 ms 63096 KB Output is correct

Subtask #8
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 63640 KB Output is correct
2 Correct 188 ms 63540 KB Output is correct
3 Correct 174 ms 63540 KB Output is correct

Subtask #9
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 373 ms 64276 KB Output is correct
2 Correct 441 ms 64392 KB Output is correct
3 Correct 393 ms 64272 KB Output is correct

Subtask #10
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 475 ms 65068 KB Output is correct
2 Correct 133 ms 65064 KB Output is correct
3 Correct 270 ms 65036 KB Output is correct
4 Correct 856 ms 65104 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 738 ms 65444 KB Output is correct
2 Correct 952 ms 65548 KB Output is correct
3 Correct 363 ms 65384 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 530 ms 65624 KB Output is correct
2 Correct 1245 ms 65844 KB Output is correct
3 Correct 1243 ms 65728 KB Output is correct
4 Correct 1205 ms 65712 KB Output is correct
5 Correct 1209 ms 65540 KB Output is correct
6 Correct 339 ms 65660 KB Output is correct

Subtask #13
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5073 ms 81700 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 5082 ms 94832 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 5075 ms 100012 KB Time limit exceeded
2 Halted 0 ms 0 KB -