JOI 2010 春合宿 day4-4 「plugs」

うん、変わった問題ですね。
ざっくり説明すると、左上と右下に1、右上と左下に-1を書き、
縦と横に一回ずつ総和を取るといいらしい。（ざっくり過ぎか。）
nが小さく限られているので、この方法が上手くいく。

#include<cstdio>
#include<algorithm>
#include<queue>
#define rep(i,n) for(int i = 0; i < n; i++)
using namespace std;



int dp[3001][3001], ans[3000], p[3000], s[3000];


int main(){
	int n, m, a, b, c, d, x, y;
	queue<int> pq, sq;
	
	scanf("%d%d",&n,&m);
	
	rep(i,m){
		scanf("%d%d%d%d",&a,&b,&c,&d);
		
		dp[a-1][c-1] ++; dp[b][d] ++;
		dp[a-1][d] --; dp[b][c-1] --;
	}
	
	
	rep(i,n+1){
		for(int j = 1; j <= n; j++){
			dp[i][j] += dp[i][j-1];
		}
	}
	rep(i,n+1){
		for(int j = 1; j <= n; j++){
			dp[j][i] += dp[j-1][i];
		}
	}
	
	
	rep(i,n){
		rep(j,n){
			if(!dp[i][j]){
				p[i]++;
				s[j]++;
			}
		}
	}
	
	rep(i,n){
		if(p[i] == 1) pq.push(i);
		if(s[i] == 1) sq.push(i);
	}
	
	while(!pq.empty() || !sq.empty()){
		
		if(pq.empty()){
			x = sq.front(); sq.pop();
			
			if(s[x] == 1){
				rep(i,n){
					if(!dp[i][x]) y = i;
				}
				
				ans[y] = x+1;
				p[y] = 0; s[x] = 0;
				
				rep(i,n){
					if(!dp[y][i]){
						dp[y][i] = 1;
						s[i] --;
						if(s[i] == 1) sq.push(i);
					}
				}
			}
		} else {
			x = pq.front(); pq.pop();
			
			if(p[x] == 1){
				rep(i,n){
					if(!dp[x][i]) y = i;
				}
				
				ans[x] = y+1;
				s[y] = 0; p[x] = 0;
				
				rep(i,n){
					if(!dp[i][y]){
						dp[i][y] = 1;
						p[i] --;
						if(p[i] == 1) pq.push(i);
					}
				}
			}
		}
	}
	
	
	rep(i,n){
		printf("%d\n", ans[i]);
	}
	
	return 0;
}