oj.uz

Submission #365865

# Submission time Handle Problem Language Result Execution time Memory
365865 2021-02-12T13:08:39 Z vaaven Two Dishes (JOI19_dishes) C++14
100 / 100
 5187 ms 178560 KB 
//#pragma GCC target("avx2")
//#pragma GCC optimize("O3")
#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <set>
#include <stack>
#include <iomanip>
#include <bitset>
#include <map>
#include <cassert>
#include <array>
#include <queue>
#include <cstring>
#include <random>
#include <unordered_set>
#include <unordered_map>
#define pqueue priority_queue
#define pb(x) push_back(x)
// #define endl '\n'
#define all(x) x.begin(), x.end()
#define int long  long

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
// typedef tuple<ll, ll, ll> tiii;
typedef pair<int, int> pii;
typedef vector<pair<int, int> > vpii;
typedef vector<bool> vb;
typedef vector<string> vs;
typedef vector<char> vc;

const int inf = 1e9;
const ll mod = 1e9 + 7;
const ll mod2 = 998244353;
const ld eps = 1e-14;


void fast_io(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
//    freopen("cbs.in", "r", stdin);
//    freopen("cbs.out", "w", stdout);
}

const int maxn = 1e6 + 228;

vpii kek[maxn];
int t[maxn*4];
int cnt[maxn*4];
int A[maxn], B[maxn], S[maxn], T[maxn], P[maxn], Q[maxn];
ll lzy[4*maxn];
ll mx[4*maxn];
void push(int n) {
    lzy[2*n] += lzy[n];
    lzy[2*n+1] += lzy[n];
    mx[2*n] += lzy[n];
    mx[2*n+1] += lzy[n];
    lzy[n] = 0;
}
void add(int n, int tl, int tr, int l, int r, ll ad) {
    if (tr < l || r < tl) {
        return;
    }
    if (l <= tl && tr <= r) {
        lzy[n] += ad;
        mx[n] += ad;
    }
    else {
        push(n);
        int tm = (tl + tr)/2;
        add(2*n, tl, tm, l, r, ad);
        add(2*n+1, tm+1, tr, l, r, ad);
        mx[n] = max(mx[2*n], mx[2*n+1]);
    }
}
ll get(int n, int tl, int tr, int l, int r) {
   if (tr < l || r < tl) {
        return -1e18;
    }
    if (l <= tl && tr <= r) {
        return mx[n];
    }
    else {
        push(n);
        int tm = (tl + tr)/2;
        return max(get(2*n, tl, tm, l, r), get(2*n+1, tm+1, tr, l, r));
    }
}
void upd(int n, int tl, int tr, int i, ll val) {
    if (tl == tr) {
        mx[n] = max(mx[n], val);
        lzy[n] = 0;
    }
    else {
        push(n);
        int tm = (tl + tr)/2;
        if (i <= tm) {
            upd(2*n, tl, tm, i, val);
        }
        else {
            upd(2*n+1, tm+1, tr, i, val);
        }
        mx[n] = max(mx[2*n], mx[2*n+1]);
    }
}

void solve(){
    int n, m;
    cin >> n >> m;
    for(int &i:mx)
        i = -1e18;
//    cout << t[0] << endl;
    for(int i=1; i<=n; i++){
        cin >> A[i] >> S[i] >> P[i];
        A[i] += A[i-1];
    }
    for(int i=1; i<=m; i++){
        cin >> B[i] >> T[i] >> Q[i];
        B[i] += B[i-1];
    }
    int ans = 0;
    for(int i=1; i<=n; i++){
        if(A[i] > S[i]){
            continue;
        }
        if(A[i] + B[m] <= S[i]){
            ans += P[i];
            continue;
        }
        int l = 0, r = m;
        int j = 0;
        while(l<r){
            int mid = (l+r+1)/2;
            if(B[mid] <= S[i]-A[i]){
                l = mid;
                j = mid;
            } else{
                r = mid-1;
            }
        }
        kek[i].pb(make_pair(j, P[i]));
    }
    for(int i=1; i<=m; i++){
        if(B[i] > T[i]){
            continue;
        }
        int l = 0, r = n;
        int j = 0;
        while(l<r){
            int mid = (l+r+1)/2;
            if(A[mid] <= T[i]-B[i]){
                l = mid;
                j = mid;
            } else{
                r = mid-1;
            }
        }
        ans += Q[i];
        if(j < n){
            kek[j+1].pb(make_pair(i-1, -Q[i]));
        }
    }
    upd(1, 0, maxn, 0, 0);
    for(int i=0; i<=n; i++){
        sort(all(kek[i]));
        while(!kek[i].empty()){
            while(kek[i].size() > 1){
                if(kek[i][kek[i].size()-1].first == kek[i][kek[i].size()-2].first){
                    kek[i][kek[i].size()-2].second += kek[i][kek[i].size()-1].second;
                    kek[i].pop_back();
                } else{
                    break;
                }
            }
            int lol = get(1, 0, maxn, 0, kek[i].back().first);
            upd(1, 0, maxn, kek[i].back().first+1, lol);
            add(1, 0, maxn, 0, kek[i].back().first, kek[i].back().second);
            kek[i].pop_back();
        }
    }
    ans += mx[1];
    cout << ans << endl;
}

/*
4 3
2 1 1
3 8 1
2 13 1
1 13 1
3 6 1
2 11 1
2 15 1
======
5 7
16 73 16
17 73 10
20 73 1
14 73 16
18 73 10
3 73 2
10 73 7
16 73 19
12 73 4
15 73 15
20 73 14
15 73 8
=========
 9 11
 86 565 58
 41 469 -95
 73 679 28
 91 585 -78
 17 513 -63
 48 878 -66
 66 901 59
 72 983 -70
 68 1432 11
 42 386 -87
 36 895 57
 100 164 10
 96 812 -6
 23 961 -66
 54 193 51
 37 709 82
 62 148 -36
 28 853 22
 15 44 53
 77 660 -19
 */

signed main(){
     fast_io();
//  srand(time(NULL));
    cout << fixed << setprecision(10);
    int q = 1;
//    cin >> q;
    while(q--)
        solve();
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 475 ms 81056 KB Output is correct
2 Correct 463 ms 81436 KB Output is correct
3 Correct 211 ms 68944 KB Output is correct
4 Correct 370 ms 76652 KB Output is correct
5 Correct 34 ms 55276 KB Output is correct
6 Correct 427 ms 78992 KB Output is correct
7 Correct 119 ms 64236 KB Output is correct
8 Correct 140 ms 64236 KB Output is correct
9 Correct 234 ms 68716 KB Output is correct
10 Correct 387 ms 81772 KB Output is correct
11 Correct 158 ms 68972 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 55276 KB Output is correct
2 Correct 34 ms 55276 KB Output is correct
3 Correct 37 ms 55276 KB Output is correct
4 Correct 34 ms 55276 KB Output is correct
5 Correct 34 ms 55276 KB Output is correct
6 Correct 34 ms 55276 KB Output is correct
7 Correct 34 ms 55276 KB Output is correct
8 Correct 34 ms 55276 KB Output is correct
9 Correct 35 ms 55276 KB Output is correct
10 Correct 35 ms 55276 KB Output is correct
11 Correct 35 ms 55296 KB Output is correct
12 Correct 36 ms 55276 KB Output is correct
13 Correct 35 ms 55276 KB Output is correct
14 Correct 34 ms 55276 KB Output is correct
15 Correct 34 ms 55276 KB Output is correct
16 Correct 34 ms 55276 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 55276 KB Output is correct
2 Correct 34 ms 55276 KB Output is correct
3 Correct 37 ms 55276 KB Output is correct
4 Correct 34 ms 55276 KB Output is correct
5 Correct 34 ms 55276 KB Output is correct
6 Correct 34 ms 55276 KB Output is correct
7 Correct 34 ms 55276 KB Output is correct
8 Correct 34 ms 55276 KB Output is correct
9 Correct 35 ms 55276 KB Output is correct
10 Correct 35 ms 55276 KB Output is correct
11 Correct 35 ms 55296 KB Output is correct
12 Correct 36 ms 55276 KB Output is correct
13 Correct 35 ms 55276 KB Output is correct
14 Correct 34 ms 55276 KB Output is correct
15 Correct 34 ms 55276 KB Output is correct
16 Correct 34 ms 55276 KB Output is correct
17 Correct 37 ms 55532 KB Output is correct
18 Correct 38 ms 55532 KB Output is correct
19 Correct 40 ms 55660 KB Output is correct
20 Correct 38 ms 55532 KB Output is correct
21 Correct 40 ms 55532 KB Output is correct
22 Correct 40 ms 55660 KB Output is correct
23 Correct 41 ms 55532 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 55276 KB Output is correct
2 Correct 34 ms 55276 KB Output is correct
3 Correct 37 ms 55276 KB Output is correct
4 Correct 34 ms 55276 KB Output is correct
5 Correct 34 ms 55276 KB Output is correct
6 Correct 34 ms 55276 KB Output is correct
7 Correct 34 ms 55276 KB Output is correct
8 Correct 34 ms 55276 KB Output is correct
9 Correct 35 ms 55276 KB Output is correct
10 Correct 35 ms 55276 KB Output is correct
11 Correct 35 ms 55296 KB Output is correct
12 Correct 36 ms 55276 KB Output is correct
13 Correct 35 ms 55276 KB Output is correct
14 Correct 34 ms 55276 KB Output is correct
15 Correct 34 ms 55276 KB Output is correct
16 Correct 34 ms 55276 KB Output is correct
17 Correct 37 ms 55532 KB Output is correct
18 Correct 38 ms 55532 KB Output is correct
19 Correct 40 ms 55660 KB Output is correct
20 Correct 38 ms 55532 KB Output is correct
21 Correct 40 ms 55532 KB Output is correct
22 Correct 40 ms 55660 KB Output is correct
23 Correct 41 ms 55532 KB Output is correct
24 Correct 369 ms 73912 KB Output is correct
25 Correct 374 ms 74128 KB Output is correct
26 Correct 389 ms 77164 KB Output is correct
27 Correct 427 ms 77164 KB Output is correct
28 Correct 348 ms 73836 KB Output is correct
29 Correct 182 ms 67564 KB Output is correct
30 Correct 830 ms 82560 KB Output is correct
31 Correct 213 ms 68196 KB Output is correct
32 Correct 222 ms 66412 KB Output is correct
33 Correct 512 ms 76524 KB Output is correct
34 Correct 695 ms 79620 KB Output is correct
35 Correct 804 ms 83052 KB Output is correct
36 Correct 765 ms 82540 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 55276 KB Output is correct
2 Correct 34 ms 55276 KB Output is correct
3 Correct 37 ms 55276 KB Output is correct
4 Correct 34 ms 55276 KB Output is correct
5 Correct 34 ms 55276 KB Output is correct
6 Correct 34 ms 55276 KB Output is correct
7 Correct 34 ms 55276 KB Output is correct
8 Correct 34 ms 55276 KB Output is correct
9 Correct 35 ms 55276 KB Output is correct
10 Correct 35 ms 55276 KB Output is correct
11 Correct 35 ms 55296 KB Output is correct
12 Correct 36 ms 55276 KB Output is correct
13 Correct 35 ms 55276 KB Output is correct
14 Correct 34 ms 55276 KB Output is correct
15 Correct 34 ms 55276 KB Output is correct
16 Correct 34 ms 55276 KB Output is correct
17 Correct 37 ms 55532 KB Output is correct
18 Correct 38 ms 55532 KB Output is correct
19 Correct 40 ms 55660 KB Output is correct
20 Correct 38 ms 55532 KB Output is correct
21 Correct 40 ms 55532 KB Output is correct
22 Correct 40 ms 55660 KB Output is correct
23 Correct 41 ms 55532 KB Output is correct
24 Correct 369 ms 73912 KB Output is correct
25 Correct 374 ms 74128 KB Output is correct
26 Correct 389 ms 77164 KB Output is correct
27 Correct 427 ms 77164 KB Output is correct
28 Correct 348 ms 73836 KB Output is correct
29 Correct 182 ms 67564 KB Output is correct
30 Correct 830 ms 82560 KB Output is correct
31 Correct 213 ms 68196 KB Output is correct
32 Correct 222 ms 66412 KB Output is correct
33 Correct 512 ms 76524 KB Output is correct
34 Correct 695 ms 79620 KB Output is correct
35 Correct 804 ms 83052 KB Output is correct
36 Correct 765 ms 82540 KB Output is correct
37 Correct 416 ms 77164 KB Output is correct
38 Correct 416 ms 77168 KB Output is correct
39 Correct 415 ms 80236 KB Output is correct
40 Correct 429 ms 80108 KB Output is correct
41 Correct 35 ms 55276 KB Output is correct
42 Correct 860 ms 81728 KB Output is correct
43 Correct 536 ms 75536 KB Output is correct
44 Correct 692 ms 78316 KB Output is correct
45 Correct 836 ms 81772 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 55276 KB Output is correct
2 Correct 34 ms 55276 KB Output is correct
3 Correct 37 ms 55276 KB Output is correct
4 Correct 34 ms 55276 KB Output is correct
5 Correct 34 ms 55276 KB Output is correct
6 Correct 34 ms 55276 KB Output is correct
7 Correct 34 ms 55276 KB Output is correct
8 Correct 34 ms 55276 KB Output is correct
9 Correct 35 ms 55276 KB Output is correct
10 Correct 35 ms 55276 KB Output is correct
11 Correct 35 ms 55296 KB Output is correct
12 Correct 36 ms 55276 KB Output is correct
13 Correct 35 ms 55276 KB Output is correct
14 Correct 34 ms 55276 KB Output is correct
15 Correct 34 ms 55276 KB Output is correct
16 Correct 34 ms 55276 KB Output is correct
17 Correct 37 ms 55532 KB Output is correct
18 Correct 38 ms 55532 KB Output is correct
19 Correct 40 ms 55660 KB Output is correct
20 Correct 38 ms 55532 KB Output is correct
21 Correct 40 ms 55532 KB Output is correct
22 Correct 40 ms 55660 KB Output is correct
23 Correct 41 ms 55532 KB Output is correct
24 Correct 369 ms 73912 KB Output is correct
25 Correct 374 ms 74128 KB Output is correct
26 Correct 389 ms 77164 KB Output is correct
27 Correct 427 ms 77164 KB Output is correct
28 Correct 348 ms 73836 KB Output is correct
29 Correct 182 ms 67564 KB Output is correct
30 Correct 830 ms 82560 KB Output is correct
31 Correct 213 ms 68196 KB Output is correct
32 Correct 222 ms 66412 KB Output is correct
33 Correct 512 ms 76524 KB Output is correct
34 Correct 695 ms 79620 KB Output is correct
35 Correct 804 ms 83052 KB Output is correct
36 Correct 765 ms 82540 KB Output is correct
37 Correct 416 ms 77164 KB Output is correct
38 Correct 416 ms 77168 KB Output is correct
39 Correct 415 ms 80236 KB Output is correct
40 Correct 429 ms 80108 KB Output is correct
41 Correct 35 ms 55276 KB Output is correct
42 Correct 860 ms 81728 KB Output is correct
43 Correct 536 ms 75536 KB Output is correct
44 Correct 692 ms 78316 KB Output is correct
45 Correct 836 ms 81772 KB Output is correct
46 Correct 1966 ms 152256 KB Output is correct
47 Correct 1970 ms 151848 KB Output is correct
48 Correct 1955 ms 167728 KB Output is correct
49 Correct 1924 ms 167784 KB Output is correct
50 Correct 5100 ms 178560 KB Output is correct
51 Correct 2802 ms 145692 KB Output is correct
52 Correct 3506 ms 155096 KB Output is correct
53 Correct 4720 ms 176192 KB Output is correct

Subtask #7
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 475 ms 81056 KB Output is correct
2 Correct 463 ms 81436 KB Output is correct
3 Correct 211 ms 68944 KB Output is correct
4 Correct 370 ms 76652 KB Output is correct
5 Correct 34 ms 55276 KB Output is correct
6 Correct 427 ms 78992 KB Output is correct
7 Correct 119 ms 64236 KB Output is correct
8 Correct 140 ms 64236 KB Output is correct
9 Correct 234 ms 68716 KB Output is correct
10 Correct 387 ms 81772 KB Output is correct
11 Correct 158 ms 68972 KB Output is correct
12 Correct 34 ms 55276 KB Output is correct
13 Correct 34 ms 55276 KB Output is correct
14 Correct 37 ms 55276 KB Output is correct
15 Correct 34 ms 55276 KB Output is correct
16 Correct 34 ms 55276 KB Output is correct
17 Correct 34 ms 55276 KB Output is correct
18 Correct 34 ms 55276 KB Output is correct
19 Correct 34 ms 55276 KB Output is correct
20 Correct 35 ms 55276 KB Output is correct
21 Correct 35 ms 55276 KB Output is correct
22 Correct 35 ms 55296 KB Output is correct
23 Correct 36 ms 55276 KB Output is correct
24 Correct 35 ms 55276 KB Output is correct
25 Correct 34 ms 55276 KB Output is correct
26 Correct 34 ms 55276 KB Output is correct
27 Correct 34 ms 55276 KB Output is correct
28 Correct 37 ms 55532 KB Output is correct
29 Correct 38 ms 55532 KB Output is correct
30 Correct 40 ms 55660 KB Output is correct
31 Correct 38 ms 55532 KB Output is correct
32 Correct 40 ms 55532 KB Output is correct
33 Correct 40 ms 55660 KB Output is correct
34 Correct 41 ms 55532 KB Output is correct
35 Correct 369 ms 73912 KB Output is correct
36 Correct 374 ms 74128 KB Output is correct
37 Correct 389 ms 77164 KB Output is correct
38 Correct 427 ms 77164 KB Output is correct
39 Correct 348 ms 73836 KB Output is correct
40 Correct 182 ms 67564 KB Output is correct
41 Correct 830 ms 82560 KB Output is correct
42 Correct 213 ms 68196 KB Output is correct
43 Correct 222 ms 66412 KB Output is correct
44 Correct 512 ms 76524 KB Output is correct
45 Correct 695 ms 79620 KB Output is correct
46 Correct 804 ms 83052 KB Output is correct
47 Correct 765 ms 82540 KB Output is correct
48 Correct 416 ms 77164 KB Output is correct
49 Correct 416 ms 77168 KB Output is correct
50 Correct 415 ms 80236 KB Output is correct
51 Correct 429 ms 80108 KB Output is correct
52 Correct 35 ms 55276 KB Output is correct
53 Correct 860 ms 81728 KB Output is correct
54 Correct 536 ms 75536 KB Output is correct
55 Correct 692 ms 78316 KB Output is correct
56 Correct 836 ms 81772 KB Output is correct
57 Correct 417 ms 75504 KB Output is correct
58 Correct 424 ms 75628 KB Output is correct
59 Correct 427 ms 78776 KB Output is correct
60 Correct 425 ms 78700 KB Output is correct
61 Correct 897 ms 81132 KB Output is correct
62 Correct 35 ms 55276 KB Output is correct
63 Correct 855 ms 80748 KB Output is correct
64 Correct 513 ms 74368 KB Output is correct
65 Correct 712 ms 77856 KB Output is correct
66 Correct 817 ms 80620 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 475 ms 81056 KB Output is correct
2 Correct 463 ms 81436 KB Output is correct
3 Correct 211 ms 68944 KB Output is correct
4 Correct 370 ms 76652 KB Output is correct
5 Correct 34 ms 55276 KB Output is correct
6 Correct 427 ms 78992 KB Output is correct
7 Correct 119 ms 64236 KB Output is correct
8 Correct 140 ms 64236 KB Output is correct
9 Correct 234 ms 68716 KB Output is correct
10 Correct 387 ms 81772 KB Output is correct
11 Correct 158 ms 68972 KB Output is correct
12 Correct 34 ms 55276 KB Output is correct
13 Correct 34 ms 55276 KB Output is correct
14 Correct 37 ms 55276 KB Output is correct
15 Correct 34 ms 55276 KB Output is correct
16 Correct 34 ms 55276 KB Output is correct
17 Correct 34 ms 55276 KB Output is correct
18 Correct 34 ms 55276 KB Output is correct
19 Correct 34 ms 55276 KB Output is correct
20 Correct 35 ms 55276 KB Output is correct
21 Correct 35 ms 55276 KB Output is correct
22 Correct 35 ms 55296 KB Output is correct
23 Correct 36 ms 55276 KB Output is correct
24 Correct 35 ms 55276 KB Output is correct
25 Correct 34 ms 55276 KB Output is correct
26 Correct 34 ms 55276 KB Output is correct
27 Correct 34 ms 55276 KB Output is correct
28 Correct 37 ms 55532 KB Output is correct
29 Correct 38 ms 55532 KB Output is correct
30 Correct 40 ms 55660 KB Output is correct
31 Correct 38 ms 55532 KB Output is correct
32 Correct 40 ms 55532 KB Output is correct
33 Correct 40 ms 55660 KB Output is correct
34 Correct 41 ms 55532 KB Output is correct
35 Correct 369 ms 73912 KB Output is correct
36 Correct 374 ms 74128 KB Output is correct
37 Correct 389 ms 77164 KB Output is correct
38 Correct 427 ms 77164 KB Output is correct
39 Correct 348 ms 73836 KB Output is correct
40 Correct 182 ms 67564 KB Output is correct
41 Correct 830 ms 82560 KB Output is correct
42 Correct 213 ms 68196 KB Output is correct
43 Correct 222 ms 66412 KB Output is correct
44 Correct 512 ms 76524 KB Output is correct
45 Correct 695 ms 79620 KB Output is correct
46 Correct 804 ms 83052 KB Output is correct
47 Correct 765 ms 82540 KB Output is correct
48 Correct 416 ms 77164 KB Output is correct
49 Correct 416 ms 77168 KB Output is correct
50 Correct 415 ms 80236 KB Output is correct
51 Correct 429 ms 80108 KB Output is correct
52 Correct 35 ms 55276 KB Output is correct
53 Correct 860 ms 81728 KB Output is correct
54 Correct 536 ms 75536 KB Output is correct
55 Correct 692 ms 78316 KB Output is correct
56 Correct 836 ms 81772 KB Output is correct
57 Correct 1966 ms 152256 KB Output is correct
58 Correct 1970 ms 151848 KB Output is correct
59 Correct 1955 ms 167728 KB Output is correct
60 Correct 1924 ms 167784 KB Output is correct
61 Correct 5100 ms 178560 KB Output is correct
62 Correct 2802 ms 145692 KB Output is correct
63 Correct 3506 ms 155096 KB Output is correct
64 Correct 4720 ms 176192 KB Output is correct
65 Correct 417 ms 75504 KB Output is correct
66 Correct 424 ms 75628 KB Output is correct
67 Correct 427 ms 78776 KB Output is correct
68 Correct 425 ms 78700 KB Output is correct
69 Correct 897 ms 81132 KB Output is correct
70 Correct 35 ms 55276 KB Output is correct
71 Correct 855 ms 80748 KB Output is correct
72 Correct 513 ms 74368 KB Output is correct
73 Correct 712 ms 77856 KB Output is correct
74 Correct 817 ms 80620 KB Output is correct
75 Correct 1963 ms 151052 KB Output is correct
76 Correct 1951 ms 150892 KB Output is correct
77 Correct 1958 ms 166548 KB Output is correct
78 Correct 1953 ms 166292 KB Output is correct
79 Correct 5187 ms 177332 KB Output is correct
80 Correct 2844 ms 142852 KB Output is correct
81 Correct 3579 ms 157024 KB Output is correct
82 Correct 4946 ms 176076 KB Output is correct
83 Correct 4818 ms 172432 KB Output is correct