我有一个思路但是不知道对不对,写了一下不知道是我写炸了还是思路就不对

首先观察到对于一个奶牛 $i$ 他的时间应该等于自己移动的时间和等待的时间,显然前一部分是 $s_i -i + n$ 的时间,考虑后一半时间

显然只有右边的奶牛会让他停止,所以考虑右边的奶牛 $j$,如果满足奶牛 $j$ 比 $i$ 先落座,那么就意味着 $s_j - j + n < s_i -i + n$,也就是 $s_j - j < s_i - i$

那么他需要等待的就是满足 $s_j-j < s_i-i$ 的奶牛 $j$ 的放包时间 $t_j$

所以我们建一颗线段树,维护满足 $s_i - i > s_j - j$ 的 $j$ 的 $t$ 值之和

具体来说,我们从后往前扫,每次询问满足 $s_j -j < s_i - i$ 的 $j$ 的 $t_j$ 之和.然后在 $s_i-i$ 处修改贡献,注意如果同时到达应该取最大的等待时间,所以修改时不是加和而是取最大值

以上是思路,我写了个代码但是只有 10pts,求大佬指出代码或思路的错误

代码:

#include <bits/stdc++.h>
using namespace std;
const int maxn = 4e5 + 5;
int n, t[maxn], x[maxn];
struct Segtree {
	int tr[maxn << 2];
	void pushup(int t) {
		tr[t] = tr[t << 1] + tr[t << 1 | 1];
	}
	void modify(int l, int r, int pos, int t, int val) {
		if(l == r) {
			tr[t] = max(val, tr[t]);
			return ;
		}
		int mid = l + r >> 1;
		if(pos <= mid)
			modify(l, mid, pos, t << 1, val);
		else
			modify(mid + 1, r, pos, t << 1 | 1, val);
		pushup(t);
	}
	int query(int l, int r, int x, int y, int t) {
		if(x > y)
			return 0;
		if(x <= l && r <= y)
			return tr[t];
		int mid = l + r >> 1, ans = 0;
		if(x <= mid)
			ans += query(l, mid, x, y, t << 1);
		if(mid < y)
			ans += query(mid + 1, r, x, y, t << 1 | 1);
		return ans;
	}
} tree;
int main() {
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> x[i] >> t[i];
	int ans = 0;
	for (int i = n; i >= 1; i--) {
		ans = max(ans, tree.query(1, 2 * n, 1, x[i] - i + n - 1, 1) + t[i] + (x[i] + n - i));
	//	cout << tree.query(1, 2 * n, 1, x[i] - i + n - 1, 1) + t[i] << endl;
		tree.modify(1, 2 * n, x[i] - i + n, 1, t[i]);
	}
	cout << ans << endl;
	return 0;
}