求助
查看原帖
求助
369181
bamboo1030楼主2024/9/11 16:40

人傻了,咋编译一直不过啊

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 4e5 + 5;
const double eps = 1e-9;
int rt[maxn];
struct node {
	int l, r, sum;
};
struct Segtree {
	node tr[maxn * 30];
	int tot = 0;
	void pushup(int t) {
		tr[t].sum = tr[tr[t].l].sum + tr[tr[t].r].sum;
	}
	int modify(int l, int r, int pos, int q, int val) {
		int p = ++tot;
		tr[p] = tr[q], tr[p].sum += val;
	//	cout << l << " " << r << " " << p << endl;
		if(l == r)
			return p;
		int mid = l + r >> 1;
		if(pos <= mid)
			tr[p].l = modify(l, mid, pos, tr[q].l, val);
		else
			tr[p].r = modify(mid + 1, r, pos, tr[q].r, val);
		pushup(p);
		return p;
	}
	int query(int l, int r, int pos, int p) {
		if(pos > r)
			return 0;
		if(!p)
			return 0;
		if(l == r)
			return tr[p].sum;
		int mid = l + r >> 1;
		if(pos <= mid)
			return query(l, mid, pos, tr[p].l) + tr[tr[p].r].sum;
		return query(mid + 1, r, pos, tr[p].r);
	}
} tree;
int n, m, w, Tt[maxn], x[maxn], y[maxn], a[maxn], b[maxn], c[maxn];
vector<int> v[maxn];
int l[maxn], r[maxn];
int tim[maxn], tot, dp[maxn];
int qpos(int x) {
	return lower_bound(tim + 1, tim + tot + 1, x) - tim;
}
struct Seg {
	int p, ed, l, r;
};
vector<int> bg[maxn], ed[maxn];
vector<Seg> q[maxn];
int f[maxn], t[maxn];
int cal(int l, int r) {
	if(l > r)
		return 0;
	return tree.query(1, tot, l + 1, rt[r - 1]);
}
int calc(int id, int x, int l, int r) {
	return dp[id] + Tt[x] * cal(l, r);
}
void add(int p, int ed, int i) {
	while(f[p] < t[p]) {
		Seg tmp = q[p][t[p] - 1];
		if(calc(tmp.p, p, tmp.ed, tmp.l) >= calc(i, p, ed, tmp.l))
			t[p]--, q[p].pop_back();
		else if(calc(tmp.p, p, tmp.ed, tmp.r) < calc(i, p, ed, tmp.r)) {
			if(tmp.r != tot)
				q[p].push_back(Seg{i, ed, tmp.r + 1, tot});
			break;
		}
		else {
			int l = tmp.l - 1, r = tmp.r;
			while(l + 1 < r) {
				int mid = l + r >> 1;
				if(calc(tmp.p, p, tmp.ed, mid) < calc(i, p, ed, mid))
					l = mid;
				else
					r = mid;
			}
			q[p][t[p] - 1].r = l;
			t[p]++, q[p].push_back(Seg{i, ed, r, tot});
		}
	}
	if(f[p] == t[p]) {
		t[p]++;
		q[p].push_back(Seg{i, ed, 1, tot});
	}
}
long long solve(int N, int M, int W, std::vector<int> T,
                std::vector<int> X, std::vector<int> Y,
                std::vector<int> A, std::vector<int> B, std::vector<int> C,
                std::vector<int> L, std::vector<int> R){

	n = N, m = M, w = W;
	for (int i = 1; i <= n; i++)
		Tt[i] = T[i - 1];
	for (int i = 1; i <= m; i++)
		x[i] = X[i - 1], y[i] = Y[i - 1], a[i] = A[i - 1], b[i] = B[i - 1], c[i] = C[i - 1], tim[++tot] = a[i], tim[++tot] = b[i], x[i]++, y[i]++;
	x[0] = 1, y[0] = 1, a[0] = 0, b[0] = 0;
	for (int i = 1; i <= w; i++)
		l[i] = L[i - 1], r[i] = R[i - 1], tim[++tot] = l[i], tim[++tot] = r[i];
	sort(tim + 1, tim + tot + 1);
	tot = unique(tim + 1, tim + tot + 1) - tim - 1;
	for (int i = 1; i <= m; i++)
		a[i] = qpos(a[i]), b[i] = qpos(b[i]);
	for (int i = 1; i <= w; i++)
		l[i] = qpos(l[i]), r[i] = qpos(r[i]);
	for (int i = 1; i <= w; i++) 
		v[r[i]].push_back(l[i]);
	for (int i = 1; i <= tot; i++) {
		rt[i] = rt[i - 1];
		for (int j = 0; j < v[i].size(); j++)
			rt[i] = tree.modify(1, tot, v[i][j], rt[i], 1);
	}
	for (int i = 0; i <= m; i++)
		bg[a[i]].push_back(i);
	q[1].push_back(Seg{0, x[0], 1, tot});
	t[1]++;
	int ans = 9e18;
	for (int i = 0; i <= tot; i++) {
	//	cout << i << endl;
		int nw = ed[i].size();
		for (int j = 0; j < ed[i].size(); j++) {
			int p = ed[i][j];
			add(y[p], b[p], p);
		}
		for (int j = 0; j < bg[i].size(); j++) {
			int p = bg[i][j];
			while(f[x[p]] < t[x[p]] && q[x[p]][f[x[p]]].r < i)
				f[x[p]]++;
			if(f[x[p]] == t[x[p]])
				continue;
			Seg k = q[x[p]][f[x[p]]];
			dp[p] = calc(k.p, x[p], k.ed, a[p]) + c[p];
			ed[b[p]].push_back(p);
		//	cout << p << " " << dp[p] << " " << tim[k.ed] << " " << cal(k.ed, a[p]) << endl;
			if(y[p] == n)
				ans = min(ans, calc(p, n, b[p], tot + 1));
		}	
		for (int j = nw; j < ed[i].size(); j++) {
			int p = ed[i][j];
			add(y[p], b[p], p);
		}
	}
//	cout << cal(qpos(15), qpos(20)) << endl;
	return (ans == 9e18 ? -1 : ans);
}
2024/9/11 16:40
加载中...