Submission #580438

#TimeUsernameProblemLanguageResultExecution timeMemory
580438thezomb1eDivide and conquer (IZhO14_divide)C++17
0 / 100
0 ms212 KiB
//thatsramen #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define eb emplace_back #define pb push_back #define ft first #define sd second #define pi pair<ll, ll> #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() #define dbg(...) dbg_out(__VA_ARGS__) using ll = long long; using ld = long double; using namespace std; using namespace __gnu_pbds; //Constants const ll INF = 5 * 1e18; const int IINF = 2 * 1e9; const ll MOD = 1e9 + 7; // const ll MOD = 998244353; const ll dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1}; const ld PI = 3.14159265359; //Templates template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) {return os << '(' << p.first << ", " << p.second << ')';} template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) {os << '['; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << ']';} void dbg_out() {cerr << endl;} template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << H << ' '; dbg_out(T...); } template<typename T> void mins(T& x, T y) {x = min(x, y);} template<typename T> void maxs(T& x, T y) {x = max(x, y);} template<typename T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; template<typename T> using omset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>; //order_of_key(k): number of elements strictly less than k //find_by_order(k): k-th element in the set void setPrec() {cout << fixed << setprecision(15);} void unsyncIO() {cin.tie(0)->sync_with_stdio(0);} void setIn(string s) {freopen(s.c_str(), "r", stdin);} void setOut(string s) {freopen(s.c_str(), "w", stdout);} void setIO(string s = "") { unsyncIO(); setPrec(); if(s.size()) setIn(s + ".in"), setOut(s + ".out"); } // #define TEST_CASES struct SegmentTree { struct Node { vector<pi> ar; vector<ll> suf; }; vector<Node> tre; int sz; SegmentTree(vector<pi> &a) { int n = (int) a.size(); sz = 1; while (sz < n) sz *= 2; tre.resize(2 * sz); build(a, 1, 0, sz); } void rcl(int x) { int p_l = 0, p_r = 0, sz_l = tre[2 * x].ar.size(), sz_r = tre[2 * x + 1].ar.size(); while ((p_l < sz_l) || (p_r < sz_r)) { if (p_r == sz_r || (p_l < sz_l && tre[2 * x].ar[p_l].ft < tre[2 * x + 1].ar[p_r].ft)) { tre[x].ar.pb(tre[2 * x].ar[p_l]); p_l++; } else { tre[x].ar.pb(tre[2 * x + 1].ar[p_r]); p_r++; } } int sz_cur = sz_l + sz_r; tre[x].suf.resize(sz_cur); for (int i = sz_cur - 1; i >= 0; i--) { tre[x].suf[i] = tre[x].ar[i].sd; if (i != sz_cur - 1) maxs(tre[x].suf[i], tre[x].suf[i + 1]); } } void build(vector<pi> &a, int x, int lx, int rx) { if (rx - lx == 1) { if (lx < a.size()) { tre[x].ar.pb(a[lx]); tre[x].suf.pb(a[lx].sd); } return; } int m = (lx + rx) / 2; build(a, 2 * x, lx, m); build(a, 2 * x + 1, m, rx); rcl(x); } ll get(int l, int r, ll bb, int x, int lx, int rx) { if (rx <= l || lx >= r) { return -INF; } if (l <= lx && r >= rx) { pi comp = {bb, -INF}; int j = lower_bound(all(tre[x].ar), comp) - tre[x].ar.begin(); return tre[x].suf[j]; } int m = (lx + rx) / 2; ll s1 = get(l, r, bb, 2 * x, lx, m); ll s2 = get(l, r, bb, 2 * x + 1, m, rx); return max(s1, s2); } ll get(int l, int r, ll bb) { return get(l, r, bb, 1, 0, sz); } }; void solve() { int n; cin >> n; vector<int> x(n), g(n), d(n); for (int i = 0; i < n; i++) { cin >> x[i] >> g[i] >> d[i]; } vector<pi> init(n); { ll pref_gold = 0, pref_energy = 0; for (int i = 0; i < n; i++) { ll len = x[i] - x[0]; init[i] = {len - pref_energy, pref_gold}; pref_energy += d[i]; pref_gold -= g[i]; } } SegmentTree st(init); ll pref_gold = 0, pref_energy = 0, ans = 0; for (int i = 0; i < n; i++) { ll len = x[i] - x[0]; pref_energy += d[i]; pref_gold += g[i]; ll bb = len - pref_energy; ll res = pref_gold + st.get(0, i + 1, bb); maxs(ans, res); } cout << ans; } int main() { setIO(); int tt = 1; #ifdef TEST_CASES cin >> tt; #endif while (tt--) solve(); return 0; }

Compilation message (stderr)

divide.cpp: In member function 'void SegmentTree::build(std::vector<std::pair<long long int, long long int> >&, int, int, int)':
divide.cpp:95:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |             if (lx < a.size()) {
      |                 ~~~^~~~~~~~~~
divide.cpp: In function 'void setIn(std::string)':
divide.cpp:44:30: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 | void setIn(string s) {freopen(s.c_str(), "r", stdin);}
      |                       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
divide.cpp: In function 'void setOut(std::string)':
divide.cpp:45:31: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 | void setOut(string s) {freopen(s.c_str(), "w", stdout);}
      |                        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...