Submission #200170

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
200170	2020-02-05T15:34:59 Z	EntityIT	Two Dishes (JOI19_dishes)	C++14	0 / 100	441 ms	55464 KB

dishes

#include<bits/stdc++.h>

using namespace std;

#define all(x) (x).begin(), (x).end()
#define sz(x) ( (int)(x).size() )
using LL = long long;

template<class T>
inline bool asMn(T &a, const T &b) { return a > b ? a = b, true : false; }
template<class T>
inline bool asMx(T &a, const T &b) { return a < b ? a = b, true : false; }

mt19937 rng( (uint32_t)chrono::steady_clock::now().time_since_epoch().count() );

int n, m;
vector<int> p, q;
vector<LL> s, t, pSA, pSB;

struct It {
  vector<LL> sum;
  vector<bool> lz;
  It(int nNode) { sum.assign(nNode, 0); lz.assign(nNode, false); }

  void trueVal(int i, int Left, int Right) {
    if (!lz[i]) return ;
    sum[i] = 0;
    if (Left != Right) lz[i << 1] = lz[i << 1 | 1] = lz[i];
    lz[i] = false;
  }

  void upd(int l, int r, int i = 1, int Left = 0, int Right = m) {
    trueVal(i, Left, Right);
    if (l <= Left && Right <= r) {
      lz[i] = true; trueVal(i, Left, Right);
      return ;
    }
    int Mid = (Left + Right) >> 1;
    if (l <= Mid) upd(l, r, i << 1, Left, Mid);
    if (Mid < r) upd(l, r, i << 1 | 1, Mid + 1, Right);
    sum[i] = sum[i << 1] + sum[i << 1 | 1];
  }
  void add(int pos, LL val, int i = 1, int Left = 0, int Right = m) {
    trueVal(i, Left, Right);
    sum[i] += val;

    if (Left == Right) return ;
    int Mid = (Left + Right) >> 1;
    if (pos <= Mid) add(pos, val, i << 1, Left, Mid);
    else add(pos, val, i << 1 | 1, Mid + 1, Right);
  }

  int findPos(int l, LL &cur, int i = 1, int Left = 0, int Right = m) {
    trueVal(i, Left, Right);
    if (l <= Left && sum[i] < cur) {
      cur -= sum[i];
      return m + 1;
    }

    if (Left == Right) return Left;

    int Mid = (Left + Right) >> 1;
    int tmp;
    if (l <= Mid && (tmp = findPos(l, cur, i << 1, Left, Mid) ) <= m) return tmp;
    else return findPos(l, cur, i << 1 | 1, Mid + 1, Right);
  }
  LL get(int l, int r, int i = 1, int Left = 0, int Right = m) {
    trueVal(i, Left, Right);
    if (l <= Left && Right <= r) return sum[i];
    int Mid = (Left + Right) >> 1;
    if (Mid < l) return get(l, r, i << 1 | 1, Mid + 1, Right);
    else if (r <= Mid) return get(l, r, i << 1, Left, Mid);
    else return get(l, r, i << 1, Left, Mid) + get(l, r, i << 1 | 1, Mid + 1, Right);
  }
};

int main() {
  ios_base::sync_with_stdio(0); cin.tie(0);

  #ifdef FourLeafClover
  freopen("input", "r", stdin);
  #endif // FourLeafCLover

  cin >> n >> m;
  pSA.assign(n + 1, 0);
  pSB.assign(m + 1, 0);
  s.assign(n + 1, 0);
  t.assign(m + 1, 0);
  p.assign(n + 1, 0);
  q.assign(m + 1, 0);

  for (int i = 1; i <= n; ++i) {
    cin >> pSA[i] >> s[i] >> p[i];
    pSA[i] += pSA[i - 1];
  }

  for (int i = 1; i <= m; ++i) {
    cin >> pSB[i] >> t[i] >> q[i];
    pSB[i] += pSB[i - 1];
  }

  vector<int> mxI(m + 1);
  vector<vector<int> > changeMxI(n + 1);
  for (int j = 0; j <= m; ++j) {
    mxI[j] = (int)(upper_bound(all(pSA), t[j] - pSB[j]) - pSA.begin() ) - 1;
    if (mxI[j] + 1 <= n) changeMxI[ mxI[j] + 1 ].emplace_back(j);
  }

  It it( (m + 5) << 2);

  auto upd = [&](int pos) {
    LL tmp = it.get(pos, pos);

    if (tmp >= 0) return ;

    tmp = -tmp;
    int r = it.findPos(pos + 1, tmp);
    it.add(r, it.get(pos, r - 1) );
    it.upd(pos, r - 1);
  };

  for (int i = 1; i <= n; ++i) {
    int mxJ = (int)(upper_bound(all(pSB), s[i] - pSA[i]) - pSB.begin() ) - 1;

    vector<int> tmp;
    if (mxJ >= 0) {
      it.add(0, p[i]); tmp.emplace_back(0);
      if (mxJ < m) {
        it.add(mxJ + 1, -p[i]);
        tmp.emplace_back(mxJ + 1);
      }
    }

    for (auto j : changeMxI[i]) {
      it.add(j, q[j]);
      tmp.emplace_back(j);
    }

    sort(all(tmp) ); reverse(all(tmp) );
    for (int j : tmp) if (j) upd(j);
  }

  LL ans = it.get(0, m);
  for (int j = 0; j <= m; ++j) ans += mxI[j] < n ? 0 : q[j];

  cout << ans << '\n';

  return 0;
}

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	325 ms	24568 KB	Output is correct
2	Correct	441 ms	25848 KB	Output is correct
3	Correct	226 ms	22520 KB	Output is correct
4	Correct	304 ms	26228 KB	Output is correct
5	Correct	5 ms	376 KB	Output is correct
6	Correct	364 ms	24568 KB	Output is correct
7	Correct	104 ms	13944 KB	Output is correct
8	Correct	122 ms	11400 KB	Output is correct
9	Correct	238 ms	22444 KB	Output is correct
10	Runtime error	196 ms	55464 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
11	Halted	0 ms	0 KB	-

Subtask #2
0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	376 KB	Output is correct
2	Correct	5 ms	376 KB	Output is correct
3	Correct	5 ms	376 KB	Output is correct
4	Correct	5 ms	376 KB	Output is correct
5	Correct	5 ms	376 KB	Output is correct
6	Correct	5 ms	376 KB	Output is correct
7	Correct	5 ms	376 KB	Output is correct
8	Correct	5 ms	376 KB	Output is correct
9	Correct	5 ms	504 KB	Output is correct
10	Runtime error	5 ms	632 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
11	Halted	0 ms	0 KB	-

Subtask #3
0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	376 KB	Output is correct
2	Correct	5 ms	376 KB	Output is correct
3	Correct	5 ms	376 KB	Output is correct
4	Correct	5 ms	376 KB	Output is correct
5	Correct	5 ms	376 KB	Output is correct
6	Correct	5 ms	376 KB	Output is correct
7	Correct	5 ms	376 KB	Output is correct
8	Correct	5 ms	376 KB	Output is correct
9	Correct	5 ms	504 KB	Output is correct
10	Runtime error	5 ms	632 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
11	Halted	0 ms	0 KB	-

Subtask #4
0 / 39.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	376 KB	Output is correct
2	Correct	5 ms	376 KB	Output is correct
3	Correct	5 ms	376 KB	Output is correct
4	Correct	5 ms	376 KB	Output is correct
5	Correct	5 ms	376 KB	Output is correct
6	Correct	5 ms	376 KB	Output is correct
7	Correct	5 ms	376 KB	Output is correct
8	Correct	5 ms	376 KB	Output is correct
9	Correct	5 ms	504 KB	Output is correct
10	Runtime error	5 ms	632 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
11	Halted	0 ms	0 KB	-

Subtask #5
0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	376 KB	Output is correct
2	Correct	5 ms	376 KB	Output is correct
3	Correct	5 ms	376 KB	Output is correct
4	Correct	5 ms	376 KB	Output is correct
5	Correct	5 ms	376 KB	Output is correct
6	Correct	5 ms	376 KB	Output is correct
7	Correct	5 ms	376 KB	Output is correct
8	Correct	5 ms	376 KB	Output is correct
9	Correct	5 ms	504 KB	Output is correct
10	Runtime error	5 ms	632 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
11	Halted	0 ms	0 KB	-

Subtask #6
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	376 KB	Output is correct
2	Correct	5 ms	376 KB	Output is correct
3	Correct	5 ms	376 KB	Output is correct
4	Correct	5 ms	376 KB	Output is correct
5	Correct	5 ms	376 KB	Output is correct
6	Correct	5 ms	376 KB	Output is correct
7	Correct	5 ms	376 KB	Output is correct
8	Correct	5 ms	376 KB	Output is correct
9	Correct	5 ms	504 KB	Output is correct
10	Runtime error	5 ms	632 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
11	Halted	0 ms	0 KB	-

Subtask #7
0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	325 ms	24568 KB	Output is correct
2	Correct	441 ms	25848 KB	Output is correct
3	Correct	226 ms	22520 KB	Output is correct
4	Correct	304 ms	26228 KB	Output is correct
5	Correct	5 ms	376 KB	Output is correct
6	Correct	364 ms	24568 KB	Output is correct
7	Correct	104 ms	13944 KB	Output is correct
8	Correct	122 ms	11400 KB	Output is correct
9	Correct	238 ms	22444 KB	Output is correct
10	Runtime error	196 ms	55464 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
11	Halted	0 ms	0 KB	-

Subtask #8
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	325 ms	24568 KB	Output is correct
2	Correct	441 ms	25848 KB	Output is correct
3	Correct	226 ms	22520 KB	Output is correct
4	Correct	304 ms	26228 KB	Output is correct
5	Correct	5 ms	376 KB	Output is correct
6	Correct	364 ms	24568 KB	Output is correct
7	Correct	104 ms	13944 KB	Output is correct
8	Correct	122 ms	11400 KB	Output is correct
9	Correct	238 ms	22444 KB	Output is correct
10	Runtime error	196 ms	55464 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
11	Halted	0 ms	0 KB	-

Submission #200170

Compilation message