Polish Olympiad in Informatics XIII

tetris3d.cpp

// Ivan Carvalho
// Tetris 3D - POI XIII
// O(N*sqrt(S)*sqrt(D))
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1010;
const int MAXB = 40;

struct decomp{

	int todos[MAXB],melhores[MAXB],vetor[MAXN];
	int S,BUCKET;

	void init(int _S){
		S = _S;
		BUCKET = (int)ceil(sqrt(S));
	}

	void update(int lo,int hi,int val){
		int b1 = lo/BUCKET,b2 = hi/BUCKET;
		if(b1 == b2){
			for(int i = lo;i<=hi;i++) vetor[i] = max(val,vetor[i]);
			melhores[b1] = max(melhores[b1],val);
		}
		else{
			for(int i = lo;i<=(b1+1)*BUCKET - 1;i++) vetor[i] = max(val,vetor[i]);
			for(int i = b1 + 1;i<=b2-1;i++){
				melhores[i] = max(melhores[i],val);
				todos[i] = max(todos[i],val);
			}
			for(int i = b2*BUCKET;i<=hi;i++) vetor[i] = max(val,vetor[i]);
			melhores[b1] = max(melhores[b1],val);
			melhores[b2] = max(melhores[b2],val);
		}
	}

	int query(int lo,int hi){
		int b1 = lo/BUCKET,b2 = hi/BUCKET;
		if(b1 == b2){
			int mx = 0;
			for(int i = lo;i<=hi;i++) mx = max(mx,vetor[i]);
			mx = max(mx,todos[b1]);
			return mx;
		}
		else{
			int mx = 0;
			for(int i = lo;i<=(b1+1)*BUCKET - 1;i++) mx = max(mx,vetor[i]);
			for(int i = b1 + 1;i<=b2-1;i++){
				mx = max(melhores[i],mx);
				mx = max(todos[i],mx);
			}
			for(int i = b2*BUCKET;i<=hi;i++) mx = max(mx,vetor[i]);
			mx = max(mx,todos[b1]);
			mx = max(mx,todos[b2]);
			return mx;
		}
	}

};

decomp colunas[MAXN],melhor[MAXB],todos[MAXB];
int N,D,S,BUCKET;

int main(){
	
	scanf("%d %d %d",&D,&S,&N);
	BUCKET = (int)ceil(sqrt(D));
	
	for(int i = 0;i<=D;i++) colunas[i].init(S);
	for(int i = 0;i<=D/BUCKET;i++){
		melhor[i].init(S);
		todos[i].init(S);
	}
	
	int ans = 0;

	while(N--){
		int d,s,w,x,y;
		scanf("%d %d %d %d %d",&d,&s,&w,&x,&y);
		
		int lo = x, hi = x + d - 1, y_lo = y, y_hi = y + s - 1;
		int mx = 0;
		int b1 = lo/BUCKET,b2 = hi/BUCKET;
		
		for(int idx = b1 + 1;idx <= b2 - 1;idx++){
			mx = max(mx, melhor[idx].query(y_lo,y_hi) );
		}
		for(int idx = b1;idx <= b2;idx++){
			mx = max(mx, todos[idx].query(y_lo,y_hi) );
		}
		if(b1 == b2){
			for(int idx = lo;idx <= hi;idx++) mx = max(mx, colunas[idx].query(y_lo,y_hi) );
		}
		else{
			for(int idx = lo;idx<=(b1+1)*BUCKET - 1;idx++) mx = max(mx, colunas[idx].query(y_lo,y_hi) );
			for(int idx = b2*BUCKET;idx<=hi;idx++) mx = max(mx, colunas[idx].query(y_lo,y_hi) );
		}
		
		mx += w;
		ans = max(ans,mx);
		
		for(int idx = b1 + 1;idx <= b2 - 1;idx++){
			todos[idx].update(y_lo,y_hi,mx);
		}
		for(int idx = b1;idx <= b2;idx++){
			melhor[idx].update(y_lo,y_hi,mx);
		}
		if(b1 == b2){
			for(int idx = lo;idx <= hi;idx++) colunas[idx].update(y_lo,y_hi,mx);
		}
		else{
			for(int idx = lo;idx<=(b1+1)*BUCKET - 1;idx++) colunas[idx].update(y_lo,y_hi,mx);
			for(int idx = b2*BUCKET;idx<=hi;idx++) colunas[idx].update(y_lo,y_hi,mx);
		}

	}
	
	printf("%d\n",ans);
	
	return 0;
}