Submission #918028

#TimeUsernameProblemLanguageResultExecution timeMemory
918028borisAngelovDivide and conquer (IZhO14_divide)C++17
0 / 100
1 ms348 KiB
#include <bits/stdc++.h> using namespace std; const int maxn = 100005; const long long inf = (1LL << 62); int n; struct Element { int pos; int gold; int energy; }; Element a[maxn]; long long prefEenrgy[maxn]; struct SegmentTree { long long tree[maxn]; long long lazy[maxn]; void build(int node, int l, int r) { lazy[node] = 0; if (l == r) { tree[node] = prefEenrgy[l] - (a[l].pos - a[1].pos); return; } int mid = (l + r) / 2; build(2 * node, l, mid); build(2 * node + 1, mid + 1, r); tree[node] = max(tree[2 * node], tree[2 * node + 1]); } void pushLazy(int node, int l, int r) { tree[node] += lazy[node]; if (l != r) { lazy[2 * node] += lazy[node]; lazy[2 * node + 1] += lazy[node]; } lazy[node] = 0; } void update(int node, int l, int r, int ql, int qr, long long delta) { pushLazy(node, l, r); if (l > qr || r < ql) { return; } if (ql <= l && r <= qr) { lazy[node] += delta; pushLazy(node, l, r); return; } int mid = (l + r) / 2; update(2 * node, l, mid, ql, qr, delta); update(2 * node + 1, mid + 1, r, ql, qr, delta); tree[node] = max(tree[2 * node], tree[2 * node + 1]); } long long query(int node, int l ,int r, int ql, int qr) { pushLazy(node, l, r); if (l > qr || r < ql) { return -inf; } if (ql <= l && r <= qr) { return tree[node]; } int mid = (l + r) / 2; return max(query(2 * node, l, mid, ql, qr), query(2 * node + 1, mid + 1, r, ql, qr)); } void build() { build(1, 1, n); } void update(int l, int r, long long delta) { update(1, 1, n, l, r, delta); } long long query(int l, int r) { return query(1, 1, n, l, r); } }; SegmentTree tree; bool check(long long targetGold) { long long currentSum = 0; int ptr = 0; tree.build(); //cout << "checking for " << targetGold << endl; for (int i = 1; i <= n; ++i) { if (a[i].gold >= targetGold) { return true; } while (ptr + 1 <= n && currentSum < targetGold) { currentSum += a[ptr + 1].gold; ++ptr; } //cout << i << " :: " << ptr << " " << currentSum << endl; if (currentSum >= targetGold) { //cout << "here " << tree.query(ptr, n) << endl; if (tree.query(ptr, n) >= 0) { return true; } } else { break; } currentSum -= a[i].gold; if (i + 1 <= n) { tree.update(i + 1, n, -(a[i + 1].pos - a[i].energy)); } } return false; } void fastIO() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); } int main() { fastIO(); cin >> n; for (int i = 1; i <= n; ++i) { cin >> a[i].pos >> a[i].gold >> a[i].energy; prefEenrgy[i] = prefEenrgy[i - 1] + a[i].energy; } long long sum = 0; for (int i = 1; i <= n; ++i) { sum += a[i].gold; } long long l = 0; long long r = sum; while (l <= r) { long long mid = (l + r) / 2; if (check(mid) == true) { l = mid + 1; } else { r = mid - 1; } } cout << r << endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...