3 条题解

  • 1
    @ 2026-10-20 18:08:04

    破环成链,复制一倍数组。直接线段树维护以 11 为起点到达每一个点的时候加好油走到下一个点之后的油量,查询区间内这一值的最小值,如果最小值为负,则一定不可。换起点时直接使用前缀和推出其新值即可。注意正反分别扫一遍。 另外,空间时间均卡线,跑慢勿笑。

    #include <bits/stdc++.h>
    #define int long long
    using namespace std;
    const int N = 1e6 + 5;
    const long long INF = 1e18;
    int n, p[N << 1], d[N << 1];
    int sp[N << 1], sd[N << 1];
    struct tree {
    	int l, r;
    	long long val;
    }tr[N << 3];
    void pushup(int u) {
    	tr[u].val = min(tr[u << 1].val, tr[u << 1 | 1].val);
    } 
    void build(int u, int l, int r) {
    	tr[u].l = l, tr[u].r = r;
    	if(l == r) {
    		tr[u].val = INF;
    		return ;
    	}
    	int mid = (l + r) >> 1;
    	build(u << 1, l, mid);
    	build(u << 1 | 1, mid + 1, r);
    	pushup(u);
    }
    void update(int u, int p, long long x) {
    	if(tr[u].l == tr[u].r) {
    		tr[u].val = x;
    		return ;
    	}
    	int mid = (tr[u].l + tr[u].r) >> 1;
    	if(p <= mid) update(u << 1, p, x);
    	else update(u << 1 | 1, p, x);
    	pushup(u);
    }
    long long query(int u, int l, int r) {
    	if(tr[u].l >= l && tr[u].r <= r) {
    		return tr[u].val;
    	}
    	if(tr[u].l > r || tr[u].r < l || l > r) return INF;
    	int mid = (tr[u].l + tr[u].r) >> 1;
    	if(r <= mid) return query(u << 1, l, r);
    	if(l > mid) return query(u << 1 | 1, l, r);
    	return min(query(u << 1, l, r), query(u << 1 | 1, l, r));
    }
    bool mark[N];
    signed main() {
    	ios :: sync_with_stdio(0);
    	cin.tie(0);
    	cout.tie(0);
    	cin >> n;
    	for(int i=1; i<=n; ++i) {
    		cin >> p[i] >> d[i];
    		p[i + n] = p[i], d[i + n] = d[i];
    	}
    	build(1, 1, n << 1);
    	for(int i=1; i<=2*n; ++i) {
    		sp[i] = sp[i - 1] + p[i];
    		sd[i] = sd[i - 1] + d[i];
    		update(1, i, sp[i] - sd[i]);
    	}
    	for(int i=1; i<=n; ++i) {
    		int L = i, R = i + n - 1;
    		long long res = query(1, L, R);
    		if(res - sp[i - 1] + sd[i - 1] < 0) mark[i] = 0;
    		else mark[i] = 1;
    	}
    	build(1, 1, n << 1);
    	for(int i=2*n; i>=1; --i) {
    		sp[i] = sp[i + 1] + p[i];
    		sd[i] = sd[i + 1] + d[i];
    		update(1, i, sp[i + 1] - sd[i]);
    	}
    	for(int i=2*n; i>=1+n; --i) {
    		int L = i - n, R = i - 1;
    		long long res = query(1, L, R);
    		if(res - sp[i + 1] + sd[i] >= 0) mark[i - n] = 1;
    	}
    	for(int i=1; i<=n; ++i) {
    		if(mark[i]) cout << "YES\n";
    		else cout << "NO\n";
    	}
    	return 0;
    }
    
    • @ 2026-10-21 10:40:06

      caohongxuan,a题数据更新了,你去试试

    • @ 2026-10-21 10:52:45

      过了

信息

ID
927
时间
1000ms
内存
256MiB
难度
9
标签
(无)
递交数
225
已通过
12
上传者