oj.uz

Submission #68065

# Submission time Handle Problem Language Result Execution time Memory
68065 2018-08-15T20:49:20 Z spencercompton Pyramid Base (IOI08_pyramid_base) C++17
70 / 100
 5000 ms 138124 KB 
#include <bits/stdc++.h>
using namespace std;
int inf = 2000000069;
class Node{
public:
	Node *l, *r;
	int mini, lazy, s, e;
	bool res;
	Node (int a, int b){
		s = a;
		e = b;
		lazy = 0;
		mini = 0;
		res = false;
		if(s==e){
			l = NULL;
			r = NULL;
		}
		else{
			l = new Node(s,(s+e)/2);
			r = new Node((s+e)/2+1,e);
		}
	}
	void push(){
		if(s!=e && res){
			res = false;
			l->mini = 0;
			l->lazy = 0;
			l->res = true;
			r->mini = 0;
			r->lazy = 0;
			r->res = true;
			res = false;
		}
	    if(s!=e && lazy!=0){
	        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){
		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;
		}
		t->res = true;
		t->mini = 0;
		t->lazy = 0;
	}
	cout << lo << endl;
}

Compilation message

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

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 520 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 10016 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 94548 KB Output is correct
2 Correct 163 ms 94548 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 94592 KB Output is correct
2 Correct 159 ms 94592 KB Output is correct

Subtask #8
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 94592 KB Output is correct
2 Correct 83 ms 94592 KB Output is correct
3 Correct 61 ms 94592 KB Output is correct

Subtask #9
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 363 ms 94592 KB Output is correct
2 Correct 608 ms 94592 KB Output is correct
3 Correct 436 ms 94592 KB Output is correct

Subtask #10
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 759 ms 96188 KB Output is correct
2 Correct 64 ms 96188 KB Output is correct
3 Correct 418 ms 96188 KB Output is correct
4 Correct 935 ms 97068 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1167 ms 97128 KB Output is correct
2 Correct 1608 ms 97400 KB Output is correct
3 Correct 743 ms 97400 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1188 ms 97400 KB Output is correct
2 Correct 2055 ms 97560 KB Output is correct
3 Correct 1866 ms 97708 KB Output is correct
4 Correct 2155 ms 97840 KB Output is correct
5 Correct 2220 ms 97840 KB Output is correct
6 Correct 843 ms 97840 KB Output is correct

Subtask #13
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5044 ms 116896 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 5042 ms 132568 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 5044 ms 138124 KB Time limit exceeded
2 Halted 0 ms 0 KB -