记录编号	223345	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2011]拆迁队	最终得分	100
用户昵称	thomount	是否通过	通过
代码语言	C++	运行时间	3.713 s
提交时间	2016-02-09 20:29:19	内存使用	192.55 MiB

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int read() {
	char ch = getchar();
	while (ch < '0' || ch > '9') ch = getchar();
	int ans = 0;
	while (ch >= '0' && ch <= '9') ans = ans * 10 + ch - '0', ch = getchar();
	return ans;
}
const int ml = 200000000, N = 300010;
const long long Ml = 1LL << 60;
const double eps = 0.00000001;
struct point {
	int l, r, ans;
	point * ls, * rs;
	point(int l = 0, int r = 0): l(l), r(r), ans(-1), ls(0), rs(0) {}
	void update() {
		ans = -1;
		if (ls) ans = max(ans, ls->ans);
		if (rs) ans = max(ans, rs->ans);
	}
} D[N * 30];
typedef point * link;
link head;
int ptt = 0;
link make(int l, int r) {
	D[++ptt] = point(l, r);
	return &D[ptt];
}

void add(link p, int x, int y) {
	if (p->l == p->r) {
		p->ans = max(p->ans, y);
		return;
	}
	int mid = (p->l + p->r) >> 1;
	if (x <= mid) {
		if (!p->ls) p->ls = make(p->l, mid);
		add(p->ls, x, y); 
	} else {
		if (!p->rs) p->rs = make(mid+1, p->r);
		add(p->rs, x, y);
	}
	p->update();
}

int check(link p, int x) {
	if (!p) return -1;
	if (p->r <= x) return p->ans;
	int mid = (p->l + p->r) >> 1;
	int ans = check(p->ls, x);
	if (x > mid) ans = max(ans, check(p->rs, x));
	return ans;
}

long long st[N], en[N], a[N], b[N], ans[N], s[N];
long long cost[N], Y[N];
int f[N], q[N];
int main() {
	freopen("lanxisi.in", "r", stdin);
	freopen("lanxisi.out", "w", stdout);
	int n = read();
	for (int i = 1; i <= n; i++) a[i] = read();
	for (int i = 1; i <= n; i++) b[i] = read();
	a[++n] = ml; b[n] = 0;
	head = make(0, ml);
	
	add(head, 0, 0);
	for (int i = 1; i <= n; i++) {
		ans[i] = check(head, a[i]-i)+1;
		add(head, a[i]-i, ans[i]);
	}
	
	printf("%d ", ans[n] - 1);
	
	for (int i = 0; i <= n; i++) s[ans[i]]++;
	for (int i = 1; i <= n; i++) s[i] += s[i-1];
	for (int i = 1; i <= n; i++) st[i] = s[i-1]+1, en[i] = st[i] - 1;
	st[0] = 1, en[0] = 1;
	f[0] = -1;
	q[1] = 0;
	cost[0] = 0;
	for (int i = 1; i <= n; i++) {
		cost[i] = Ml;
		int x = ans[i] - 1;
		int stat = max(st[x], en[x] - 800);
		for (int j = stat; j <= en[x]; j++) {
			if (a[q[j]] - q[j] <= a[i] - i) {
				long long kk = cost[q[j]] + a[q[j]]*(i-q[j]-1) + (long long)(i-q[j]-1)*(i-q[j])/2 + a[i]+b[i];
				if (kk < cost[i]) {
					cost[i] = kk;
				}
			}
		}
		q[++en[ans[i]]] = i;
	}
	
	printf("%lld\n", cost[n] - a[n]);
	return 0;
}