oj.uz

Submission #68059

# Submission time Handle Problem Language Result Execution time Memory
68059 2018-08-15T20:30:29 Z spencercompton Pyramid Base (IOI08_pyramid_base) C++14
70 / 100
 5000 ms 175712 KB 
#include <bits/stdc++.h>
using namespace std;
int inf = 2000000069;
class Node{
public:
	Node *l, *r;
	int mini, lazy, s, e;
	Node (int a, int b){
		s = a;
		e = b;
		lazy = 0;
		mini = 0;
		if(s==e){
			l = NULL;
			r = NULL;
		}
		else{
			l = new Node(s,(s+e)/2);
			r = new Node((s+e)/2+1,e);
		}
	}
	void res(){
		mini = 0;
		lazy = 0;
		if(s!=e){
			l->res();
			r->res();
		}
	}
	void push(){
	    if(s!=e){
	        l->mini += lazy;
	        l->lazy += lazy;
	        r->mini += lazy;
	        r->lazy += lazy;
	    }
	    lazy = 0;
	}
	void pull(){
	    if(s!=e){
	        mini = min(l->mini,r->mini);
	    }
	}
	void add(int st, int en, int val){
		if(st<=s && e <= en){
			lazy += val;
			mini += val;
			return;
		}
		push();
		if(st<=(s+e)/2){
			l->add(st,en,val);
		}
		if(en>(s+e)/2){
			r->add(st,en,val);
		}
		pull();
	}
	// int gmin(int st, int en){
	// 	if(st<=s && e <= en){
	// 		return mini;
	// 	}
	// 	push();
	// 	int ret = inf;
	// 	if(st<=(s+e)/2){
	// 		ret = min(ret,l->gmin(st,en));
	// 	}
	// 	if(en>(s+e)/2){
	// 		ret = min(ret,r->gmin(st,en));
	// 	}
	// 	return ret;
	// }
};

class Obj{
public:
	int x, y1, y2, c;
	bool add;
	Obj(int a , int b, int d, int e, bool f){
		x = a;
		y1 = b;
		y2 = d;
		c = e;
		add = f;
	}
	bool operator<(const Obj &o) const{
		if(x!=o.x){
			return x<o.x;
		}
		if(add && !o.add){
			return true;
		}
		return false;
	}
};

class Rect{
public:
	//get Rekt
	int x1, y1, x2, y2, c;
	Rect(int a, int b, int d, int e, int f){
		x1 = a;
		y1 = b;
		x2 = d;
		y2 = e;
		c = f;
	}
};

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int col, row, bud, p;
	cin >> col >> row >> bud >> p;
	vector<Rect> li;
	for(int i = 0; i<p; i++){
		int a, b,c,d,e;
		cin >> a >> b >> c >> d >> e;
		a--;
		b--;
		c--;
		d--;
		if(bud==0){
			e = 1;
		}
		li.push_back(Rect(a,b,c,d,e));
	}
	Node *t = new Node(0,row-1);
	int lo = 0;
	int hi = min(col,row);
	while(lo<hi){
		t->res();
		int mid = (lo+hi+1)/2;
		bool ok = false;
		vector<Obj> li2;
		int f = 0;
		int s = row-mid;
		int last = col-mid;
		for(int i = 0; i<p; i++){
			li2.push_back(Obj(max(0,li[i].x1-mid+1),max(0,li[i].y1-mid+1),li[i].y2,li[i].c,true));
			if(li2.back().x>last){
				li2.pop_back();
			}
			li2.push_back(Obj(li[i].x2+1,max(0,li[i].y1-mid+1),li[i].y2,li[i].c,false));
			if(li2.back().x>last){
				li2.pop_back();
			}
		}
		sort(li2.begin(),li2.end());
		if(s<row-1){
			t->add(s+1,row-1,bud+1);
		}
		bool zero = true;
		for(int i =0; i<li2.size() && !ok; i++){
			if(zero && li2[i].x>0){
				zero = false;
				ok |= t->mini<=bud;
				if(ok){
					break;
				}
			}
			if(li2[i].x>last){
				break;
			}
			if(li2[i].add){
				t->add(li2[i].y1,li2[i].y2,li2[i].c);
			}
			else{
				t->add(li2[i].y1,li2[i].y2,-li2[i].c);
				ok |= t->mini<=bud;
			}
		}
		if(!ok){
			ok |= t->mini<=bud;
		}
		if(ok){
			lo = mid;
		}
		else{
			hi = mid-1;
		}
	}
	cout << lo << endl;
}

Compilation message

pyramid_base.cpp: In function 'int main()':
pyramid_base.cpp:154:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i =0; i<li2.size() && !ok; i++){
                 ~^~~~~~~~~~~
pyramid_base.cpp:136:7: warning: unused variable 'f' [-Wunused-variable]
   int f = 0;
       ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 476 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 716 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1784 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 10316 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 502 ms 94936 KB Output is correct
2 Correct 526 ms 95024 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 517 ms 95116 KB Output is correct
2 Correct 508 ms 95116 KB Output is correct

Subtask #8
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 95116 KB Output is correct
2 Correct 70 ms 95116 KB Output is correct
3 Correct 60 ms 95116 KB Output is correct

Subtask #9
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 379 ms 95116 KB Output is correct
2 Correct 610 ms 95116 KB Output is correct
3 Correct 461 ms 95116 KB Output is correct

Subtask #10
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1085 ms 98860 KB Output is correct
2 Correct 60 ms 98860 KB Output is correct
3 Correct 506 ms 99592 KB Output is correct
4 Correct 1168 ms 101236 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1365 ms 101964 KB Output is correct
2 Correct 1805 ms 103008 KB Output is correct
3 Correct 1033 ms 103008 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1374 ms 104344 KB Output is correct
2 Correct 2309 ms 105740 KB Output is correct
3 Correct 2071 ms 106648 KB Output is correct
4 Correct 2351 ms 107572 KB Output is correct
5 Correct 2377 ms 108504 KB Output is correct
6 Correct 1041 ms 108504 KB Output is correct

Subtask #13
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5101 ms 133956 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 158816 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 5072 ms 175712 KB Time limit exceeded
2 Halted 0 ms 0 KB -