oj.uz

답안 #579289

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
579289 2022-06-18T19:38:27 Z lumibons Two Dishes (JOI19_dishes) C++17
100 / 100
 6820 ms 205000 KB 
#include <bits/stdc++.h>

typedef long long ll;

using namespace std;

const ll inf = 1LL << 60;

typedef ll sdata;

struct operation {
  ll add = 0, max = -inf;
};

sdata combine(sdata dl, sdata dr) {
  return max(dl, dr);
}

sdata calculate(operation o, sdata d) {
  return max(o.max, d + o.add);
}

operation merge(operation ot, operation ob) {
  return { ot.add + ob.add, max(ot.max, ob.max + ot.add) };
}

const int sn = 1 << 20;
sdata s[2 * sn];
operation o[sn];

void apply(int x, operation op) {
  s[x] = calculate(op, s[x]);
  if (x < sn)
    o[x] = merge(op, o[x]);
}

void push(int x) {
  apply(x << 1, o[x]);
  apply(x << 1 | 1, o[x]);
  o[x] = operation();
}

sdata query(int a, int b, int l = 0, int r = sn, int x = 1) {
  if (b <= l || r <= a)
    return -inf;
  if (a <= l && r <= b)
    return s[x];
  push(x);
  return combine(query(a, b, l, (l + r) / 2, x << 1), query(a, b, (l + r) / 2, r, x << 1 | 1));
}

void apply(int a, int b, operation op, int l = 0, int r = sn, int x = 1) {
  if (b <= l || r <= a)
    return;
  if (a <= l && r <= b)
    return apply(x, op);
  push(x);
  apply(a, b, op, l, (l + r) / 2, x << 1);
  apply(a, b, op, (l + r) / 2, r, x << 1 | 1);
  s[x] = combine(s[x << 1], s[x << 1 | 1]);
}

int n[2];
ll a[2][1000100], t[2][1000100], p[2][1000100];
vector<int> rem[1000100];

int main() {
  cin >> n[0] >> n[1];
  for (int j = 0; j < 2; j++)
    for (int i = 0; i < n[j]; i++)
      cin >> a[j][i] >> t[j][i] >> p[j][i], i > 0 ? a[j][i] += a[j][i - 1] : 0, t[j][i] -= a[j][i];
  ll p1 = 0;
  for (int i = 0; i < n[1]; i++)
    if (t[1][i] >= 0) {
      p1 += p[1][i];
      int j = upper_bound(a[0], a[0] + n[0], t[1][i]) - a[0];
      rem[j].push_back(i);
    }
  apply(0, n[1] + 1, { -inf, p1 });
  for (int i = 0; i < n[0]; i++) {
    for (int j : rem[i])
      apply(j + 1, n[1] + 1, { 0, query(0, j + 1) });
    if (t[0][i] >= 0) {
      int j = upper_bound(a[1], a[1] + n[1], t[0][i]) - a[1];
      apply(j + 1, n[1] + 1, { 0, query(0, j + 1) });
      apply(0, j + 1, { p[0][i], -inf });
    }
    for (int j : rem[i])
      apply(0, j + 1, { -p[1][j], -inf });
  }
  cout << query(0, n[1] + 1) << "\n";
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 930 ms 43984 KB Output is correct
2 Correct 929 ms 43588 KB Output is correct
3 Correct 668 ms 35936 KB Output is correct
4 Correct 810 ms 42220 KB Output is correct
5 Correct 12 ms 23892 KB Output is correct
6 Correct 913 ms 42036 KB Output is correct
7 Correct 258 ms 30808 KB Output is correct
8 Correct 419 ms 29748 KB Output is correct
9 Correct 717 ms 35620 KB Output is correct
10 Correct 800 ms 46872 KB Output is correct
11 Correct 530 ms 35492 KB Output is correct

Subtask #2
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 23892 KB Output is correct
2 Correct 12 ms 23916 KB Output is correct
3 Correct 13 ms 23892 KB Output is correct
4 Correct 13 ms 23924 KB Output is correct
5 Correct 12 ms 23892 KB Output is correct
6 Correct 12 ms 23980 KB Output is correct
7 Correct 12 ms 23892 KB Output is correct
8 Correct 12 ms 23892 KB Output is correct
9 Correct 12 ms 23884 KB Output is correct
10 Correct 12 ms 23892 KB Output is correct
11 Correct 13 ms 23892 KB Output is correct
12 Correct 14 ms 23892 KB Output is correct
13 Correct 13 ms 23868 KB Output is correct
14 Correct 12 ms 23932 KB Output is correct
15 Correct 12 ms 23892 KB Output is correct
16 Correct 12 ms 23892 KB Output is correct

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 23892 KB Output is correct
2 Correct 12 ms 23916 KB Output is correct
3 Correct 13 ms 23892 KB Output is correct
4 Correct 13 ms 23924 KB Output is correct
5 Correct 12 ms 23892 KB Output is correct
6 Correct 12 ms 23980 KB Output is correct
7 Correct 12 ms 23892 KB Output is correct
8 Correct 12 ms 23892 KB Output is correct
9 Correct 12 ms 23884 KB Output is correct
10 Correct 12 ms 23892 KB Output is correct
11 Correct 13 ms 23892 KB Output is correct
12 Correct 14 ms 23892 KB Output is correct
13 Correct 13 ms 23868 KB Output is correct
14 Correct 12 ms 23932 KB Output is correct
15 Correct 12 ms 23892 KB Output is correct
16 Correct 12 ms 23892 KB Output is correct
17 Correct 19 ms 24148 KB Output is correct
18 Correct 20 ms 24196 KB Output is correct
19 Correct 22 ms 24148 KB Output is correct
20 Correct 20 ms 24148 KB Output is correct
21 Correct 21 ms 24148 KB Output is correct
22 Correct 18 ms 24148 KB Output is correct
23 Correct 18 ms 24068 KB Output is correct

Subtask #4
39.0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 23892 KB Output is correct
2 Correct 12 ms 23916 KB Output is correct
3 Correct 13 ms 23892 KB Output is correct
4 Correct 13 ms 23924 KB Output is correct
5 Correct 12 ms 23892 KB Output is correct
6 Correct 12 ms 23980 KB Output is correct
7 Correct 12 ms 23892 KB Output is correct
8 Correct 12 ms 23892 KB Output is correct
9 Correct 12 ms 23884 KB Output is correct
10 Correct 12 ms 23892 KB Output is correct
11 Correct 13 ms 23892 KB Output is correct
12 Correct 14 ms 23892 KB Output is correct
13 Correct 13 ms 23868 KB Output is correct
14 Correct 12 ms 23932 KB Output is correct
15 Correct 12 ms 23892 KB Output is correct
16 Correct 12 ms 23892 KB Output is correct
17 Correct 19 ms 24148 KB Output is correct
18 Correct 20 ms 24196 KB Output is correct
19 Correct 22 ms 24148 KB Output is correct
20 Correct 20 ms 24148 KB Output is correct
21 Correct 21 ms 24148 KB Output is correct
22 Correct 18 ms 24148 KB Output is correct
23 Correct 18 ms 24068 KB Output is correct
24 Correct 650 ms 34896 KB Output is correct
25 Correct 681 ms 43684 KB Output is correct
26 Correct 667 ms 43244 KB Output is correct
27 Correct 740 ms 49100 KB Output is correct
28 Correct 718 ms 44676 KB Output is correct
29 Correct 614 ms 37452 KB Output is correct
30 Correct 1065 ms 46836 KB Output is correct
31 Correct 333 ms 40968 KB Output is correct
32 Correct 370 ms 33996 KB Output is correct
33 Correct 721 ms 45192 KB Output is correct
34 Correct 967 ms 45140 KB Output is correct
35 Correct 886 ms 47792 KB Output is correct
36 Correct 855 ms 47748 KB Output is correct

Subtask #5
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 23892 KB Output is correct
2 Correct 12 ms 23916 KB Output is correct
3 Correct 13 ms 23892 KB Output is correct
4 Correct 13 ms 23924 KB Output is correct
5 Correct 12 ms 23892 KB Output is correct
6 Correct 12 ms 23980 KB Output is correct
7 Correct 12 ms 23892 KB Output is correct
8 Correct 12 ms 23892 KB Output is correct
9 Correct 12 ms 23884 KB Output is correct
10 Correct 12 ms 23892 KB Output is correct
11 Correct 13 ms 23892 KB Output is correct
12 Correct 14 ms 23892 KB Output is correct
13 Correct 13 ms 23868 KB Output is correct
14 Correct 12 ms 23932 KB Output is correct
15 Correct 12 ms 23892 KB Output is correct
16 Correct 12 ms 23892 KB Output is correct
17 Correct 19 ms 24148 KB Output is correct
18 Correct 20 ms 24196 KB Output is correct
19 Correct 22 ms 24148 KB Output is correct
20 Correct 20 ms 24148 KB Output is correct
21 Correct 21 ms 24148 KB Output is correct
22 Correct 18 ms 24148 KB Output is correct
23 Correct 18 ms 24068 KB Output is correct
24 Correct 650 ms 34896 KB Output is correct
25 Correct 681 ms 43684 KB Output is correct
26 Correct 667 ms 43244 KB Output is correct
27 Correct 740 ms 49100 KB Output is correct
28 Correct 718 ms 44676 KB Output is correct
29 Correct 614 ms 37452 KB Output is correct
30 Correct 1065 ms 46836 KB Output is correct
31 Correct 333 ms 40968 KB Output is correct
32 Correct 370 ms 33996 KB Output is correct
33 Correct 721 ms 45192 KB Output is correct
34 Correct 967 ms 45140 KB Output is correct
35 Correct 886 ms 47792 KB Output is correct
36 Correct 855 ms 47748 KB Output is correct
37 Correct 736 ms 43032 KB Output is correct
38 Correct 831 ms 48876 KB Output is correct
39 Correct 889 ms 48984 KB Output is correct
40 Correct 899 ms 48844 KB Output is correct
41 Correct 13 ms 23892 KB Output is correct
42 Correct 1142 ms 46580 KB Output is correct
43 Correct 803 ms 44820 KB Output is correct
44 Correct 1020 ms 44804 KB Output is correct
45 Correct 1006 ms 47976 KB Output is correct

Subtask #6
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 23892 KB Output is correct
2 Correct 12 ms 23916 KB Output is correct
3 Correct 13 ms 23892 KB Output is correct
4 Correct 13 ms 23924 KB Output is correct
5 Correct 12 ms 23892 KB Output is correct
6 Correct 12 ms 23980 KB Output is correct
7 Correct 12 ms 23892 KB Output is correct
8 Correct 12 ms 23892 KB Output is correct
9 Correct 12 ms 23884 KB Output is correct
10 Correct 12 ms 23892 KB Output is correct
11 Correct 13 ms 23892 KB Output is correct
12 Correct 14 ms 23892 KB Output is correct
13 Correct 13 ms 23868 KB Output is correct
14 Correct 12 ms 23932 KB Output is correct
15 Correct 12 ms 23892 KB Output is correct
16 Correct 12 ms 23892 KB Output is correct
17 Correct 19 ms 24148 KB Output is correct
18 Correct 20 ms 24196 KB Output is correct
19 Correct 22 ms 24148 KB Output is correct
20 Correct 20 ms 24148 KB Output is correct
21 Correct 21 ms 24148 KB Output is correct
22 Correct 18 ms 24148 KB Output is correct
23 Correct 18 ms 24068 KB Output is correct
24 Correct 650 ms 34896 KB Output is correct
25 Correct 681 ms 43684 KB Output is correct
26 Correct 667 ms 43244 KB Output is correct
27 Correct 740 ms 49100 KB Output is correct
28 Correct 718 ms 44676 KB Output is correct
29 Correct 614 ms 37452 KB Output is correct
30 Correct 1065 ms 46836 KB Output is correct
31 Correct 333 ms 40968 KB Output is correct
32 Correct 370 ms 33996 KB Output is correct
33 Correct 721 ms 45192 KB Output is correct
34 Correct 967 ms 45140 KB Output is correct
35 Correct 886 ms 47792 KB Output is correct
36 Correct 855 ms 47748 KB Output is correct
37 Correct 736 ms 43032 KB Output is correct
38 Correct 831 ms 48876 KB Output is correct
39 Correct 889 ms 48984 KB Output is correct
40 Correct 899 ms 48844 KB Output is correct
41 Correct 13 ms 23892 KB Output is correct
42 Correct 1142 ms 46580 KB Output is correct
43 Correct 803 ms 44820 KB Output is correct
44 Correct 1020 ms 44804 KB Output is correct
45 Correct 1006 ms 47976 KB Output is correct
46 Correct 3690 ms 106624 KB Output is correct
47 Correct 4187 ms 135940 KB Output is correct
48 Correct 4597 ms 135292 KB Output is correct
49 Correct 4461 ms 135260 KB Output is correct
50 Correct 6463 ms 124076 KB Output is correct
51 Correct 4231 ms 113720 KB Output is correct
52 Correct 5442 ms 109332 KB Output is correct
53 Correct 6297 ms 121772 KB Output is correct

Subtask #7
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 930 ms 43984 KB Output is correct
2 Correct 929 ms 43588 KB Output is correct
3 Correct 668 ms 35936 KB Output is correct
4 Correct 810 ms 42220 KB Output is correct
5 Correct 12 ms 23892 KB Output is correct
6 Correct 913 ms 42036 KB Output is correct
7 Correct 258 ms 30808 KB Output is correct
8 Correct 419 ms 29748 KB Output is correct
9 Correct 717 ms 35620 KB Output is correct
10 Correct 800 ms 46872 KB Output is correct
11 Correct 530 ms 35492 KB Output is correct
12 Correct 12 ms 23892 KB Output is correct
13 Correct 12 ms 23916 KB Output is correct
14 Correct 13 ms 23892 KB Output is correct
15 Correct 13 ms 23924 KB Output is correct
16 Correct 12 ms 23892 KB Output is correct
17 Correct 12 ms 23980 KB Output is correct
18 Correct 12 ms 23892 KB Output is correct
19 Correct 12 ms 23892 KB Output is correct
20 Correct 12 ms 23884 KB Output is correct
21 Correct 12 ms 23892 KB Output is correct
22 Correct 13 ms 23892 KB Output is correct
23 Correct 14 ms 23892 KB Output is correct
24 Correct 13 ms 23868 KB Output is correct
25 Correct 12 ms 23932 KB Output is correct
26 Correct 12 ms 23892 KB Output is correct
27 Correct 12 ms 23892 KB Output is correct
28 Correct 19 ms 24148 KB Output is correct
29 Correct 20 ms 24196 KB Output is correct
30 Correct 22 ms 24148 KB Output is correct
31 Correct 20 ms 24148 KB Output is correct
32 Correct 21 ms 24148 KB Output is correct
33 Correct 18 ms 24148 KB Output is correct
34 Correct 18 ms 24068 KB Output is correct
35 Correct 650 ms 34896 KB Output is correct
36 Correct 681 ms 43684 KB Output is correct
37 Correct 667 ms 43244 KB Output is correct
38 Correct 740 ms 49100 KB Output is correct
39 Correct 718 ms 44676 KB Output is correct
40 Correct 614 ms 37452 KB Output is correct
41 Correct 1065 ms 46836 KB Output is correct
42 Correct 333 ms 40968 KB Output is correct
43 Correct 370 ms 33996 KB Output is correct
44 Correct 721 ms 45192 KB Output is correct
45 Correct 967 ms 45140 KB Output is correct
46 Correct 886 ms 47792 KB Output is correct
47 Correct 855 ms 47748 KB Output is correct
48 Correct 736 ms 43032 KB Output is correct
49 Correct 831 ms 48876 KB Output is correct
50 Correct 889 ms 48984 KB Output is correct
51 Correct 899 ms 48844 KB Output is correct
52 Correct 13 ms 23892 KB Output is correct
53 Correct 1142 ms 46580 KB Output is correct
54 Correct 803 ms 44820 KB Output is correct
55 Correct 1020 ms 44804 KB Output is correct
56 Correct 1006 ms 47976 KB Output is correct
57 Correct 812 ms 40692 KB Output is correct
58 Correct 850 ms 60148 KB Output is correct
59 Correct 947 ms 57904 KB Output is correct
60 Correct 924 ms 57944 KB Output is correct
61 Correct 1148 ms 54268 KB Output is correct
62 Correct 13 ms 23892 KB Output is correct
63 Correct 1174 ms 57396 KB Output is correct
64 Correct 817 ms 54996 KB Output is correct
65 Correct 1022 ms 55624 KB Output is correct
66 Correct 950 ms 50992 KB Output is correct

Subtask #8
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 930 ms 43984 KB Output is correct
2 Correct 929 ms 43588 KB Output is correct
3 Correct 668 ms 35936 KB Output is correct
4 Correct 810 ms 42220 KB Output is correct
5 Correct 12 ms 23892 KB Output is correct
6 Correct 913 ms 42036 KB Output is correct
7 Correct 258 ms 30808 KB Output is correct
8 Correct 419 ms 29748 KB Output is correct
9 Correct 717 ms 35620 KB Output is correct
10 Correct 800 ms 46872 KB Output is correct
11 Correct 530 ms 35492 KB Output is correct
12 Correct 12 ms 23892 KB Output is correct
13 Correct 12 ms 23916 KB Output is correct
14 Correct 13 ms 23892 KB Output is correct
15 Correct 13 ms 23924 KB Output is correct
16 Correct 12 ms 23892 KB Output is correct
17 Correct 12 ms 23980 KB Output is correct
18 Correct 12 ms 23892 KB Output is correct
19 Correct 12 ms 23892 KB Output is correct
20 Correct 12 ms 23884 KB Output is correct
21 Correct 12 ms 23892 KB Output is correct
22 Correct 13 ms 23892 KB Output is correct
23 Correct 14 ms 23892 KB Output is correct
24 Correct 13 ms 23868 KB Output is correct
25 Correct 12 ms 23932 KB Output is correct
26 Correct 12 ms 23892 KB Output is correct
27 Correct 12 ms 23892 KB Output is correct
28 Correct 19 ms 24148 KB Output is correct
29 Correct 20 ms 24196 KB Output is correct
30 Correct 22 ms 24148 KB Output is correct
31 Correct 20 ms 24148 KB Output is correct
32 Correct 21 ms 24148 KB Output is correct
33 Correct 18 ms 24148 KB Output is correct
34 Correct 18 ms 24068 KB Output is correct
35 Correct 650 ms 34896 KB Output is correct
36 Correct 681 ms 43684 KB Output is correct
37 Correct 667 ms 43244 KB Output is correct
38 Correct 740 ms 49100 KB Output is correct
39 Correct 718 ms 44676 KB Output is correct
40 Correct 614 ms 37452 KB Output is correct
41 Correct 1065 ms 46836 KB Output is correct
42 Correct 333 ms 40968 KB Output is correct
43 Correct 370 ms 33996 KB Output is correct
44 Correct 721 ms 45192 KB Output is correct
45 Correct 967 ms 45140 KB Output is correct
46 Correct 886 ms 47792 KB Output is correct
47 Correct 855 ms 47748 KB Output is correct
48 Correct 736 ms 43032 KB Output is correct
49 Correct 831 ms 48876 KB Output is correct
50 Correct 889 ms 48984 KB Output is correct
51 Correct 899 ms 48844 KB Output is correct
52 Correct 13 ms 23892 KB Output is correct
53 Correct 1142 ms 46580 KB Output is correct
54 Correct 803 ms 44820 KB Output is correct
55 Correct 1020 ms 44804 KB Output is correct
56 Correct 1006 ms 47976 KB Output is correct
57 Correct 3690 ms 106624 KB Output is correct
58 Correct 4187 ms 135940 KB Output is correct
59 Correct 4597 ms 135292 KB Output is correct
60 Correct 4461 ms 135260 KB Output is correct
61 Correct 6463 ms 124076 KB Output is correct
62 Correct 4231 ms 113720 KB Output is correct
63 Correct 5442 ms 109332 KB Output is correct
64 Correct 6297 ms 121772 KB Output is correct
65 Correct 812 ms 40692 KB Output is correct
66 Correct 850 ms 60148 KB Output is correct
67 Correct 947 ms 57904 KB Output is correct
68 Correct 924 ms 57944 KB Output is correct
69 Correct 1148 ms 54268 KB Output is correct
70 Correct 13 ms 23892 KB Output is correct
71 Correct 1174 ms 57396 KB Output is correct
72 Correct 817 ms 54996 KB Output is correct
73 Correct 1022 ms 55624 KB Output is correct
74 Correct 950 ms 50992 KB Output is correct
75 Correct 3924 ms 176076 KB Output is correct
76 Correct 4275 ms 205000 KB Output is correct
77 Correct 4711 ms 191000 KB Output is correct
78 Correct 4634 ms 191352 KB Output is correct
79 Correct 6820 ms 190940 KB Output is correct
80 Correct 4475 ms 176808 KB Output is correct
81 Correct 5954 ms 176632 KB Output is correct
82 Correct 5856 ms 159700 KB Output is correct
83 Correct 6446 ms 178972 KB Output is correct