3 条题解
-
1
破环成链,复制一倍数组。直接线段树维护以 为起点到达每一个点的时候加好油走到下一个点之后的油量,查询区间内这一值的最小值,如果最小值为负,则一定不可。换起点时直接使用前缀和推出其新值即可。注意正反分别扫一遍。 另外,空间时间均卡线,跑慢勿笑。
#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; }
信息
- ID
- 927
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 9
- 标签
- (无)
- 递交数
- 225
- 已通过
- 12
- 上传者