Submission #561581

#	Time	Username	Problem	Language	Result	Execution time	Memory
561581		KiriLL1ca	Divide and conquer (IZhO14_divide)	C++14	100 / 100	43 ms	8400 KiB

divide

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fr first
#define sc second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pw(x) (1ll << x)
#define sz(x) (int)((x).size())
#define pb push_back
#define endl '\n'
#define vec vector

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;

template <typename T> inline bool umin (T &a, const T &b) { if (a > b) { a = b; return 1; } return 0; }
template <typename T> inline bool umax (T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }

template <typename T>
using oset = tree<T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;

#define int long long

const int N = 3e5 + 100;
int t[N << 2];
inline int get (int v, int tl, int tr, int x, int R) {
      if (tl == tr) { return tl; }
      int tm = (tl + tr) >> 1;
      if (t[v << 1] >= x && tl <= R) return get(v << 1, tl, tm, x, R);
      if (t[v << 1 | 1] >= x && tm + 1 <= R) return get(v << 1 | 1, tm + 1, tr, x, R);
      return -1;
}
inline void upd (int v, int tl, int tr, int p, int x) {
      if (tl == tr) { t[v] = x; return; }
      int tm = (tl + tr) >> 1;
      if (p <= tm) upd(v << 1, tl, tm, p, x);
      else upd(v << 1 | 1, tm + 1, tr, p, x);
      t[v] = max(t[v << 1], t[v << 1 | 1]);
}

inline void solve () {
      int n; cin >> n;
      vector <int> x (n + 1), g (n + 1), pd (n + 1), pg (n + 1);
      vector <int> cmp;
      for (int i = 1; i <= n; ++i) {
            int d; cin >> x[i] >> g[i] >> d;
            pd[i] = pd[i - 1] + d;
            pg[i] = pg[i - 1] + g[i];
      }
      int ans = 0;
      for (int i = 1; i <= n; ++i) {
            upd(1, 1, n, i, x[i] - pd[i - 1]);
            int p = get(1, 1, n, x[i] - pd[i], i);
            if (~p) umax(ans, pg[i] - pg[p - 1]);
      }
      cout << ans << endl;
}

signed main() {
      ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
      int t = 1; //cin >> t;
      while (t--) solve();
      return 0;
}

• Subtask 1: 17 / 17
• Subtask 2: 31 / 31
• Subtask 3: 52 / 52