AOJ 0509: Sheets

最大値の伝播で解くのは難しそうだったから、累積和で解きました。
少し枝刈りしましたが遅いです。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int g[10003][10003];
int n,r;

int main(){
	while(scanf("%d%d",&n,&r),n){
		memset(g,0,sizeof(g));
		int mx = 10001,Mx = 1,my = 10001,My = 1;
		for(int i = 0; i < n; i++){
			int a,b,c,d;
			scanf("%d%d%d%d",&a,&b,&c,&d);
			a++;b++;c++;d++;
			g[a][b]++; g[a][d]--;
			g[c][b]--; g[c][d]++;
			mx = min(mx,a);
			Mx = max(Mx,c);
			my = min(my,b);
			My = max(My,d);
		}
		
		for(int i = mx; i <= Mx; i++){
			int t = 0;
			for(int j = my; j <= My; j++){
				t += g[i][j];
				g[i][j] = t;
			}
		}
		
		int s = 0;
		for(int j = my; j <= My; j++){
			int t = 0;
			for(int i = mx; i <= Mx; i++){
				t += g[i][j];
				if(g[i][j] = t)s++;
			}
		}
		printf("%d\n",s);
		
		if(r==2){
			int l = 0;
			for(int i = mx; i <= Mx; i++){
				for(int j = my; j <= My; j++){
					if(g[i][j]){
						l += !g[i-1][j]+!g[i+1][j]+!g[i][j-1]+!g[i][j+1];
					}
				}
			}
			printf("%d\n",l);
		}
	}
	return 0;
}