Submission #1167439

#TimeUsernameProblemLanguageResultExecution timeMemory
1167439SG2AlokArt Exhibition (JOI18_art)C++20
100 / 100
500 ms28612 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> using namespace std; typedef long long ll; using namespace __gnu_pbds; #define endl '\n' #define hitaf ios_base::sync_with_stdio(false); cin.tie(0); #define fi first #define se second template <typename T> using ordered_set = tree<T,null_type,less<T>,rb_tree_tag, tree_order_statistics_node_update>; const ll MOD = 1e9 + 7; const ll MOD1 = 998244353; const ll INF = 4500000000000000000LL; const ll mod1 = 6900000469; const ll mod2 = 698000002369; ll n, m, q, k, a[1200005], b[500005], c[500005], st[2000005], lazy[2000005]; string s, s1, s2; void prop(ll pos){ st[pos * 2] += lazy[pos]; st[pos * 2 + 1] += lazy[pos]; lazy[pos * 2] += lazy[pos]; lazy[pos * 2 + 1] += lazy[pos]; lazy[pos] = 0; } void update(ll l, ll r, ll L, ll R, ll pos, ll val){ if(l > R || r < L) return; if(L <= l && r <= R){ st[pos] += val; lazy[pos] += val; return; } prop(pos); ll mid = (l + r) / 2; update(l, mid, L, R, pos * 2, val); update(mid + 1, r, L, R, pos * 2 + 1, val); st[pos] = max(st[pos * 2], st[pos * 2 + 1]); } void update2(ll l, ll r, ll idx, ll pos, ll val){ if(l == r){ st[pos] += val; return; } prop(pos); ll mid = (l + r) / 2; if(idx <= mid) update2(l, mid, idx, pos * 2, val); else update2(mid + 1, r, idx, pos * 2 + 1, val); st[pos] = max(st[pos * 2], st[pos * 2 + 1]); } ll query(ll l, ll r, ll L, ll R, ll pos){ if(l > R || r < L) return -INF; if(L <= l && r <= R) return st[pos]; prop(pos); ll mid = (l + r) / 2; return max(query(l, mid, L, R, pos * 2), query(mid + 1, r, L, R, pos * 2 + 1)); } int main(){ hitaf int T = 1; // cin >> T; while(T--){ cin >> n; for(int i = 1; i <= n; i++) cin >> a[i] >> b[i]; vector<ll> ord(n + 1); iota(ord.begin(), ord.end(), 0); sort(ord.begin() + 1, ord.end(), [&](ll x, ll y){ return a[x] < a[y]; }); ll ans = -INF; for(int i = 1; i <= n; i++){ ll x = ord[i]; update(1, n, 1, i, 1, b[x] - a[x]); update2(1, n, i, 1, a[x]); ans = max(ans, query(1, n, 1, i, 1)); update(1, n, 1, i, 1, a[x]); } cout << ans << endl; } return 0; } /* dp[i][j] = */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...