Submission #68059

#	Time	Username	Problem	Language	Result	Execution time	Memory
68059		spencercompton	Pyramid Base (IOI08_pyramid_base)	C++14	70 / 100	5101 ms	175712 KiB

pyramid_base

#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 (stderr)

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 / 5
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 5 / 5
• Subtask 8: 7 / 7
• Subtask 9: 7 / 7
• Subtask 10: 7 / 7
• Subtask 11: 7 / 7
• Subtask 12: 7 / 7
• Subtask 13: 0 / 10
• Subtask 14: 0 / 10
• Subtask 15: 0 / 10