oj.uz

Submission #95040

# Submission time Handle Problem Language Result Execution time Memory
95040 2019-01-27T06:53:20 Z Retro3014 Pyramid Base (IOI08_pyramid_base) C++17
35 / 100
 1840 ms 179844 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <stdio.h>

using namespace std;
typedef long long ll;

int N, M, P;
struct SEG{
	SEG (int l, int r, ll lazy, ll mn) : l(l), r(r), lazy(lazy), mn(mn)	{}
	int l, r;
	ll lazy, mn;
};
vector<SEG> seg;
SEG ss(-1, -1, 0, 0);
struct SQ{
	SQ (int x1, int x2, int y1, int y2, ll c) : x1(x1), x2(x2), y1(y1), y2(y2), c(c) {}
	int x1, x2, y1, y2;
	ll c;
};
vector<SQ> sc;



ll B;
struct LINE{
	LINE (int x, int y1, int y2, ll c) : x(x), y1(y1), y2(y2), c(c) {}
	int x, y1, y2;
	ll c;
	bool operator <(const LINE &a)const{
		return x<a.x;
	}
};
vector<LINE> line;

void lazy(int idx, int s, int e, int l, int r, ll cost){
	if(seg[idx].lazy!=0){
		if(seg[idx].l==-1)	{seg[idx].l = seg.size(); seg.push_back(ss);}
		if(seg[idx].r==-1)	{seg[idx].r = seg.size(); seg.push_back(ss);}
		seg[seg[idx].l].lazy+=seg[idx].lazy; seg[seg[idx].l].mn += seg[idx].lazy;
		seg[seg[idx].r].lazy+=seg[idx].lazy; seg[seg[idx].r].mn += seg[idx].lazy;
		seg[idx].lazy = 0;
	}
	if(l<=s && e<=r){
		seg[idx].lazy+=cost;	seg[idx].mn+=cost;	return;
	}
	if(e<l || s>r)	return;
	if(seg[idx].l==-1)	{seg[idx].l = seg.size(); seg.push_back(ss);}
	if(seg[idx].r==-1)	{seg[idx].r = seg.size(); seg.push_back(ss);}
	lazy(seg[idx].l, s, (s+e)/2, l, r, cost);
	lazy(seg[idx].r, (s+e)/2+1, e, l, r, cost);
	seg[idx].mn = min(seg[seg[idx].l].mn, seg[seg[idx].r].mn);
}

struct SEG2{
	SEG2 (int l, int r, int lmn, int rmn, int smn, int mn, int lazy, int len) : l(l), r(r), lmn(lmn), rmn(rmn), smn(smn), mn(mn), lazy(lazy), len(len) {}
	int l, r;
	int lmn, rmn, smn;
	int mn, lazy, len;
};
vector<SEG2> seg2;
vector<LINE> l1, l2;

void init(int idx, int s, int e){
	seg2.push_back({-1, -1, e-s+1, e-s+1, e-s+1, 0, 0, e-s+1});
	if(s==e)	return;
	seg2[idx].l=seg2.size();
	init(seg2[idx].l, s, (s+e)/2);
	seg2[idx].r=seg2.size();
	init(seg2[idx].r, (s+e)/2+1, e);
}

void update(int idx, int s, int e, int l, int r, int c){
	if(s!=e && seg2[idx].lazy!=0){
		seg2[seg[idx].l].mn+=seg2[idx].lazy; seg2[seg2[idx].l].lazy+=seg2[idx].lazy;
		seg2[seg[idx].r].mn+=seg2[idx].lazy; seg2[seg2[idx].r].lazy+=seg2[idx].lazy;
		seg2[idx].lazy = 0;
	}
	if(l<=s && e<=r){
		seg2[idx].lazy+=c; seg2[idx].mn+=c;	return;
	}
	if(l>e || s>r)	return;
	update(seg2[idx].l, s, (s+e)/2, l, r, c);
	update(seg2[idx].r, (s+e)/2+1, e, l, r, c);
	if(seg2[seg2[idx].l].mn==seg2[seg2[idx].r].mn){
		seg2[idx].mn = seg2[seg2[idx].l].mn;
		seg2[idx].smn = max(seg2[seg2[idx].l].smn, max(seg2[seg2[idx].r].smn, seg2[seg2[idx].l].rmn+seg2[seg2[idx].r].lmn));
		if(seg2[seg2[idx].l].lmn == seg2[seg2[idx].l].len)	seg2[idx].lmn = seg2[seg2[idx].l].lmn + seg2[seg2[idx].r].lmn;
		else	seg2[idx].lmn = seg2[seg2[idx].l].lmn; 
		if(seg2[seg2[idx].r].rmn == seg2[seg2[idx].r].len)	seg2[idx].rmn = seg2[seg2[idx].r].rmn + seg2[seg2[idx].l].rmn;
		else seg2[idx].rmn = seg2[seg2[idx].r].rmn;
	}else if(seg2[seg2[idx].l].mn<seg2[seg2[idx].r].mn){
		seg2[idx].mn = seg2[seg2[idx].l].mn;
		seg2[idx].smn = seg2[seg2[idx].l].smn;
		seg2[idx].lmn = seg2[seg2[idx].l].lmn; seg2[idx].rmn = 0;
	}else{
		seg2[idx].mn = seg2[seg2[idx].r].mn;
		seg2[idx].smn = seg2[seg2[idx].r].smn;
		seg2[idx].lmn = 0; seg2[idx].rmn = seg2[seg2[idx].r].rmn;
	}
	return;
}


void solve(){
	scanf("%d", &P);
	for(int i=0; i<P; i++){
		int a, b, c, d, e;
		scanf("%d%d%d%d%d", &a, &b, &c, &d, &e);
		l1.push_back({a, b, d, 1});
		l2.push_back({c, b, d, -1});
	}
	sort(l1.begin(), l1.end()); sort(l2.begin(), l2.end());
	init(0, 1, M);
	int s = 1, e = 0;
	int idx1 = 0, idx2 = 0;
	int ans = 0;
	while(e<=N){
		int h = seg2[0].smn;
		//printf("%d %d %d\n", s, e, h);
		ans = max(ans, min(h, e-s+1));
		if(h>=(e-s+1) || s==e){
			e++;
			while(idx1<l1.size() && l1[idx1].x==e){
				update(0, 1, M, l1[idx1].y1, l1[idx1].y2, 1);	idx1++;
			}
		}else{
			while(idx2<l2.size() && l2[idx2].x==s){
				//cout<<1<<endl;
				update(0, 1, M, l2[idx2].y1, l2[idx2].y2, -1); idx2++;
			}	
			s++;
		}
	}
	printf("%d", ans);
	return;
}


int main(){
	scanf("%d%d", &N, &M);
	scanf("%lld", &B);
	if(B==0){
		solve();
		return 0;
	}
	N*=2; M*=2;
	scanf("%d", &P);	
	for(int i=0; i<P; i++){
		int a, b, c, d, e;
		scanf("%d%d%d%d%d", &a, &b, &c, &d, &e);
		a--; b--;
		sc.push_back({a*2, c*2, b*2, d*2, (ll)e});
	}
	int s = 0, e = (min(N, M))/2, m;
	while(s<e){
		m = (s+e)/2+1;
		seg.clear();
		seg.push_back({-1, -1, 0, 0});
		line.clear();
		for(int i=0; i<sc.size(); i++){
			SQ now = sc[i];
			now.x1-=(m-1);	now.y1-=(m-1); now.x2+=(m-1); now.y2+=(m-1);
			line.push_back({max(m, now.x1), max(m, now.y1), min(M-m, now.y2), now.c});
			line.push_back({max(m, now.x2), max(m, now.y1), min(M-m, now.y2), -now.c});
		}
		line.push_back({m, m, m, 0});
		sort(line.begin(), line.end());
		//printf("%d\n", m);
		for(int i=0; i<line.size(); i++){
			//printf("%d %d %d %lld\n", line[i].x, line[i].y1, line[i].y2, line[i].c);
			if(line[i].x>N-m)	break;
			if(i!=0 && line[i].x!=line[i-1].x){
				if(seg[0].mn<=B){
					s = m;	break;
				}
			}
			lazy(0, m, M-m, line[i].y1, line[i].y2, line[i].c);
		}
		if(seg[0].mn<=B){
			s = m;
		}
		if(s==m)	continue;
		else	e = m-1;
	}
	printf("%d", s);
	return 0;
}

Compilation message

pyramid_base.cpp: In function 'void solve()':
pyramid_base.cpp:125:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while(idx1<l1.size() && l1[idx1].x==e){
          ~~~~^~~~~~~~~~
pyramid_base.cpp:129:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while(idx2<l2.size() && l2[idx2].x==s){
          ~~~~^~~~~~~~~~
pyramid_base.cpp: In function 'int main()':
pyramid_base.cpp:162:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<sc.size(); i++){
                ~^~~~~~~~~~
pyramid_base.cpp:171:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<line.size(); i++){
                ~^~~~~~~~~~~~
pyramid_base.cpp: In function 'void solve()':
pyramid_base.cpp:107:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &P);
  ~~~~~^~~~~~~~~~
pyramid_base.cpp:110:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d%d%d", &a, &b, &c, &d, &e);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
pyramid_base.cpp: In function 'int main()':
pyramid_base.cpp:142:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &M);
  ~~~~~^~~~~~~~~~~~~~~~
pyramid_base.cpp:143:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld", &B);
  ~~~~~^~~~~~~~~~~~
pyramid_base.cpp:149:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &P); 
  ~~~~~^~~~~~~~~~
pyramid_base.cpp:152:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d%d%d", &a, &b, &c, &d, &e);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 760 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 2028 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 22 ms 13320 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 194 ms 126096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 66200 KB Output is correct
2 Runtime error 201 ms 126032 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #8
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 1716 KB Output is correct
2 Correct 80 ms 2520 KB Output is correct
3 Correct 70 ms 2608 KB Output is correct

Subtask #9
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 269 ms 7776 KB Output is correct
2 Correct 582 ms 14084 KB Output is correct
3 Correct 375 ms 7816 KB Output is correct

Subtask #10
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 274 ms 14288 KB Output is correct
2 Correct 32 ms 2528 KB Output is correct
3 Correct 280 ms 26576 KB Output is correct
4 Correct 670 ms 26704 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 533 ms 14684 KB Output is correct
2 Correct 1357 ms 26896 KB Output is correct
3 Correct 139 ms 8468 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 392 ms 14984 KB Output is correct
2 Correct 1840 ms 27336 KB Output is correct
3 Correct 1749 ms 27308 KB Output is correct
4 Correct 1783 ms 27424 KB Output is correct
5 Correct 1591 ms 27340 KB Output is correct
6 Correct 113 ms 8928 KB Output is correct

Subtask #13
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 340 ms 153084 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #14
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 448 ms 170444 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #15
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1233 ms 93264 KB Output is correct
2 Runtime error 509 ms 179844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -