oj.uz

Submission #200155

# Submission time Handle Problem Language Result Execution time Memory
200155 2020-02-05T14:32:43 Z EntityIT Two Dishes (JOI19_dishes) C++14
82 / 100
 6565 ms 200280 KB 
#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 (r < Left || Right < l) return ;
    if (l <= Left && Right <= r) {
      lz[i] = true; trueVal(i, Left, Right);
      return ;
    }
    int Mid = (Left + Right) >> 1;
    upd(l, r, i << 1, Left, Mid);
    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);
    if (pos < Left || Right < pos) return ;
    if (Left == Right) {
      sum[i] += val;
      return ;
    }
    int Mid = (Left + Right) >> 1;
    add(pos, val, i << 1, Left, Mid);
    add(pos, val, i << 1 | 1, Mid + 1, Right);

    sum[i] = sum[i << 1] + sum[i << 1 | 1];
  }

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

    if (Left == Right) return Left;

    int Mid = (Left + Right) >> 1;
    int tmp = findPos(l, cur, i << 1, Left, Mid);
    if (tmp != m + 1) 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 (r < Left || Right < l) return 0;
    if (l <= Left && Right <= r) return sum[i];
    int Mid = (Left + Right) >> 1;
    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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 405 ms 23928 KB Output is correct
2 Correct 528 ms 37240 KB Output is correct
3 Correct 267 ms 33656 KB Output is correct
4 Correct 354 ms 37492 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 446 ms 35580 KB Output is correct
7 Correct 106 ms 18296 KB Output is correct
8 Correct 123 ms 15964 KB Output is correct
9 Correct 259 ms 34552 KB Output is correct
10 Correct 467 ms 33784 KB Output is correct
11 Correct 201 ms 28040 KB Output is correct

Subtask #2
3.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 380 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 376 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 5 ms 376 KB Output is correct
12 Correct 5 ms 376 KB Output is correct
13 Correct 5 ms 376 KB Output is correct
14 Correct 5 ms 376 KB Output is correct
15 Correct 5 ms 376 KB Output is correct
16 Correct 5 ms 380 KB Output is correct

Subtask #3
7.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 380 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 376 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 5 ms 376 KB Output is correct
12 Correct 5 ms 376 KB Output is correct
13 Correct 5 ms 376 KB Output is correct
14 Correct 5 ms 376 KB Output is correct
15 Correct 5 ms 376 KB Output is correct
16 Correct 5 ms 380 KB Output is correct
17 Correct 8 ms 504 KB Output is correct
18 Correct 7 ms 632 KB Output is correct
19 Correct 11 ms 632 KB Output is correct
20 Correct 8 ms 632 KB Output is correct
21 Correct 10 ms 504 KB Output is correct
22 Correct 10 ms 504 KB Output is correct
23 Correct 10 ms 504 KB Output is correct

Subtask #4
39.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 380 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 376 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 5 ms 376 KB Output is correct
12 Correct 5 ms 376 KB Output is correct
13 Correct 5 ms 376 KB Output is correct
14 Correct 5 ms 376 KB Output is correct
15 Correct 5 ms 376 KB Output is correct
16 Correct 5 ms 380 KB Output is correct
17 Correct 8 ms 504 KB Output is correct
18 Correct 7 ms 632 KB Output is correct
19 Correct 11 ms 632 KB Output is correct
20 Correct 8 ms 632 KB Output is correct
21 Correct 10 ms 504 KB Output is correct
22 Correct 10 ms 504 KB Output is correct
23 Correct 10 ms 504 KB Output is correct
24 Correct 419 ms 20508 KB Output is correct
25 Correct 278 ms 33008 KB Output is correct
26 Correct 423 ms 31220 KB Output is correct
27 Correct 305 ms 36984 KB Output is correct
28 Correct 423 ms 32248 KB Output is correct
29 Correct 237 ms 31480 KB Output is correct
30 Correct 918 ms 34736 KB Output is correct
31 Correct 130 ms 17780 KB Output is correct
32 Correct 114 ms 14200 KB Output is correct
33 Correct 576 ms 33136 KB Output is correct
34 Correct 707 ms 32864 KB Output is correct
35 Correct 885 ms 28280 KB Output is correct
36 Correct 864 ms 28408 KB Output is correct

Subtask #5
11.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 380 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 376 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 5 ms 376 KB Output is correct
12 Correct 5 ms 376 KB Output is correct
13 Correct 5 ms 376 KB Output is correct
14 Correct 5 ms 376 KB Output is correct
15 Correct 5 ms 376 KB Output is correct
16 Correct 5 ms 380 KB Output is correct
17 Correct 8 ms 504 KB Output is correct
18 Correct 7 ms 632 KB Output is correct
19 Correct 11 ms 632 KB Output is correct
20 Correct 8 ms 632 KB Output is correct
21 Correct 10 ms 504 KB Output is correct
22 Correct 10 ms 504 KB Output is correct
23 Correct 10 ms 504 KB Output is correct
24 Correct 419 ms 20508 KB Output is correct
25 Correct 278 ms 33008 KB Output is correct
26 Correct 423 ms 31220 KB Output is correct
27 Correct 305 ms 36984 KB Output is correct
28 Correct 423 ms 32248 KB Output is correct
29 Correct 237 ms 31480 KB Output is correct
30 Correct 918 ms 34736 KB Output is correct
31 Correct 130 ms 17780 KB Output is correct
32 Correct 114 ms 14200 KB Output is correct
33 Correct 576 ms 33136 KB Output is correct
34 Correct 707 ms 32864 KB Output is correct
35 Correct 885 ms 28280 KB Output is correct
36 Correct 864 ms 28408 KB Output is correct
37 Correct 457 ms 34220 KB Output is correct
38 Correct 346 ms 40216 KB Output is correct
39 Correct 407 ms 37428 KB Output is correct
40 Correct 660 ms 37368 KB Output is correct
41 Correct 5 ms 376 KB Output is correct
42 Correct 984 ms 37820 KB Output is correct
43 Correct 593 ms 36080 KB Output is correct
44 Correct 744 ms 35704 KB Output is correct
45 Correct 919 ms 31480 KB Output is correct

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 380 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 376 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 5 ms 376 KB Output is correct
12 Correct 5 ms 376 KB Output is correct
13 Correct 5 ms 376 KB Output is correct
14 Correct 5 ms 376 KB Output is correct
15 Correct 5 ms 376 KB Output is correct
16 Correct 5 ms 380 KB Output is correct
17 Correct 8 ms 504 KB Output is correct
18 Correct 7 ms 632 KB Output is correct
19 Correct 11 ms 632 KB Output is correct
20 Correct 8 ms 632 KB Output is correct
21 Correct 10 ms 504 KB Output is correct
22 Correct 10 ms 504 KB Output is correct
23 Correct 10 ms 504 KB Output is correct
24 Correct 419 ms 20508 KB Output is correct
25 Correct 278 ms 33008 KB Output is correct
26 Correct 423 ms 31220 KB Output is correct
27 Correct 305 ms 36984 KB Output is correct
28 Correct 423 ms 32248 KB Output is correct
29 Correct 237 ms 31480 KB Output is correct
30 Correct 918 ms 34736 KB Output is correct
31 Correct 130 ms 17780 KB Output is correct
32 Correct 114 ms 14200 KB Output is correct
33 Correct 576 ms 33136 KB Output is correct
34 Correct 707 ms 32864 KB Output is correct
35 Correct 885 ms 28280 KB Output is correct
36 Correct 864 ms 28408 KB Output is correct
37 Correct 457 ms 34220 KB Output is correct
38 Correct 346 ms 40216 KB Output is correct
39 Correct 407 ms 37428 KB Output is correct
40 Correct 660 ms 37368 KB Output is correct
41 Correct 5 ms 376 KB Output is correct
42 Correct 984 ms 37820 KB Output is correct
43 Correct 593 ms 36080 KB Output is correct
44 Correct 744 ms 35704 KB Output is correct
45 Correct 919 ms 31480 KB Output is correct
46 Correct 2444 ms 170796 KB Output is correct
47 Correct 1805 ms 200280 KB Output is correct
48 Correct 2186 ms 186600 KB Output is correct
49 Correct 3730 ms 186492 KB Output is correct
50 Correct 6565 ms 188428 KB Output is correct
51 Correct 3902 ms 176396 KB Output is correct
52 Correct 4539 ms 170628 KB Output is correct
53 Execution timed out 1163 ms 120728 KB Time limit exceeded (wall clock)

Subtask #7
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 405 ms 23928 KB Output is correct
2 Correct 528 ms 37240 KB Output is correct
3 Correct 267 ms 33656 KB Output is correct
4 Correct 354 ms 37492 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 446 ms 35580 KB Output is correct
7 Correct 106 ms 18296 KB Output is correct
8 Correct 123 ms 15964 KB Output is correct
9 Correct 259 ms 34552 KB Output is correct
10 Correct 467 ms 33784 KB Output is correct
11 Correct 201 ms 28040 KB Output is correct
12 Correct 5 ms 376 KB Output is correct
13 Correct 5 ms 376 KB Output is correct
14 Correct 5 ms 376 KB Output is correct
15 Correct 5 ms 380 KB Output is correct
16 Correct 5 ms 376 KB Output is correct
17 Correct 5 ms 376 KB Output is correct
18 Correct 5 ms 376 KB Output is correct
19 Correct 5 ms 376 KB Output is correct
20 Correct 5 ms 376 KB Output is correct
21 Correct 5 ms 376 KB Output is correct
22 Correct 5 ms 376 KB Output is correct
23 Correct 5 ms 376 KB Output is correct
24 Correct 5 ms 376 KB Output is correct
25 Correct 5 ms 376 KB Output is correct
26 Correct 5 ms 376 KB Output is correct
27 Correct 5 ms 380 KB Output is correct
28 Correct 8 ms 504 KB Output is correct
29 Correct 7 ms 632 KB Output is correct
30 Correct 11 ms 632 KB Output is correct
31 Correct 8 ms 632 KB Output is correct
32 Correct 10 ms 504 KB Output is correct
33 Correct 10 ms 504 KB Output is correct
34 Correct 10 ms 504 KB Output is correct
35 Correct 419 ms 20508 KB Output is correct
36 Correct 278 ms 33008 KB Output is correct
37 Correct 423 ms 31220 KB Output is correct
38 Correct 305 ms 36984 KB Output is correct
39 Correct 423 ms 32248 KB Output is correct
40 Correct 237 ms 31480 KB Output is correct
41 Correct 918 ms 34736 KB Output is correct
42 Correct 130 ms 17780 KB Output is correct
43 Correct 114 ms 14200 KB Output is correct
44 Correct 576 ms 33136 KB Output is correct
45 Correct 707 ms 32864 KB Output is correct
46 Correct 885 ms 28280 KB Output is correct
47 Correct 864 ms 28408 KB Output is correct
48 Correct 457 ms 34220 KB Output is correct
49 Correct 346 ms 40216 KB Output is correct
50 Correct 407 ms 37428 KB Output is correct
51 Correct 660 ms 37368 KB Output is correct
52 Correct 5 ms 376 KB Output is correct
53 Correct 984 ms 37820 KB Output is correct
54 Correct 593 ms 36080 KB Output is correct
55 Correct 744 ms 35704 KB Output is correct
56 Correct 919 ms 31480 KB Output is correct
57 Correct 374 ms 34780 KB Output is correct
58 Correct 479 ms 40440 KB Output is correct
59 Correct 708 ms 38520 KB Output is correct
60 Correct 429 ms 38264 KB Output is correct
61 Correct 645 ms 34808 KB Output is correct
62 Correct 5 ms 376 KB Output is correct
63 Correct 992 ms 37928 KB Output is correct
64 Correct 600 ms 36080 KB Output is correct
65 Correct 801 ms 35728 KB Output is correct
66 Correct 915 ms 31608 KB Output is correct

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 405 ms 23928 KB Output is correct
2 Correct 528 ms 37240 KB Output is correct
3 Correct 267 ms 33656 KB Output is correct
4 Correct 354 ms 37492 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 446 ms 35580 KB Output is correct
7 Correct 106 ms 18296 KB Output is correct
8 Correct 123 ms 15964 KB Output is correct
9 Correct 259 ms 34552 KB Output is correct
10 Correct 467 ms 33784 KB Output is correct
11 Correct 201 ms 28040 KB Output is correct
12 Correct 5 ms 376 KB Output is correct
13 Correct 5 ms 376 KB Output is correct
14 Correct 5 ms 376 KB Output is correct
15 Correct 5 ms 380 KB Output is correct
16 Correct 5 ms 376 KB Output is correct
17 Correct 5 ms 376 KB Output is correct
18 Correct 5 ms 376 KB Output is correct
19 Correct 5 ms 376 KB Output is correct
20 Correct 5 ms 376 KB Output is correct
21 Correct 5 ms 376 KB Output is correct
22 Correct 5 ms 376 KB Output is correct
23 Correct 5 ms 376 KB Output is correct
24 Correct 5 ms 376 KB Output is correct
25 Correct 5 ms 376 KB Output is correct
26 Correct 5 ms 376 KB Output is correct
27 Correct 5 ms 380 KB Output is correct
28 Correct 8 ms 504 KB Output is correct
29 Correct 7 ms 632 KB Output is correct
30 Correct 11 ms 632 KB Output is correct
31 Correct 8 ms 632 KB Output is correct
32 Correct 10 ms 504 KB Output is correct
33 Correct 10 ms 504 KB Output is correct
34 Correct 10 ms 504 KB Output is correct
35 Correct 419 ms 20508 KB Output is correct
36 Correct 278 ms 33008 KB Output is correct
37 Correct 423 ms 31220 KB Output is correct
38 Correct 305 ms 36984 KB Output is correct
39 Correct 423 ms 32248 KB Output is correct
40 Correct 237 ms 31480 KB Output is correct
41 Correct 918 ms 34736 KB Output is correct
42 Correct 130 ms 17780 KB Output is correct
43 Correct 114 ms 14200 KB Output is correct
44 Correct 576 ms 33136 KB Output is correct
45 Correct 707 ms 32864 KB Output is correct
46 Correct 885 ms 28280 KB Output is correct
47 Correct 864 ms 28408 KB Output is correct
48 Correct 457 ms 34220 KB Output is correct
49 Correct 346 ms 40216 KB Output is correct
50 Correct 407 ms 37428 KB Output is correct
51 Correct 660 ms 37368 KB Output is correct
52 Correct 5 ms 376 KB Output is correct
53 Correct 984 ms 37820 KB Output is correct
54 Correct 593 ms 36080 KB Output is correct
55 Correct 744 ms 35704 KB Output is correct
56 Correct 919 ms 31480 KB Output is correct
57 Correct 2444 ms 170796 KB Output is correct
58 Correct 1805 ms 200280 KB Output is correct
59 Correct 2186 ms 186600 KB Output is correct
60 Correct 3730 ms 186492 KB Output is correct
61 Correct 6565 ms 188428 KB Output is correct
62 Correct 3902 ms 176396 KB Output is correct
63 Correct 4539 ms 170628 KB Output is correct
64 Execution timed out 1163 ms 120728 KB Time limit exceeded (wall clock)