oj.uz

Submission #375821

# Submission time Handle Problem Language Result Execution time Memory
375821 2021-03-10T03:12:09 Z jainbot27 Two Dishes (JOI19_dishes) C++17
100 / 100
 6968 ms 250864 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define f first
#define s second
#define pb push_back
#define ar array
#define all(x) x.begin(), x.end()
#define siz(x) (int)x.size()
 
#define FOR(x, y, z) for(int x = (y); x < (z); x++)
#define ROF(x, z, y) for(int x = (y-1); x >= (z); x--)
#define F0R(x, z) FOR(x, 0, z)
#define R0F(x, z) ROF(x, 0, z)
#define trav(x, y) for(auto&x:y)
 
using ll = long long;
using vi = vector<int>;
using vl = vector<long long>;
using pii = pair<int, int>;
using vpii = vector<pair<int, int>>;
 
template<class T> inline bool ckmin(T&a, T b) {return b < a ? a = b, 1 : 0;}
template<class T> inline bool ckmax(T&a, T b) {return b > a ? a = b, 1 : 0;}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
const char nl = '\n';
const int mxN = 1e6+10;
const int MOD = 1e9 + 7;
const long long infLL = 1e18;
 
//use to make shit go faster (magic from KACTL)
static char buf[450 << 20];
void* operator new(size_t s) {
    static size_t i = sizeof buf;
    assert(s < i);
    return (void*)&buf[i -= s];
}
void operator delete(void*) {}
// implicit lazy segment tree adapted from KACTL
template<class V> struct Node {
    Node *l = 0, *r = 0;
    const V no_op = infLL;
    int lo, hi; V madd = 0, val = 0;
    Node(int lo,int hi):lo(lo),hi(hi){} 
    Node(vector<V>& v, int lo, int hi) : lo(lo), hi(hi) {
        if (lo + 1 < hi) {
            int mid = lo + (hi - lo)/2;
            l = new Node(v, lo, mid); r = new Node(v, mid, hi);
            val = l->val+r->val;
        }
        else val = v[lo];
    }
    V query(int L, int R) {
        if (R <= lo || hi <= L) return -infLL;
        if (L <= lo && hi <= R) return val;
        push();
        return max(l->query(L, R), r->query(L, R));
    }
    void mx(int L, V x) {
        if(lo==hi-1) {
            ckmax(val, x);
        }
        else{
            push();
            int m = (lo+hi)/2; if(L<m) l->mx(L, x);
            else r->mx(L, x);
            val = max(l->val, r->val);
        }
    }
    void add(int L, int R, V x) {
        if (R <= lo || hi <= L) return;
        if (L <= lo && hi <= R) {
            madd += x;
            val += x;
        }
        else {
            push(), l->add(L, R, x), r->add(L, R, x);
            val = max(l->val, r->val);
        }
    }
    void push() {
        if (!l) {
            int mid = lo + (hi - lo)/2;
            l = new Node(lo, mid); r = new Node(mid, hi);
        }
        if(madd) l->add(lo,hi,madd), r->add(lo,hi,madd), madd = 0;
    }
};
 
Node<ll>* st = new Node<ll>(0, mxN);
pair<int, pair<ll, ll>> a[mxN], b[mxN];
ll pa[mxN], pb[mxN];
ll ans;
map<pii, ll> mp;
int n, m;
 
int32_t main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    FOR(i, 1, n+1){
        cin >> a[i].f >> a[i].s.f >> a[i].s.s;
        pa[i] = pa[i-1]+a[i].f;
    }
    FOR(i, 1, m+1){
        cin >> b[i].f >> b[i].s.f >> b[i].s.s;
        pb[i] = pb[i-1]+b[i].f;
    }
    FOR(i, 1, n+1){
        if(pa[i]>a[i].s.f) continue;
        if(pb[m]+pa[i]<=a[i].s.f) {
            ans += a[i].s.s ;
            continue;
        }
        mp[{i-1, -(upper_bound(pb+1, pb+1+m, a[i].s.f-pa[i])-pb-1+1)}] += a[i].s.s;
    } 
    FOR(i, 1, m+1){
        if(pb[i]>b[i].s.f) continue;
        if(pb[i]+pa[n]<=b[i].s.f) {
            ans += b[i].s.s;
            continue;
        }
        ans += b[i].s.s;
        mp[{upper_bound(pa+1, pa+n+1, b[i].s.f-pb[i])-pa-1, -i}] -= b[i].s.s;
 
    }
    trav(cur, mp){
        int x = cur.f.f, y = -cur.f.s, z = cur.s;
        ll t = st->query(0, y);
        st->mx(y, t);
        st->add(0, y, z);
    }
    cout << st->query(0, mxN)+ans << nl;
    return 0;
}

Compilation message

dishes.cpp: In function 'int32_t main()':
dishes.cpp:128:13: warning: unused variable 'x' [-Wunused-variable]
  128 |         int x = cur.f.f, y = -cur.f.s, z = cur.s;
      |             ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 423 ms 41376 KB Output is correct
2 Correct 419 ms 39916 KB Output is correct
3 Correct 168 ms 13036 KB Output is correct
4 Correct 312 ms 30256 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 367 ms 34888 KB Output is correct
7 Correct 84 ms 6764 KB Output is correct
8 Correct 94 ms 6764 KB Output is correct
9 Correct 168 ms 13036 KB Output is correct
10 Correct 362 ms 41324 KB Output is correct
11 Correct 122 ms 13036 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 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 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 364 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 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 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 364 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 876 KB Output is correct
20 Correct 4 ms 876 KB Output is correct
21 Correct 5 ms 876 KB Output is correct
22 Correct 6 ms 876 KB Output is correct
23 Correct 6 ms 876 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 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 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 364 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 876 KB Output is correct
20 Correct 4 ms 876 KB Output is correct
21 Correct 5 ms 876 KB Output is correct
22 Correct 6 ms 876 KB Output is correct
23 Correct 6 ms 876 KB Output is correct
24 Correct 295 ms 22764 KB Output is correct
25 Correct 351 ms 50668 KB Output is correct
26 Correct 349 ms 50668 KB Output is correct
27 Correct 346 ms 50628 KB Output is correct
28 Correct 361 ms 42248 KB Output is correct
29 Correct 148 ms 22636 KB Output is correct
30 Correct 1008 ms 59576 KB Output is correct
31 Correct 172 ms 32748 KB Output is correct
32 Correct 148 ms 16620 KB Output is correct
33 Correct 592 ms 49364 KB Output is correct
34 Correct 776 ms 54764 KB Output is correct
35 Correct 952 ms 54380 KB Output is correct
36 Correct 919 ms 53796 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 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 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 364 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 876 KB Output is correct
20 Correct 4 ms 876 KB Output is correct
21 Correct 5 ms 876 KB Output is correct
22 Correct 6 ms 876 KB Output is correct
23 Correct 6 ms 876 KB Output is correct
24 Correct 295 ms 22764 KB Output is correct
25 Correct 351 ms 50668 KB Output is correct
26 Correct 349 ms 50668 KB Output is correct
27 Correct 346 ms 50628 KB Output is correct
28 Correct 361 ms 42248 KB Output is correct
29 Correct 148 ms 22636 KB Output is correct
30 Correct 1008 ms 59576 KB Output is correct
31 Correct 172 ms 32748 KB Output is correct
32 Correct 148 ms 16620 KB Output is correct
33 Correct 592 ms 49364 KB Output is correct
34 Correct 776 ms 54764 KB Output is correct
35 Correct 952 ms 54380 KB Output is correct
36 Correct 919 ms 53796 KB Output is correct
37 Correct 381 ms 48880 KB Output is correct
38 Correct 376 ms 48748 KB Output is correct
39 Correct 390 ms 50668 KB Output is correct
40 Correct 395 ms 50924 KB Output is correct
41 Correct 1 ms 364 KB Output is correct
42 Correct 1033 ms 57484 KB Output is correct
43 Correct 581 ms 47468 KB Output is correct
44 Correct 785 ms 52460 KB Output is correct
45 Correct 987 ms 57452 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 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 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 364 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 876 KB Output is correct
20 Correct 4 ms 876 KB Output is correct
21 Correct 5 ms 876 KB Output is correct
22 Correct 6 ms 876 KB Output is correct
23 Correct 6 ms 876 KB Output is correct
24 Correct 295 ms 22764 KB Output is correct
25 Correct 351 ms 50668 KB Output is correct
26 Correct 349 ms 50668 KB Output is correct
27 Correct 346 ms 50628 KB Output is correct
28 Correct 361 ms 42248 KB Output is correct
29 Correct 148 ms 22636 KB Output is correct
30 Correct 1008 ms 59576 KB Output is correct
31 Correct 172 ms 32748 KB Output is correct
32 Correct 148 ms 16620 KB Output is correct
33 Correct 592 ms 49364 KB Output is correct
34 Correct 776 ms 54764 KB Output is correct
35 Correct 952 ms 54380 KB Output is correct
36 Correct 919 ms 53796 KB Output is correct
37 Correct 381 ms 48880 KB Output is correct
38 Correct 376 ms 48748 KB Output is correct
39 Correct 390 ms 50668 KB Output is correct
40 Correct 395 ms 50924 KB Output is correct
41 Correct 1 ms 364 KB Output is correct
42 Correct 1033 ms 57484 KB Output is correct
43 Correct 581 ms 47468 KB Output is correct
44 Correct 785 ms 52460 KB Output is correct
45 Correct 987 ms 57452 KB Output is correct
46 Correct 1891 ms 205876 KB Output is correct
47 Correct 1901 ms 205676 KB Output is correct
48 Correct 1975 ms 205240 KB Output is correct
49 Correct 2004 ms 205432 KB Output is correct
50 Correct 6968 ms 250864 KB Output is correct
51 Correct 3674 ms 194872 KB Output is correct
52 Correct 4662 ms 207860 KB Output is correct
53 Correct 6597 ms 246532 KB Output is correct

Subtask #7
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 423 ms 41376 KB Output is correct
2 Correct 419 ms 39916 KB Output is correct
3 Correct 168 ms 13036 KB Output is correct
4 Correct 312 ms 30256 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 367 ms 34888 KB Output is correct
7 Correct 84 ms 6764 KB Output is correct
8 Correct 94 ms 6764 KB Output is correct
9 Correct 168 ms 13036 KB Output is correct
10 Correct 362 ms 41324 KB Output is correct
11 Correct 122 ms 13036 KB Output is correct
12 Correct 1 ms 364 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 364 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 1 ms 364 KB Output is correct
18 Correct 1 ms 364 KB Output is correct
19 Correct 1 ms 364 KB Output is correct
20 Correct 1 ms 364 KB Output is correct
21 Correct 1 ms 364 KB Output is correct
22 Correct 1 ms 364 KB Output is correct
23 Correct 1 ms 364 KB Output is correct
24 Correct 1 ms 384 KB Output is correct
25 Correct 1 ms 364 KB Output is correct
26 Correct 1 ms 364 KB Output is correct
27 Correct 1 ms 364 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 876 KB Output is correct
31 Correct 4 ms 876 KB Output is correct
32 Correct 5 ms 876 KB Output is correct
33 Correct 6 ms 876 KB Output is correct
34 Correct 6 ms 876 KB Output is correct
35 Correct 295 ms 22764 KB Output is correct
36 Correct 351 ms 50668 KB Output is correct
37 Correct 349 ms 50668 KB Output is correct
38 Correct 346 ms 50628 KB Output is correct
39 Correct 361 ms 42248 KB Output is correct
40 Correct 148 ms 22636 KB Output is correct
41 Correct 1008 ms 59576 KB Output is correct
42 Correct 172 ms 32748 KB Output is correct
43 Correct 148 ms 16620 KB Output is correct
44 Correct 592 ms 49364 KB Output is correct
45 Correct 776 ms 54764 KB Output is correct
46 Correct 952 ms 54380 KB Output is correct
47 Correct 919 ms 53796 KB Output is correct
48 Correct 381 ms 48880 KB Output is correct
49 Correct 376 ms 48748 KB Output is correct
50 Correct 390 ms 50668 KB Output is correct
51 Correct 395 ms 50924 KB Output is correct
52 Correct 1 ms 364 KB Output is correct
53 Correct 1033 ms 57484 KB Output is correct
54 Correct 581 ms 47468 KB Output is correct
55 Correct 785 ms 52460 KB Output is correct
56 Correct 987 ms 57452 KB Output is correct
57 Correct 379 ms 46700 KB Output is correct
58 Correct 384 ms 46572 KB Output is correct
59 Correct 401 ms 47980 KB Output is correct
60 Correct 414 ms 47916 KB Output is correct
61 Correct 1063 ms 58276 KB Output is correct
62 Correct 1 ms 364 KB Output is correct
63 Correct 1029 ms 55404 KB Output is correct
64 Correct 597 ms 44524 KB Output is correct
65 Correct 771 ms 51052 KB Output is correct
66 Correct 972 ms 56940 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 423 ms 41376 KB Output is correct
2 Correct 419 ms 39916 KB Output is correct
3 Correct 168 ms 13036 KB Output is correct
4 Correct 312 ms 30256 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 367 ms 34888 KB Output is correct
7 Correct 84 ms 6764 KB Output is correct
8 Correct 94 ms 6764 KB Output is correct
9 Correct 168 ms 13036 KB Output is correct
10 Correct 362 ms 41324 KB Output is correct
11 Correct 122 ms 13036 KB Output is correct
12 Correct 1 ms 364 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 364 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 1 ms 364 KB Output is correct
18 Correct 1 ms 364 KB Output is correct
19 Correct 1 ms 364 KB Output is correct
20 Correct 1 ms 364 KB Output is correct
21 Correct 1 ms 364 KB Output is correct
22 Correct 1 ms 364 KB Output is correct
23 Correct 1 ms 364 KB Output is correct
24 Correct 1 ms 384 KB Output is correct
25 Correct 1 ms 364 KB Output is correct
26 Correct 1 ms 364 KB Output is correct
27 Correct 1 ms 364 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 876 KB Output is correct
31 Correct 4 ms 876 KB Output is correct
32 Correct 5 ms 876 KB Output is correct
33 Correct 6 ms 876 KB Output is correct
34 Correct 6 ms 876 KB Output is correct
35 Correct 295 ms 22764 KB Output is correct
36 Correct 351 ms 50668 KB Output is correct
37 Correct 349 ms 50668 KB Output is correct
38 Correct 346 ms 50628 KB Output is correct
39 Correct 361 ms 42248 KB Output is correct
40 Correct 148 ms 22636 KB Output is correct
41 Correct 1008 ms 59576 KB Output is correct
42 Correct 172 ms 32748 KB Output is correct
43 Correct 148 ms 16620 KB Output is correct
44 Correct 592 ms 49364 KB Output is correct
45 Correct 776 ms 54764 KB Output is correct
46 Correct 952 ms 54380 KB Output is correct
47 Correct 919 ms 53796 KB Output is correct
48 Correct 381 ms 48880 KB Output is correct
49 Correct 376 ms 48748 KB Output is correct
50 Correct 390 ms 50668 KB Output is correct
51 Correct 395 ms 50924 KB Output is correct
52 Correct 1 ms 364 KB Output is correct
53 Correct 1033 ms 57484 KB Output is correct
54 Correct 581 ms 47468 KB Output is correct
55 Correct 785 ms 52460 KB Output is correct
56 Correct 987 ms 57452 KB Output is correct
57 Correct 1891 ms 205876 KB Output is correct
58 Correct 1901 ms 205676 KB Output is correct
59 Correct 1975 ms 205240 KB Output is correct
60 Correct 2004 ms 205432 KB Output is correct
61 Correct 6968 ms 250864 KB Output is correct
62 Correct 3674 ms 194872 KB Output is correct
63 Correct 4662 ms 207860 KB Output is correct
64 Correct 6597 ms 246532 KB Output is correct
65 Correct 379 ms 46700 KB Output is correct
66 Correct 384 ms 46572 KB Output is correct
67 Correct 401 ms 47980 KB Output is correct
68 Correct 414 ms 47916 KB Output is correct
69 Correct 1063 ms 58276 KB Output is correct
70 Correct 1 ms 364 KB Output is correct
71 Correct 1029 ms 55404 KB Output is correct
72 Correct 597 ms 44524 KB Output is correct
73 Correct 771 ms 51052 KB Output is correct
74 Correct 972 ms 56940 KB Output is correct
75 Correct 1942 ms 205572 KB Output is correct
76 Correct 1923 ms 205612 KB Output is correct
77 Correct 2065 ms 205224 KB Output is correct
78 Correct 1989 ms 205292 KB Output is correct
79 Correct 6786 ms 250380 KB Output is correct
80 Correct 3474 ms 188940 KB Output is correct
81 Correct 4678 ms 216832 KB Output is correct
82 Correct 6407 ms 248300 KB Output is correct
83 Correct 6559 ms 242624 KB Output is correct