oj.uz

Submission #1079526

# Submission time Handle Problem Language Result Execution time Memory
1079526 2024-08-28T16:22:11 Z phong Two Dishes (JOI19_dishes) C++17
82 / 100
 965 ms 73632 KB 
#include<bits/stdc++.h>

#define ll long long
#define int long long
const int nmax = 2e5 + 5, N = 1e5;
const ll oo = 1e18 + 1, base = 311;
const int lg = 19, M = 10;
const ll mod = 998244353, mod2 = 1e9 + 5277;
#define pii pair<int, int>
#define fi first
#define se second
#define endl "\n"
#define debug(a, n) for(int i = 1; i <= n; ++i) cout << a[i] << ' '; cout << "\n";
using namespace std;

int n, m;
struct node{
    ll x, y, z;
}a[nmax], b[nmax];
map<int, ll> adj[nmax];
ll tree[nmax << 2], tr[nmax << 2];
pii lz[nmax << 2];
void build(int id, int l, int r){
    lz[id] = {1, 0};
    if(l != r){
        int mid = r + l >> 1;
        build(id << 1, l, mid);
        build(id << 1 | 1, mid + 1, r);
    }
}
void fix(int id, pii tx){
//    if(val == -oo) return;
    tree[id] = tree[id] * tx.fi + tx.se;
    tr[id] = tr[id] * tx.fi + tx.se;
    lz[id].fi = lz[id].fi * tx.fi;
    lz[id].se = lz[id].se * tx.fi + tx.se;
}
void down(int id){
    fix(id << 1, lz[id]);
    fix(id << 1 | 1, lz[id]);
    lz[id] = {1, 0};
}
void update(int id, int l, int r, int u, int v, pii val, int k){
    if(l > v || r < u || tr[id] > k) return;
    if(l >= u && r<= v && tree[id] <= k){
        return fix(id, val);
    }
    down(id);
    int mid = r + l >> 1;
    update(id << 1, l, mid, u, v,val, k);
    update(id << 1 |1, mid + 1, r, u,v, val, k);
    tree[id] = max(tree[id << 1], tree[id << 1 | 1]);
    tr[id] = min(tr[id << 1], tr[id << 1 | 1]);

//    for(int i = u; i <= v; ++i){
//        if(tree[i] > k) continue;
//        tree[i] = tree[i] * val.fi + val.se;
//    }
}
int get(int id, int l, int r, int u, int v){
    if(l >= u && r <=v ) return tree[id];
    int mid = r + l >> 1;
    down(id);
    if(mid < u) return get(id << 1 | 1, mid + 1, r,u, v);
    if(mid + 1 > v) return get(id << 1, l, mid, u, v);
    return max(get(id << 1, l, mid, u, v), get(id << 1 | 1, mid + 1, r, u, v));
//    int ma = -oo;
//    for(int i = u; i <= v; ++i) ma = max(ma, tree[i]);
//    return ma;
}
main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
//    freopen("code.inp", "r", stdin);
//    freopen("code.out", "w", stdout);
    cin >> n >> m;
    for(int i = 1; i <= n; ++i) cin >> a[i].x >> a[i].y >> a[i].z, a[i].x += a[i - 1].x;
    for(int i = 1; i <= m; ++i) cin >> b[i].x >> b[i].y >> b[i].z, b[i].x += b[i - 1].x;
    ll ans  = 0;
    for(int i = 1; i <= n; ++i){
        if(a[i].x <= a[i].y){
            int l = 1, r = m, it = m + 1;
            while(l <= r){
                int mid = r + l >> 1;
                if(b[mid].x > a[i].y - a[i].x){
                    r = mid - 1;
                    it = mid;
                }
                else l = mid + 1;
            }
            ans += a[i].z;
            if(it <= m) adj[i][it] -= a[i].z;
        }
    }
    for(int i = 1; i <= m; ++i){

        if(b[i].x <= b[i].y){
            int l = 1, r = n, it = n + 1;
            while(l <= r){
                int mid = r + l >> 1;
                if(a[mid].x > b[i].y - b[i].x){
                    r = mid - 1;
                    it = mid;
                }
                else l = mid + 1;
            }
//             cout << i << ' ' << it << endl;
            if(it > n) ans += b[i].z;
            else adj[it][i] += b[i].z;
        }
    }
//    memset(dp, -63, sizeof dp);
//    dp[0][0] = 0;
    build(1, 0, m);
    vector<pii> tmp;
    for(int i = 1; i <= n; ++i){

        ll sum = 0;
        for(auto [j, val] : adj[i]){
//            sum += val;
             update(1, 0, m, j, m, {1, val}, oo);
//            if(i == 3) cout <<get(1, 0, m, 0, j) << ' ';
            tmp.push_back({get(1, 0, m, 0, j), j});
        }
        sort(tmp.begin(), tmp.end());
        for(auto [val, j] : tmp){
             update(1, 0, m, j, m, {0, val}, val);
        }
//        for(int j = 0; j <= m; ++j) cout << get(1, 0, m, j, j) << ' ';
//        cout << endl;
        tmp.clear();
    }
    cout << tree[1] + ans;

}
/*
5
10 2 4
1 1 1
2 1 3
1 1 1
100 1 1
1
1 3
*/

Compilation message

dishes.cpp: In function 'void build(long long int, long long int, long long int)':
dishes.cpp:26:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   26 |         int mid = r + l >> 1;
      |                   ~~^~~
dishes.cpp: In function 'void update(long long int, long long int, long long int, long long int, long long int, std::pair<long long int, long long int>, long long int)':
dishes.cpp:49:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   49 |     int mid = r + l >> 1;
      |               ~~^~~
dishes.cpp: In function 'long long int get(long long int, long long int, long long int, long long int, long long int)':
dishes.cpp:62:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   62 |     int mid = r + l >> 1;
      |               ~~^~~
dishes.cpp: At global scope:
dishes.cpp:71:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   71 | main(){
      | ^~~~
dishes.cpp: In function 'int main()':
dishes.cpp:84:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   84 |                 int mid = r + l >> 1;
      |                           ~~^~~
dishes.cpp:100:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  100 |                 int mid = r + l >> 1;
      |                           ~~^~~
dishes.cpp:118:12: warning: unused variable 'sum' [-Wunused-variable]
  118 |         ll sum = 0;
      |            ^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 349 ms 62800 KB Output is correct
2 Correct 346 ms 62540 KB Output is correct
3 Correct 104 ms 40784 KB Output is correct
4 Correct 233 ms 53896 KB Output is correct
5 Correct 4 ms 9820 KB Output is correct
6 Correct 310 ms 58556 KB Output is correct
7 Correct 56 ms 29520 KB Output is correct
8 Correct 49 ms 21328 KB Output is correct
9 Correct 128 ms 41708 KB Output is correct
10 Correct 298 ms 55376 KB Output is correct
11 Correct 77 ms 35036 KB Output is correct

Subtask #2
3.0 / 3.0

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

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9820 KB Output is correct
2 Correct 4 ms 9820 KB Output is correct
3 Correct 4 ms 9788 KB Output is correct
4 Correct 4 ms 9820 KB Output is correct
5 Correct 5 ms 9820 KB Output is correct
6 Correct 3 ms 9816 KB Output is correct
7 Correct 4 ms 9820 KB Output is correct
8 Correct 4 ms 9820 KB Output is correct
9 Correct 4 ms 9820 KB Output is correct
10 Correct 4 ms 9820 KB Output is correct
11 Correct 4 ms 9820 KB Output is correct
12 Correct 4 ms 9820 KB Output is correct
13 Correct 4 ms 9820 KB Output is correct
14 Correct 4 ms 9820 KB Output is correct
15 Correct 4 ms 9820 KB Output is correct
16 Correct 4 ms 9816 KB Output is correct
17 Correct 7 ms 10328 KB Output is correct
18 Correct 7 ms 10328 KB Output is correct
19 Correct 8 ms 10444 KB Output is correct
20 Correct 6 ms 10076 KB Output is correct
21 Correct 8 ms 10308 KB Output is correct
22 Correct 8 ms 10332 KB Output is correct
23 Correct 12 ms 10332 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9820 KB Output is correct
2 Correct 4 ms 9820 KB Output is correct
3 Correct 4 ms 9788 KB Output is correct
4 Correct 4 ms 9820 KB Output is correct
5 Correct 5 ms 9820 KB Output is correct
6 Correct 3 ms 9816 KB Output is correct
7 Correct 4 ms 9820 KB Output is correct
8 Correct 4 ms 9820 KB Output is correct
9 Correct 4 ms 9820 KB Output is correct
10 Correct 4 ms 9820 KB Output is correct
11 Correct 4 ms 9820 KB Output is correct
12 Correct 4 ms 9820 KB Output is correct
13 Correct 4 ms 9820 KB Output is correct
14 Correct 4 ms 9820 KB Output is correct
15 Correct 4 ms 9820 KB Output is correct
16 Correct 4 ms 9816 KB Output is correct
17 Correct 7 ms 10328 KB Output is correct
18 Correct 7 ms 10328 KB Output is correct
19 Correct 8 ms 10444 KB Output is correct
20 Correct 6 ms 10076 KB Output is correct
21 Correct 8 ms 10308 KB Output is correct
22 Correct 8 ms 10332 KB Output is correct
23 Correct 12 ms 10332 KB Output is correct
24 Correct 310 ms 50512 KB Output is correct
25 Correct 313 ms 61032 KB Output is correct
26 Correct 295 ms 58764 KB Output is correct
27 Correct 305 ms 58708 KB Output is correct
28 Correct 267 ms 52912 KB Output is correct
29 Correct 99 ms 38484 KB Output is correct
30 Correct 797 ms 70476 KB Output is correct
31 Correct 165 ms 43968 KB Output is correct
32 Correct 57 ms 25880 KB Output is correct
33 Correct 442 ms 57868 KB Output is correct
34 Correct 625 ms 65444 KB Output is correct
35 Correct 781 ms 64592 KB Output is correct
36 Correct 762 ms 63596 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9820 KB Output is correct
2 Correct 4 ms 9820 KB Output is correct
3 Correct 4 ms 9788 KB Output is correct
4 Correct 4 ms 9820 KB Output is correct
5 Correct 5 ms 9820 KB Output is correct
6 Correct 3 ms 9816 KB Output is correct
7 Correct 4 ms 9820 KB Output is correct
8 Correct 4 ms 9820 KB Output is correct
9 Correct 4 ms 9820 KB Output is correct
10 Correct 4 ms 9820 KB Output is correct
11 Correct 4 ms 9820 KB Output is correct
12 Correct 4 ms 9820 KB Output is correct
13 Correct 4 ms 9820 KB Output is correct
14 Correct 4 ms 9820 KB Output is correct
15 Correct 4 ms 9820 KB Output is correct
16 Correct 4 ms 9816 KB Output is correct
17 Correct 7 ms 10328 KB Output is correct
18 Correct 7 ms 10328 KB Output is correct
19 Correct 8 ms 10444 KB Output is correct
20 Correct 6 ms 10076 KB Output is correct
21 Correct 8 ms 10308 KB Output is correct
22 Correct 8 ms 10332 KB Output is correct
23 Correct 12 ms 10332 KB Output is correct
24 Correct 310 ms 50512 KB Output is correct
25 Correct 313 ms 61032 KB Output is correct
26 Correct 295 ms 58764 KB Output is correct
27 Correct 305 ms 58708 KB Output is correct
28 Correct 267 ms 52912 KB Output is correct
29 Correct 99 ms 38484 KB Output is correct
30 Correct 797 ms 70476 KB Output is correct
31 Correct 165 ms 43968 KB Output is correct
32 Correct 57 ms 25880 KB Output is correct
33 Correct 442 ms 57868 KB Output is correct
34 Correct 625 ms 65444 KB Output is correct
35 Correct 781 ms 64592 KB Output is correct
36 Correct 762 ms 63596 KB Output is correct
37 Correct 343 ms 61840 KB Output is correct
38 Correct 319 ms 61616 KB Output is correct
39 Correct 341 ms 58964 KB Output is correct
40 Correct 451 ms 59192 KB Output is correct
41 Correct 4 ms 9816 KB Output is correct
42 Correct 817 ms 73432 KB Output is correct
43 Correct 479 ms 60980 KB Output is correct
44 Correct 639 ms 67928 KB Output is correct
45 Correct 820 ms 67664 KB Output is correct

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9820 KB Output is correct
2 Correct 4 ms 9820 KB Output is correct
3 Correct 4 ms 9788 KB Output is correct
4 Correct 4 ms 9820 KB Output is correct
5 Correct 5 ms 9820 KB Output is correct
6 Correct 3 ms 9816 KB Output is correct
7 Correct 4 ms 9820 KB Output is correct
8 Correct 4 ms 9820 KB Output is correct
9 Correct 4 ms 9820 KB Output is correct
10 Correct 4 ms 9820 KB Output is correct
11 Correct 4 ms 9820 KB Output is correct
12 Correct 4 ms 9820 KB Output is correct
13 Correct 4 ms 9820 KB Output is correct
14 Correct 4 ms 9820 KB Output is correct
15 Correct 4 ms 9820 KB Output is correct
16 Correct 4 ms 9816 KB Output is correct
17 Correct 7 ms 10328 KB Output is correct
18 Correct 7 ms 10328 KB Output is correct
19 Correct 8 ms 10444 KB Output is correct
20 Correct 6 ms 10076 KB Output is correct
21 Correct 8 ms 10308 KB Output is correct
22 Correct 8 ms 10332 KB Output is correct
23 Correct 12 ms 10332 KB Output is correct
24 Correct 310 ms 50512 KB Output is correct
25 Correct 313 ms 61032 KB Output is correct
26 Correct 295 ms 58764 KB Output is correct
27 Correct 305 ms 58708 KB Output is correct
28 Correct 267 ms 52912 KB Output is correct
29 Correct 99 ms 38484 KB Output is correct
30 Correct 797 ms 70476 KB Output is correct
31 Correct 165 ms 43968 KB Output is correct
32 Correct 57 ms 25880 KB Output is correct
33 Correct 442 ms 57868 KB Output is correct
34 Correct 625 ms 65444 KB Output is correct
35 Correct 781 ms 64592 KB Output is correct
36 Correct 762 ms 63596 KB Output is correct
37 Correct 343 ms 61840 KB Output is correct
38 Correct 319 ms 61616 KB Output is correct
39 Correct 341 ms 58964 KB Output is correct
40 Correct 451 ms 59192 KB Output is correct
41 Correct 4 ms 9816 KB Output is correct
42 Correct 817 ms 73432 KB Output is correct
43 Correct 479 ms 60980 KB Output is correct
44 Correct 639 ms 67928 KB Output is correct
45 Correct 820 ms 67664 KB Output is correct
46 Runtime error 65 ms 36084 KB Execution killed with signal 11
47 Halted 0 ms 0 KB -

Subtask #7
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 349 ms 62800 KB Output is correct
2 Correct 346 ms 62540 KB Output is correct
3 Correct 104 ms 40784 KB Output is correct
4 Correct 233 ms 53896 KB Output is correct
5 Correct 4 ms 9820 KB Output is correct
6 Correct 310 ms 58556 KB Output is correct
7 Correct 56 ms 29520 KB Output is correct
8 Correct 49 ms 21328 KB Output is correct
9 Correct 128 ms 41708 KB Output is correct
10 Correct 298 ms 55376 KB Output is correct
11 Correct 77 ms 35036 KB Output is correct
12 Correct 5 ms 9820 KB Output is correct
13 Correct 4 ms 9820 KB Output is correct
14 Correct 4 ms 9788 KB Output is correct
15 Correct 4 ms 9820 KB Output is correct
16 Correct 5 ms 9820 KB Output is correct
17 Correct 3 ms 9816 KB Output is correct
18 Correct 4 ms 9820 KB Output is correct
19 Correct 4 ms 9820 KB Output is correct
20 Correct 4 ms 9820 KB Output is correct
21 Correct 4 ms 9820 KB Output is correct
22 Correct 4 ms 9820 KB Output is correct
23 Correct 4 ms 9820 KB Output is correct
24 Correct 4 ms 9820 KB Output is correct
25 Correct 4 ms 9820 KB Output is correct
26 Correct 4 ms 9820 KB Output is correct
27 Correct 4 ms 9816 KB Output is correct
28 Correct 7 ms 10328 KB Output is correct
29 Correct 7 ms 10328 KB Output is correct
30 Correct 8 ms 10444 KB Output is correct
31 Correct 6 ms 10076 KB Output is correct
32 Correct 8 ms 10308 KB Output is correct
33 Correct 8 ms 10332 KB Output is correct
34 Correct 12 ms 10332 KB Output is correct
35 Correct 310 ms 50512 KB Output is correct
36 Correct 313 ms 61032 KB Output is correct
37 Correct 295 ms 58764 KB Output is correct
38 Correct 305 ms 58708 KB Output is correct
39 Correct 267 ms 52912 KB Output is correct
40 Correct 99 ms 38484 KB Output is correct
41 Correct 797 ms 70476 KB Output is correct
42 Correct 165 ms 43968 KB Output is correct
43 Correct 57 ms 25880 KB Output is correct
44 Correct 442 ms 57868 KB Output is correct
45 Correct 625 ms 65444 KB Output is correct
46 Correct 781 ms 64592 KB Output is correct
47 Correct 762 ms 63596 KB Output is correct
48 Correct 343 ms 61840 KB Output is correct
49 Correct 319 ms 61616 KB Output is correct
50 Correct 341 ms 58964 KB Output is correct
51 Correct 451 ms 59192 KB Output is correct
52 Correct 4 ms 9816 KB Output is correct
53 Correct 817 ms 73432 KB Output is correct
54 Correct 479 ms 60980 KB Output is correct
55 Correct 639 ms 67928 KB Output is correct
56 Correct 820 ms 67664 KB Output is correct
57 Correct 358 ms 62120 KB Output is correct
58 Correct 329 ms 62308 KB Output is correct
59 Correct 467 ms 60188 KB Output is correct
60 Correct 382 ms 59988 KB Output is correct
61 Correct 847 ms 71412 KB Output is correct
62 Correct 6 ms 9816 KB Output is correct
63 Correct 894 ms 73632 KB Output is correct
64 Correct 528 ms 60936 KB Output is correct
65 Correct 834 ms 68152 KB Output is correct
66 Correct 965 ms 66780 KB Output is correct

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 349 ms 62800 KB Output is correct
2 Correct 346 ms 62540 KB Output is correct
3 Correct 104 ms 40784 KB Output is correct
4 Correct 233 ms 53896 KB Output is correct
5 Correct 4 ms 9820 KB Output is correct
6 Correct 310 ms 58556 KB Output is correct
7 Correct 56 ms 29520 KB Output is correct
8 Correct 49 ms 21328 KB Output is correct
9 Correct 128 ms 41708 KB Output is correct
10 Correct 298 ms 55376 KB Output is correct
11 Correct 77 ms 35036 KB Output is correct
12 Correct 5 ms 9820 KB Output is correct
13 Correct 4 ms 9820 KB Output is correct
14 Correct 4 ms 9788 KB Output is correct
15 Correct 4 ms 9820 KB Output is correct
16 Correct 5 ms 9820 KB Output is correct
17 Correct 3 ms 9816 KB Output is correct
18 Correct 4 ms 9820 KB Output is correct
19 Correct 4 ms 9820 KB Output is correct
20 Correct 4 ms 9820 KB Output is correct
21 Correct 4 ms 9820 KB Output is correct
22 Correct 4 ms 9820 KB Output is correct
23 Correct 4 ms 9820 KB Output is correct
24 Correct 4 ms 9820 KB Output is correct
25 Correct 4 ms 9820 KB Output is correct
26 Correct 4 ms 9820 KB Output is correct
27 Correct 4 ms 9816 KB Output is correct
28 Correct 7 ms 10328 KB Output is correct
29 Correct 7 ms 10328 KB Output is correct
30 Correct 8 ms 10444 KB Output is correct
31 Correct 6 ms 10076 KB Output is correct
32 Correct 8 ms 10308 KB Output is correct
33 Correct 8 ms 10332 KB Output is correct
34 Correct 12 ms 10332 KB Output is correct
35 Correct 310 ms 50512 KB Output is correct
36 Correct 313 ms 61032 KB Output is correct
37 Correct 295 ms 58764 KB Output is correct
38 Correct 305 ms 58708 KB Output is correct
39 Correct 267 ms 52912 KB Output is correct
40 Correct 99 ms 38484 KB Output is correct
41 Correct 797 ms 70476 KB Output is correct
42 Correct 165 ms 43968 KB Output is correct
43 Correct 57 ms 25880 KB Output is correct
44 Correct 442 ms 57868 KB Output is correct
45 Correct 625 ms 65444 KB Output is correct
46 Correct 781 ms 64592 KB Output is correct
47 Correct 762 ms 63596 KB Output is correct
48 Correct 343 ms 61840 KB Output is correct
49 Correct 319 ms 61616 KB Output is correct
50 Correct 341 ms 58964 KB Output is correct
51 Correct 451 ms 59192 KB Output is correct
52 Correct 4 ms 9816 KB Output is correct
53 Correct 817 ms 73432 KB Output is correct
54 Correct 479 ms 60980 KB Output is correct
55 Correct 639 ms 67928 KB Output is correct
56 Correct 820 ms 67664 KB Output is correct
57 Runtime error 65 ms 36084 KB Execution killed with signal 11
58 Halted 0 ms 0 KB -