oj.uz

Submission #365860

# Submission time Handle Problem Language Result Execution time Memory
365860 2021-02-12T13:03:49 Z Kazalika Two Dishes (JOI19_dishes) C++14
100 / 100
 7161 ms 215868 KB 
#include <bits/stdc++.h>

#pragma GCC optimize("Ofast, no-stack-protector, unroll-loops, fast-math")
//#pragma GCC target("sse, sse2, sse3, ssse3, sse4.1, sse4.2, popcnt, abm, avx, mmx, tune=native")

using namespace std;
typedef long long ll;

const int N = 1e6 + 5;
const ll inf = 1e18;

ll sgt[N << 2], add[N << 2];

void push(int t, int l, int r) {
  if (add[t]) {
    sgt[t] += add[t];
    if (l < r) {
      add[t << 1] += add[t];
      add[t << 1 | 1] += add[t];
    }
    add[t] = 0;
  }
}

void upd(int t, int l, int r, int x, ll val) {
  push(t, l, r);
  if (x < l || x > r)
    return;
  if (l == r) {
    sgt[t] = max(sgt[t], val);
    return;
  }
  int md = (l + r) >> 1;
  upd(t << 1, l, md, x, val);
  upd(t << 1 | 1, md + 1, r, x, val);
  sgt[t] = max(sgt[t << 1], sgt[t << 1 | 1]);
}

void add_range(int t, int l, int r, int x, int y, ll val) {
  push(t, l, r);
  if (l > y || r < x || l > r)
    return;
  if (l >= x && r <= y) {
    add[t] = val;
    push(t, l, r);
    return;
  }
  int md = (l + r) >> 1;
  add_range(t << 1, l, md, x, y, val);
  add_range(t << 1 | 1, md + 1, r, x, y, val);
  sgt[t] = max(sgt[t << 1], sgt[t << 1 | 1]);
}

ll get_max(int t, int l, int r, int x, int y) {
  push(t, l, r);
  if (l > y || r < x || l > r)
    return -inf;
  if (l >= x && r <= y)
    return sgt[t];
  int md = (l + r) >> 1;
  return max(get_max(t << 1, l, md, x, y), get_max(t << 1 | 1, md + 1, r, x, y));
}

int a[N], b[N];
ll s[N], t[N];
int p[N], q[N];
ll sa[N], sb[N];
map<pair<int, int>, ll> qq;



int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int n, m;
  cin >> n >> m;
  for (int i = 0; i < n; ++i) {
    cin >> a[i] >> s[i] >> p[i];
    sa[i] = (i ? sa[i - 1] : 0) + a[i];
  }
  for (int i = 0; i < m; ++i) {
    cin >> b[i] >> t[i] >> q[i];
    sb[i] = (i ? sb[i - 1] : 0) + b[i];
  }
  ll sum = 0;
  for (int i = 0; i < n; ++i) {
    if (sa[i] > s[i])
      continue;
    if (sa[i] + sb[m - 1] <= s[i])
      sum += p[i];
    else {
      int nw = upper_bound(sb, sb + m, s[i] - sa[i]) - sb;
      qq[{(i + 1) - 1, -nw - 1}] += p[i];
    }
  }
  for (int i = 0; i < m; ++i) {
    if (sb[i] > t[i])
      continue;
    if (sb[i] + sa[n - 1] <= t[i])
      sum += q[i];
    else {
      int nw = upper_bound(sa, sa + n, t[i] - sb[i]) - sa;
      sum += q[i];
      qq[{nw, -(i + 1)}] -= q[i];
    }
  }
  for (auto &pt : qq) {
    int y = -pt.first.second;
    ll val = pt.second;
    ll nw = get_max(1, 0, N - 1, 0, y - 1);
    upd(1, 0, N - 1, y, nw);
    add_range(1, 0, N - 1, 0, y - 1, val);
  }
  push(0, 0, N - 1);
  ll ans = sgt[1] + sum;
  cout << ans;
}

Compilation message

dishes.cpp:3:74: warning: bad option '-f no-stack-protector' to pragma 'optimize' [-Wpragmas]
    3 | #pragma GCC optimize("Ofast, no-stack-protector, unroll-loops, fast-math")
      |                                                                          ^
dishes.cpp:3:74: warning: bad option '-f unroll-loops' to pragma 'optimize' [-Wpragmas]
dishes.cpp:3:74: warning: bad option '-f fast-math' to pragma 'optimize' [-Wpragmas]
dishes.cpp:14:30: warning: bad option '-f no-stack-protector' to attribute 'optimize' [-Wattributes]
   14 | void push(int t, int l, int r) {
      |                              ^
dishes.cpp:14:30: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
dishes.cpp:14:30: warning: bad option '-f fast-math' to attribute 'optimize' [-Wattributes]
dishes.cpp:25:44: warning: bad option '-f no-stack-protector' to attribute 'optimize' [-Wattributes]
   25 | void upd(int t, int l, int r, int x, ll val) {
      |                                            ^
dishes.cpp:25:44: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
dishes.cpp:25:44: warning: bad option '-f fast-math' to attribute 'optimize' [-Wattributes]
dishes.cpp:39:57: warning: bad option '-f no-stack-protector' to attribute 'optimize' [-Wattributes]
   39 | void add_range(int t, int l, int r, int x, int y, ll val) {
      |                                                         ^
dishes.cpp:39:57: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
dishes.cpp:39:57: warning: bad option '-f fast-math' to attribute 'optimize' [-Wattributes]
dishes.cpp:54:45: warning: bad option '-f no-stack-protector' to attribute 'optimize' [-Wattributes]
   54 | ll get_max(int t, int l, int r, int x, int y) {
      |                                             ^
dishes.cpp:54:45: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
dishes.cpp:54:45: warning: bad option '-f fast-math' to attribute 'optimize' [-Wattributes]
dishes.cpp:72:10: warning: bad option '-f no-stack-protector' to attribute 'optimize' [-Wattributes]
   72 | int main() {
      |          ^
dishes.cpp:72:10: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
dishes.cpp:72:10: warning: bad option '-f fast-math' to attribute 'optimize' [-Wattributes]

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 438 ms 30924 KB Output is correct
2 Correct 428 ms 30828 KB Output is correct
3 Correct 155 ms 10604 KB Output is correct
4 Correct 315 ms 22636 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 376 ms 26860 KB Output is correct
7 Correct 79 ms 6124 KB Output is correct
8 Correct 80 ms 5996 KB Output is correct
9 Correct 160 ms 10732 KB Output is correct
10 Correct 366 ms 29920 KB Output is correct
11 Correct 112 ms 10732 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 448 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 492 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 1 ms 492 KB Output is correct
12 Correct 1 ms 492 KB Output is correct
13 Correct 1 ms 492 KB Output is correct
14 Correct 1 ms 492 KB Output is correct
15 Correct 1 ms 492 KB Output is correct
16 Correct 1 ms 492 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 448 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 492 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 1 ms 492 KB Output is correct
12 Correct 1 ms 492 KB Output is correct
13 Correct 1 ms 492 KB Output is correct
14 Correct 1 ms 492 KB Output is correct
15 Correct 1 ms 492 KB Output is correct
16 Correct 1 ms 492 KB Output is correct
17 Correct 4 ms 748 KB Output is correct
18 Correct 4 ms 876 KB Output is correct
19 Correct 6 ms 1004 KB Output is correct
20 Correct 4 ms 876 KB Output is correct
21 Correct 6 ms 1004 KB Output is correct
22 Correct 6 ms 1004 KB Output is correct
23 Correct 6 ms 1004 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 448 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 492 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 1 ms 492 KB Output is correct
12 Correct 1 ms 492 KB Output is correct
13 Correct 1 ms 492 KB Output is correct
14 Correct 1 ms 492 KB Output is correct
15 Correct 1 ms 492 KB Output is correct
16 Correct 1 ms 492 KB Output is correct
17 Correct 4 ms 748 KB Output is correct
18 Correct 4 ms 876 KB Output is correct
19 Correct 6 ms 1004 KB Output is correct
20 Correct 4 ms 876 KB Output is correct
21 Correct 6 ms 1004 KB Output is correct
22 Correct 6 ms 1004 KB Output is correct
23 Correct 6 ms 1004 KB Output is correct
24 Correct 349 ms 33132 KB Output is correct
25 Correct 361 ms 39708 KB Output is correct
26 Correct 363 ms 39788 KB Output is correct
27 Correct 364 ms 39660 KB Output is correct
28 Correct 346 ms 33624 KB Output is correct
29 Correct 145 ms 21148 KB Output is correct
30 Correct 1012 ms 51344 KB Output is correct
31 Correct 180 ms 23404 KB Output is correct
32 Correct 159 ms 16876 KB Output is correct
33 Correct 574 ms 38988 KB Output is correct
34 Correct 775 ms 46060 KB Output is correct
35 Correct 998 ms 45420 KB Output is correct
36 Correct 942 ms 44524 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 448 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 492 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 1 ms 492 KB Output is correct
12 Correct 1 ms 492 KB Output is correct
13 Correct 1 ms 492 KB Output is correct
14 Correct 1 ms 492 KB Output is correct
15 Correct 1 ms 492 KB Output is correct
16 Correct 1 ms 492 KB Output is correct
17 Correct 4 ms 748 KB Output is correct
18 Correct 4 ms 876 KB Output is correct
19 Correct 6 ms 1004 KB Output is correct
20 Correct 4 ms 876 KB Output is correct
21 Correct 6 ms 1004 KB Output is correct
22 Correct 6 ms 1004 KB Output is correct
23 Correct 6 ms 1004 KB Output is correct
24 Correct 349 ms 33132 KB Output is correct
25 Correct 361 ms 39708 KB Output is correct
26 Correct 363 ms 39788 KB Output is correct
27 Correct 364 ms 39660 KB Output is correct
28 Correct 346 ms 33624 KB Output is correct
29 Correct 145 ms 21148 KB Output is correct
30 Correct 1012 ms 51344 KB Output is correct
31 Correct 180 ms 23404 KB Output is correct
32 Correct 159 ms 16876 KB Output is correct
33 Correct 574 ms 38988 KB Output is correct
34 Correct 775 ms 46060 KB Output is correct
35 Correct 998 ms 45420 KB Output is correct
36 Correct 942 ms 44524 KB Output is correct
37 Correct 384 ms 42624 KB Output is correct
38 Correct 386 ms 42732 KB Output is correct
39 Correct 407 ms 40084 KB Output is correct
40 Correct 409 ms 40108 KB Output is correct
41 Correct 1 ms 492 KB Output is correct
42 Correct 1050 ms 54448 KB Output is correct
43 Correct 558 ms 41836 KB Output is correct
44 Correct 804 ms 48640 KB Output is correct
45 Correct 1044 ms 48444 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 448 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 492 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 1 ms 492 KB Output is correct
12 Correct 1 ms 492 KB Output is correct
13 Correct 1 ms 492 KB Output is correct
14 Correct 1 ms 492 KB Output is correct
15 Correct 1 ms 492 KB Output is correct
16 Correct 1 ms 492 KB Output is correct
17 Correct 4 ms 748 KB Output is correct
18 Correct 4 ms 876 KB Output is correct
19 Correct 6 ms 1004 KB Output is correct
20 Correct 4 ms 876 KB Output is correct
21 Correct 6 ms 1004 KB Output is correct
22 Correct 6 ms 1004 KB Output is correct
23 Correct 6 ms 1004 KB Output is correct
24 Correct 349 ms 33132 KB Output is correct
25 Correct 361 ms 39708 KB Output is correct
26 Correct 363 ms 39788 KB Output is correct
27 Correct 364 ms 39660 KB Output is correct
28 Correct 346 ms 33624 KB Output is correct
29 Correct 145 ms 21148 KB Output is correct
30 Correct 1012 ms 51344 KB Output is correct
31 Correct 180 ms 23404 KB Output is correct
32 Correct 159 ms 16876 KB Output is correct
33 Correct 574 ms 38988 KB Output is correct
34 Correct 775 ms 46060 KB Output is correct
35 Correct 998 ms 45420 KB Output is correct
36 Correct 942 ms 44524 KB Output is correct
37 Correct 384 ms 42624 KB Output is correct
38 Correct 386 ms 42732 KB Output is correct
39 Correct 407 ms 40084 KB Output is correct
40 Correct 409 ms 40108 KB Output is correct
41 Correct 1 ms 492 KB Output is correct
42 Correct 1050 ms 54448 KB Output is correct
43 Correct 558 ms 41836 KB Output is correct
44 Correct 804 ms 48640 KB Output is correct
45 Correct 1044 ms 48444 KB Output is correct
46 Correct 1967 ms 145788 KB Output is correct
47 Correct 1984 ms 146888 KB Output is correct
48 Correct 2125 ms 147948 KB Output is correct
49 Correct 2099 ms 146284 KB Output is correct
50 Correct 6945 ms 206944 KB Output is correct
51 Correct 3560 ms 141932 KB Output is correct
52 Correct 4678 ms 165076 KB Output is correct
53 Correct 6674 ms 203352 KB Output is correct

Subtask #7
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 438 ms 30924 KB Output is correct
2 Correct 428 ms 30828 KB Output is correct
3 Correct 155 ms 10604 KB Output is correct
4 Correct 315 ms 22636 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 376 ms 26860 KB Output is correct
7 Correct 79 ms 6124 KB Output is correct
8 Correct 80 ms 5996 KB Output is correct
9 Correct 160 ms 10732 KB Output is correct
10 Correct 366 ms 29920 KB Output is correct
11 Correct 112 ms 10732 KB Output is correct
12 Correct 1 ms 448 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 492 KB Output is correct
16 Correct 1 ms 492 KB Output is correct
17 Correct 1 ms 492 KB Output is correct
18 Correct 1 ms 492 KB Output is correct
19 Correct 1 ms 492 KB Output is correct
20 Correct 1 ms 492 KB Output is correct
21 Correct 1 ms 492 KB Output is correct
22 Correct 1 ms 492 KB Output is correct
23 Correct 1 ms 492 KB Output is correct
24 Correct 1 ms 492 KB Output is correct
25 Correct 1 ms 492 KB Output is correct
26 Correct 1 ms 492 KB Output is correct
27 Correct 1 ms 492 KB Output is correct
28 Correct 4 ms 748 KB Output is correct
29 Correct 4 ms 876 KB Output is correct
30 Correct 6 ms 1004 KB Output is correct
31 Correct 4 ms 876 KB Output is correct
32 Correct 6 ms 1004 KB Output is correct
33 Correct 6 ms 1004 KB Output is correct
34 Correct 6 ms 1004 KB Output is correct
35 Correct 349 ms 33132 KB Output is correct
36 Correct 361 ms 39708 KB Output is correct
37 Correct 363 ms 39788 KB Output is correct
38 Correct 364 ms 39660 KB Output is correct
39 Correct 346 ms 33624 KB Output is correct
40 Correct 145 ms 21148 KB Output is correct
41 Correct 1012 ms 51344 KB Output is correct
42 Correct 180 ms 23404 KB Output is correct
43 Correct 159 ms 16876 KB Output is correct
44 Correct 574 ms 38988 KB Output is correct
45 Correct 775 ms 46060 KB Output is correct
46 Correct 998 ms 45420 KB Output is correct
47 Correct 942 ms 44524 KB Output is correct
48 Correct 384 ms 42624 KB Output is correct
49 Correct 386 ms 42732 KB Output is correct
50 Correct 407 ms 40084 KB Output is correct
51 Correct 409 ms 40108 KB Output is correct
52 Correct 1 ms 492 KB Output is correct
53 Correct 1050 ms 54448 KB Output is correct
54 Correct 558 ms 41836 KB Output is correct
55 Correct 804 ms 48640 KB Output is correct
56 Correct 1044 ms 48444 KB Output is correct
57 Correct 390 ms 43244 KB Output is correct
58 Correct 395 ms 43288 KB Output is correct
59 Correct 419 ms 40976 KB Output is correct
60 Correct 432 ms 40940 KB Output is correct
61 Correct 1033 ms 52332 KB Output is correct
62 Correct 1 ms 492 KB Output is correct
63 Correct 1052 ms 54636 KB Output is correct
64 Correct 583 ms 41476 KB Output is correct
65 Correct 807 ms 49132 KB Output is correct
66 Correct 972 ms 47856 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 438 ms 30924 KB Output is correct
2 Correct 428 ms 30828 KB Output is correct
3 Correct 155 ms 10604 KB Output is correct
4 Correct 315 ms 22636 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 376 ms 26860 KB Output is correct
7 Correct 79 ms 6124 KB Output is correct
8 Correct 80 ms 5996 KB Output is correct
9 Correct 160 ms 10732 KB Output is correct
10 Correct 366 ms 29920 KB Output is correct
11 Correct 112 ms 10732 KB Output is correct
12 Correct 1 ms 448 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 492 KB Output is correct
16 Correct 1 ms 492 KB Output is correct
17 Correct 1 ms 492 KB Output is correct
18 Correct 1 ms 492 KB Output is correct
19 Correct 1 ms 492 KB Output is correct
20 Correct 1 ms 492 KB Output is correct
21 Correct 1 ms 492 KB Output is correct
22 Correct 1 ms 492 KB Output is correct
23 Correct 1 ms 492 KB Output is correct
24 Correct 1 ms 492 KB Output is correct
25 Correct 1 ms 492 KB Output is correct
26 Correct 1 ms 492 KB Output is correct
27 Correct 1 ms 492 KB Output is correct
28 Correct 4 ms 748 KB Output is correct
29 Correct 4 ms 876 KB Output is correct
30 Correct 6 ms 1004 KB Output is correct
31 Correct 4 ms 876 KB Output is correct
32 Correct 6 ms 1004 KB Output is correct
33 Correct 6 ms 1004 KB Output is correct
34 Correct 6 ms 1004 KB Output is correct
35 Correct 349 ms 33132 KB Output is correct
36 Correct 361 ms 39708 KB Output is correct
37 Correct 363 ms 39788 KB Output is correct
38 Correct 364 ms 39660 KB Output is correct
39 Correct 346 ms 33624 KB Output is correct
40 Correct 145 ms 21148 KB Output is correct
41 Correct 1012 ms 51344 KB Output is correct
42 Correct 180 ms 23404 KB Output is correct
43 Correct 159 ms 16876 KB Output is correct
44 Correct 574 ms 38988 KB Output is correct
45 Correct 775 ms 46060 KB Output is correct
46 Correct 998 ms 45420 KB Output is correct
47 Correct 942 ms 44524 KB Output is correct
48 Correct 384 ms 42624 KB Output is correct
49 Correct 386 ms 42732 KB Output is correct
50 Correct 407 ms 40084 KB Output is correct
51 Correct 409 ms 40108 KB Output is correct
52 Correct 1 ms 492 KB Output is correct
53 Correct 1050 ms 54448 KB Output is correct
54 Correct 558 ms 41836 KB Output is correct
55 Correct 804 ms 48640 KB Output is correct
56 Correct 1044 ms 48444 KB Output is correct
57 Correct 1967 ms 145788 KB Output is correct
58 Correct 1984 ms 146888 KB Output is correct
59 Correct 2125 ms 147948 KB Output is correct
60 Correct 2099 ms 146284 KB Output is correct
61 Correct 6945 ms 206944 KB Output is correct
62 Correct 3560 ms 141932 KB Output is correct
63 Correct 4678 ms 165076 KB Output is correct
64 Correct 6674 ms 203352 KB Output is correct
65 Correct 390 ms 43244 KB Output is correct
66 Correct 395 ms 43288 KB Output is correct
67 Correct 419 ms 40976 KB Output is correct
68 Correct 432 ms 40940 KB Output is correct
69 Correct 1033 ms 52332 KB Output is correct
70 Correct 1 ms 492 KB Output is correct
71 Correct 1052 ms 54636 KB Output is correct
72 Correct 583 ms 41476 KB Output is correct
73 Correct 807 ms 49132 KB Output is correct
74 Correct 972 ms 47856 KB Output is correct
75 Correct 2070 ms 152572 KB Output is correct
76 Correct 2029 ms 155184 KB Output is correct
77 Correct 2154 ms 153672 KB Output is correct
78 Correct 2169 ms 153800 KB Output is correct
79 Correct 7161 ms 215868 KB Output is correct
80 Correct 3570 ms 151148 KB Output is correct
81 Correct 4599 ms 181276 KB Output is correct
82 Correct 6668 ms 209992 KB Output is correct
83 Correct 6459 ms 207640 KB Output is correct