Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define int int64_t
- const int mod = 998244353;
- const int max_sum = 1e5 + 1;
- int32_t main() {
- ios_base::sync_with_stdio(false);
- cin.tie(0); cout.tie(0);
- int n;
- cin >> n;
- vector<pair<int, pair<int, int>>> ev; // l, t (0 = seg, 1 = query), ind
- vector<int> seg_r(n), seg_cost(n);
- for (int i = 0; i < n; i++) {
- int seg_l;
- cin >> seg_cost[i] >> seg_l >> seg_r[i];
- ev.push_back({seg_l, {0, i}});
- }
- int m;
- cin >> m;
- vector<int> q_sum(m), q_r(m);
- for (int i = 0; i < m; i++) {
- int q_l;
- cin >> q_l >> q_sum[i] >> q_r[i];
- q_r[i] += q_l;
- ev.push_back({q_l, {1, i}});
- }
- sort(ev.begin(), ev.end());
- vector<bool> ans(m);
- vector<int> dp(max_sum, -2e18);
- dp[0] = 2e18;
- for (auto event: ev) {
- int t = event.second.first, ind = event.second.second;
- if (t == 1) {
- ans[ind] = dp[q_sum[ind]] > q_r[ind];
- continue;
- }
- for (int s = max_sum - 1; s >= seg_cost[ind]; s--) {
- dp[s] = max(dp[s], min(dp[s - seg_cost[ind]], seg_r[ind]));
- }
- }
- for (int i = 0; i < m; i++) {
- cout << (ans[i] ? "YES\n" : "NO\n");
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement