[JLOI2013]地形生成

JLOI2013过了好长时间，才写第四题。。

第一问比较好想。

第二问我想到了n^3次方的做法，但是数据。。。。于是没敢写，然后上网查了一下题解，居然是O(n^3)过的，数据这么弱。。。

/*

 * Problem: JLOI2013-Terrain

 * Author: Shun Yao

 */

#include <string.h>

#include <stdlib.h>

#include <limits.h>

#include <assert.h>

#include <stdio.h>

#include <ctype.h>

#include <math.h>

#include <time.h>

#include <map>

#include <set>

#include <list>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <bitset>

#include <utility>

#include <iomanip>

#include <numeric>

#include <sstream>

#include <iostream>

#include <algorithm>

#include <functional>

//using namespace std;

const int MAXN = 1010;

const int MOD = 2011;

int n;

std::map<int, int> ocr;

struct Data {

	int h, k;

} a[MAXN];

bool cmp(Data a, Data b) {

	return a.h != b.h ? a.h > b.h : a.k < b.k;

}

int main(/*int argc, char **argv*/) {

	int i, j, t, f[2][MAXN], ans1, ans2, cur, k;

	freopen("terrain.in", "r", stdin);

	freopen("terrain.out", "w", stdout);

	scanf("%d", &n);

	for (i = 1; i <= n; ++i) {

		scanf("%d%d", &a[i].h, &a[i].k);

		++ocr[a[i].h];

	}

	std::sort(a + 1, a + n + 1, cmp);

	ans1 = ans2 = 1;

	for (i = 1; i <= n; ) {

		t = 0;

		for (j = 0; j < ocr[a[i].h]; ++j)

			ans1 = ans1 * (std::min(i, a[i + j].k) + t++) % MOD;

		memset(f[0], 0, sizeof f[0]);

		f[0][1] = 1;

		cur = 0;

		for (j = 0; j < ocr[a[i].h]; ++j) {

			memset(f[1 - cur], 0, sizeof f[1 - cur]);

			for (k = 1; k <= std::min(i, a[i + j].k); ++k)

				f[1 - cur][k] = (f[1 - cur][k - 1] + f[cur][k]) % MOD;

			cur = 1 - cur;

		}

		t = 0;

		for (j = 1; j <= i; ++j)

			t = (t + f[cur][j]) % MOD;

		ans2 = ans2 * t % MOD;

		i += ocr[a[i].h];

	}

	printf("%d %d", ans1, ans2);

	fclose(stdin);

	fclose(stdout);

	return 0;

}