oj.uz

답안 #217937

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
217937 2020-03-31T09:14:59 Z arnold518 Pyramid Base (IOI08_pyramid_base) C++14
100 / 100
 2255 ms 144892 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)
	{
		if(lazy[node]==0) return;
		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;
 
struct Node
{
	int val, cnt, lcnt, rcnt, len;
	Node() : val(0), cnt(0), lcnt(0), rcnt(0), len(0) {}
};
 
Node operator + (const Node &p, const Node &q)
{
	Node ret;
	ret.len=p.len+q.len;
	ret.val=min(p.val, q.val);
	if(p.val<q.val)
	{
		ret.cnt=p.cnt;
		ret.lcnt=p.lcnt;
		ret.rcnt=0;
	}
	else if(p.val>q.val)
	{
		ret.cnt=q.cnt;
		ret.rcnt=q.rcnt;
		ret.lcnt=0;
	}
	else
	{
		ret.cnt=max({p.cnt, q.cnt, p.rcnt+q.lcnt});
		ret.lcnt=max(p.lcnt, (p.len==p.cnt)*(p.len+q.lcnt));
		ret.rcnt=max(q.rcnt, (q.len==q.cnt)*(q.len+p.rcnt));
	}
	return ret;
}
 
struct SEG2
{
	Node tree[MAXN*4+10];
	int lazy[MAXN*4+10];
 
	void init(int node, int tl, int tr)
	{
        lazy[node]=0;
		if(tl==tr)
		{
			tree[node].len=1;
			tree[node].val=0;
			tree[node].cnt=tree[node].lcnt=tree[node].rcnt=1;
			return;
		}
		int mid=tl+tr>>1;
		init(node*2, tl, mid);
		init(node*2+1, mid+1, tr);
		tree[node]=tree[node*2]+tree[node*2+1];
	}
 
	void busy(int node, int tl, int tr)
	{
		if(lazy[node]==0) return;
		if(tl!=tr) lazy[node*2]+=lazy[node], lazy[node*2+1]+=lazy[node];
		tree[node].val+=lazy[node];
		lazy[node]=0;
	}
 
	void update(int node, int tl, int tr, int l, int r, int 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]=tree[node*2]+tree[node*2+1];
	}
 
	int query(int NN)
	{
		busy(1, 1, NN);
		if(tree[1].val!=0) return 0;
		else return tree[1].cnt;
	}
}seg2;
 
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);
 
	if(B!=0)
	{
		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);
	}
	else
	{
		int l, r;
		vector<Line> V1, V2;
		int ans=0;
 
		V1.clear(); V2.clear();
		for(i=1; i<=P; i++)
		{
			V1.push_back({A[i].x1, A[i].y1, A[i].y2});
			V2.push_back({A[i].x2+1, A[i].y1, A[i].y2});
		}
		sort(V1.begin(), V1.end());
		sort(V2.begin(), V2.end());
 
		seg2.init(1, 1, N);
		for(l=1, r=1, i=0, j=0; r<=M; r++)
		{
			for(; i<V1.size() && V1[i].x==r; i++) seg2.update(1, 1, N, V1[i].y1, V1[i].y2, 1);
			for(; l<r; l++)
			{
				for(; j<V2.size() && V2[j].x==l; j++) seg2.update(1, 1, N, V2[j].y1, V2[j].y2, -1);
				if(!(seg2.query(N)<=r-l+1)) break;
				ans=max(ans, seg2.query(N));
			}
		}
 
		V1.clear(); V2.clear();
		for(i=1; i<=P; i++)
		{
			V1.push_back({A[i].y1, A[i].x1, A[i].x2});
			V2.push_back({A[i].y2+1, A[i].x1, A[i].x2});
		}
		sort(V1.begin(), V1.end());
		sort(V2.begin(), V2.end());
 
		seg2.init(1, 1, M);
		for(l=1, r=1, i=0, j=0; r<=N; r++)
		{
			for(; i<V1.size() && V1[i].x==r; i++) seg2.update(1, 1, M, V1[i].y1, V1[i].y2, 1);
			for(; l<r; l++)
			{
				for(; j<V2.size() && V2[j].x==l; j++) seg2.update(1, 1, M, V2[j].y1, V2[j].y2, -1);
				if(!(seg2.query(M)<=r-l+1)) break;
				ans=max(ans, seg2.query(M));
			}
		}
		printf("%d\n", ans);
	}
}

Compilation message

pyramid_base.cpp: In member function 'void SEG::update(int, int, int, int, int, ll)':
pyramid_base.cpp:52:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid=tl+tr>>1;
           ~~^~~
pyramid_base.cpp: In member function 'void SEG2::init(int, int, int)':
pyramid_base.cpp:106:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid=tl+tr>>1;
           ~~^~~
pyramid_base.cpp: In member function 'void SEG2::update(int, int, int, int, int, int)':
pyramid_base.cpp:130:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid=tl+tr>>1;
           ~~^~~
pyramid_base.cpp: In function 'bool solve(int)':
pyramid_base.cpp:157:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0; i<V.size();)
           ~^~~~~~~~~
pyramid_base.cpp:163:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(; i<V.size() && V[i].x==x; i++)
         ~^~~~~~~~~
pyramid_base.cpp:146:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^
pyramid_base.cpp: In function 'int main()':
pyramid_base.cpp:186:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    int mid=lo+hi>>1;
            ~~^~~
pyramid_base.cpp:210:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(; i<V1.size() && V1[i].x==r; i++) seg2.update(1, 1, N, V1[i].y1, V1[i].y2, 1);
          ~^~~~~~~~~~
pyramid_base.cpp:213:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(; j<V2.size() && V2[j].x==l; j++) seg2.update(1, 1, N, V2[j].y1, V2[j].y2, -1);
           ~^~~~~~~~~~
pyramid_base.cpp:231:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(; i<V1.size() && V1[i].x==r; i++) seg2.update(1, 1, M, V1[i].y1, V1[i].y2, 1);
          ~^~~~~~~~~~
pyramid_base.cpp:234:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(; j<V2.size() && V2[j].x==l; j++) seg2.update(1, 1, M, V2[j].y1, V2[j].y2, -1);
           ~^~~~~~~~~~
pyramid_base.cpp:178: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:179: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

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

Subtask #2
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
5.0 / 5.0

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

Subtask #6
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 111 ms 86944 KB Output is correct
2 Correct 112 ms 87032 KB Output is correct

Subtask #7
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 118 ms 86956 KB Output is correct
2 Correct 128 ms 86964 KB Output is correct

Subtask #8
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 192 ms 141924 KB Output is correct
2 Correct 224 ms 141908 KB Output is correct
3 Correct 214 ms 141876 KB Output is correct

Subtask #9
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 446 ms 143076 KB Output is correct
2 Correct 497 ms 142972 KB Output is correct
3 Correct 426 ms 143180 KB Output is correct

Subtask #10
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 518 ms 143968 KB Output is correct
2 Correct 162 ms 143752 KB Output is correct
3 Correct 294 ms 143756 KB Output is correct
4 Correct 906 ms 144024 KB Output is correct

Subtask #11
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 756 ms 144332 KB Output is correct
2 Correct 967 ms 144420 KB Output is correct
3 Correct 394 ms 144552 KB Output is correct

Subtask #12
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 557 ms 144700 KB Output is correct
2 Correct 1330 ms 144776 KB Output is correct
3 Correct 1289 ms 144692 KB Output is correct
4 Correct 1248 ms 144844 KB Output is correct
5 Correct 1265 ms 144764 KB Output is correct
6 Correct 389 ms 144892 KB Output is correct

Subtask #13
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1112 ms 102988 KB Output is correct
2 Correct 601 ms 102468 KB Output is correct

Subtask #14
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1455 ms 111024 KB Output is correct
2 Correct 1486 ms 110636 KB Output is correct
3 Correct 887 ms 110244 KB Output is correct

Subtask #15
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1846 ms 119084 KB Output is correct
2 Correct 2248 ms 118564 KB Output is correct
3 Correct 2255 ms 118352 KB Output is correct
4 Correct 1931 ms 118316 KB Output is correct
5 Correct 1279 ms 118572 KB Output is correct