oj.uz

Submission #122646

# Submission time Handle Problem Language Result Execution time Memory
122646 2019-06-28T23:48:41 Z duality Two Dishes (JOI19_dishes) C++11
100 / 100
 6187 ms 175544 KB 
#define DEBUG 0

#include <bits/stdc++.h>
using namespace std;

#if DEBUG
// basic debugging macros
int __i__,__j__;
#define printLine(l) for(__i__=0;__i__<l;__i__++){cout<<"-";}cout<<endl
#define printLine2(l,c) for(__i__=0;__i__<l;__i__++){cout<<c;}cout<<endl
#define printVar(n) cout<<#n<<": "<<n<<endl
#define printArr(a,l) cout<<#a<<": ";for(__i__=0;__i__<l;__i__++){cout<<a[__i__]<<" ";}cout<<endl
#define print2dArr(a,r,c) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<a[__i__][__j__]<<" ";}cout<<endl;}
#define print2dArr2(a,r,c,l) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<setw(l)<<setfill(' ')<<a[__i__][__j__]<<" ";}cout<<endl;}

// advanced debugging class
// debug 1,2,'A',"test";
class _Debug {
    public:
        template<typename T>
        _Debug& operator,(T val) {
            cout << val << endl;
            return *this;
        }
};
#define debug _Debug(),
#else
#define printLine(l)
#define printLine2(l,c)
#define printVar(n)
#define printArr(a,l)
#define print2dArr(a,r,c)
#define print2dArr2(a,r,c,l)
#define debug
#endif

// define
#define MAX_VAL 999999999
#define MAX_VAL_2 999999999999999999LL
#define EPS 1e-6
#define mp make_pair
#define pb push_back

// typedef
typedef unsigned int UI;
typedef long long int LLI;
typedef unsigned long long int ULLI;
typedef unsigned short int US;
typedef pair<int,int> pii;
typedef pair<LLI,LLI> plli;
typedef vector<int> vi;
typedef vector<LLI> vlli;
typedef vector<pii> vpii;
typedef vector<plli> vplli;

// ---------- END OF TEMPLATE ----------

LLI A[1000001],S[1000001],P[1000001];
LLI B[1000001],T[1000001],Q[1000001];
LLI tree[1 << 21],lazy[1 << 21];
int prop(int s,int e,int i) {
    tree[i] += lazy[i];
    if (s != e) lazy[2*i+1] += lazy[i],lazy[2*i+2] += lazy[i];
    lazy[i] = 0;
    return 0;
}
LLI update(int s,int e,int as,int ae,int i,LLI num) {
    prop(s,e,i);
    if ((s > ae) || (e < as)) return tree[i];
    else if ((s >= as) && (e <= ae)) {
        lazy[i] += num;
        prop(s,e,i);
        return tree[i];
    }

    int mid = (s+e) / 2;
    tree[i] = max(update(s,mid,as,ae,2*i+1,num),update(mid+1,e,as,ae,2*i+2,num));
    return tree[i];
}
LLI query(int s,int e,int qs,int qe,int i) {
    prop(s,e,i);
    if ((s > qe) || (e < qs)) return -1e18;
    else if ((s >= qs) && (e <= qe)) return tree[i];

    int mid = (s+e) / 2;
    return max(query(s,mid,qs,qe,2*i+1),query(mid+1,e,qs,qe,2*i+2));
}
struct event { int i,j,x; };
bool comp(event a,event b) {
    if (a.i == b.i) {
        if (a.j == b.j) return a.x < b.x;
        else return a.j > b.j;
    }
    else return a.i < b.i;
}
event events[2000000];
int main() {
    int i;
    int N,M;
    scanf("%d %d",&N,&M);
    for (i = 1; i <= N; i++) scanf("%lld %lld %lld",&A[i],&S[i],&P[i]),A[i] += A[i-1];
    for (i = 1; i <= M; i++) scanf("%lld %lld %lld",&B[i],&T[i],&Q[i]),B[i] += B[i-1];

    LLI ans = 0;
    for (i = 1; i <= N; i++) {
        int p = upper_bound(B,B+M+1,S[i]-A[i])-B-1;
        events[i-1] = {i,p,P[i]};
    }
    for (i = 1; i <= M; i++) {
        int p = upper_bound(A,A+N+1,T[i]-B[i])-A-1;
        if (p >= 0) ans += Q[i];
        events[i+N-1] = {p+1,i-1,-Q[i]};
    }
    sort(events,events+N+M,comp);
    for (i = 0; i < N+M; i++) {
        if ((events[i].j < 0) || (events[i].i > N) || (events[i].i == 0)) continue;
        LLI m = query(0,M,0,events[i].j+1,0)-query(0,M,events[i].j+1,events[i].j+1,0);
        update(0,M,events[i].j+1,events[i].j+1,0,m),update(0,M,0,events[i].j,0,events[i].x);
    }
    ans += query(0,M,0,M,0);
    printf("%lld\n",ans);

    return 0;
}

Compilation message

dishes.cpp: In function 'int main()':
dishes.cpp:107:31: warning: narrowing conversion of 'P[i]' from 'LLI {aka long long int}' to 'int' inside { } [-Wnarrowing]
         events[i-1] = {i,p,P[i]};
                            ~~~^
dishes.cpp:112:34: warning: narrowing conversion of '- Q[i]' from 'LLI {aka long long int}' to 'int' inside { } [-Wnarrowing]
         events[i+N-1] = {p+1,i-1,-Q[i]};
                                  ^~~~~
dishes.cpp:100:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&N,&M);
     ~~~~~^~~~~~~~~~~~~~~
dishes.cpp:101:71: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for (i = 1; i <= N; i++) scanf("%lld %lld %lld",&A[i],&S[i],&P[i]),A[i] += A[i-1];
                              ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~
dishes.cpp:102:71: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for (i = 1; i <= M; i++) scanf("%lld %lld %lld",&B[i],&T[i],&Q[i]),B[i] += B[i-1];
                              ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 736 ms 35576 KB Output is correct
2 Correct 728 ms 35320 KB Output is correct
3 Correct 304 ms 27768 KB Output is correct
4 Correct 600 ms 33148 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 638 ms 33572 KB Output is correct
7 Correct 124 ms 14456 KB Output is correct
8 Correct 122 ms 14488 KB Output is correct
9 Correct 309 ms 28792 KB Output is correct
10 Correct 746 ms 30072 KB Output is correct
11 Correct 248 ms 22264 KB Output is correct

Subtask #2
3.0 / 3.0

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

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 400 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 6 ms 632 KB Output is correct
18 Correct 6 ms 632 KB Output is correct
19 Correct 8 ms 736 KB Output is correct
20 Correct 6 ms 760 KB Output is correct
21 Correct 7 ms 760 KB Output is correct
22 Correct 7 ms 632 KB Output is correct
23 Correct 7 ms 632 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 400 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 6 ms 632 KB Output is correct
18 Correct 6 ms 632 KB Output is correct
19 Correct 8 ms 736 KB Output is correct
20 Correct 6 ms 760 KB Output is correct
21 Correct 7 ms 760 KB Output is correct
22 Correct 7 ms 632 KB Output is correct
23 Correct 7 ms 632 KB Output is correct
24 Correct 565 ms 25080 KB Output is correct
25 Correct 540 ms 33272 KB Output is correct
26 Correct 509 ms 33400 KB Output is correct
27 Correct 558 ms 33400 KB Output is correct
28 Correct 472 ms 33656 KB Output is correct
29 Correct 277 ms 25720 KB Output is correct
30 Correct 985 ms 33444 KB Output is correct
31 Correct 267 ms 20856 KB Output is correct
32 Correct 134 ms 12664 KB Output is correct
33 Correct 652 ms 33016 KB Output is correct
34 Correct 817 ms 33016 KB Output is correct
35 Correct 937 ms 27020 KB Output is correct
36 Correct 889 ms 27148 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 400 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 6 ms 632 KB Output is correct
18 Correct 6 ms 632 KB Output is correct
19 Correct 8 ms 736 KB Output is correct
20 Correct 6 ms 760 KB Output is correct
21 Correct 7 ms 760 KB Output is correct
22 Correct 7 ms 632 KB Output is correct
23 Correct 7 ms 632 KB Output is correct
24 Correct 565 ms 25080 KB Output is correct
25 Correct 540 ms 33272 KB Output is correct
26 Correct 509 ms 33400 KB Output is correct
27 Correct 558 ms 33400 KB Output is correct
28 Correct 472 ms 33656 KB Output is correct
29 Correct 277 ms 25720 KB Output is correct
30 Correct 985 ms 33444 KB Output is correct
31 Correct 267 ms 20856 KB Output is correct
32 Correct 134 ms 12664 KB Output is correct
33 Correct 652 ms 33016 KB Output is correct
34 Correct 817 ms 33016 KB Output is correct
35 Correct 937 ms 27020 KB Output is correct
36 Correct 889 ms 27148 KB Output is correct
37 Correct 575 ms 36344 KB Output is correct
38 Correct 615 ms 36420 KB Output is correct
39 Correct 806 ms 33804 KB Output is correct
40 Correct 811 ms 33728 KB Output is correct
41 Correct 8 ms 376 KB Output is correct
42 Correct 1025 ms 36520 KB Output is correct
43 Correct 651 ms 35908 KB Output is correct
44 Correct 847 ms 35832 KB Output is correct
45 Correct 933 ms 30084 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 400 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 6 ms 632 KB Output is correct
18 Correct 6 ms 632 KB Output is correct
19 Correct 8 ms 736 KB Output is correct
20 Correct 6 ms 760 KB Output is correct
21 Correct 7 ms 760 KB Output is correct
22 Correct 7 ms 632 KB Output is correct
23 Correct 7 ms 632 KB Output is correct
24 Correct 565 ms 25080 KB Output is correct
25 Correct 540 ms 33272 KB Output is correct
26 Correct 509 ms 33400 KB Output is correct
27 Correct 558 ms 33400 KB Output is correct
28 Correct 472 ms 33656 KB Output is correct
29 Correct 277 ms 25720 KB Output is correct
30 Correct 985 ms 33444 KB Output is correct
31 Correct 267 ms 20856 KB Output is correct
32 Correct 134 ms 12664 KB Output is correct
33 Correct 652 ms 33016 KB Output is correct
34 Correct 817 ms 33016 KB Output is correct
35 Correct 937 ms 27020 KB Output is correct
36 Correct 889 ms 27148 KB Output is correct
37 Correct 575 ms 36344 KB Output is correct
38 Correct 615 ms 36420 KB Output is correct
39 Correct 806 ms 33804 KB Output is correct
40 Correct 811 ms 33728 KB Output is correct
41 Correct 8 ms 376 KB Output is correct
42 Correct 1025 ms 36520 KB Output is correct
43 Correct 651 ms 35908 KB Output is correct
44 Correct 847 ms 35832 KB Output is correct
45 Correct 933 ms 30084 KB Output is correct
46 Correct 3177 ms 173588 KB Output is correct
47 Correct 3251 ms 173548 KB Output is correct
48 Correct 4349 ms 159964 KB Output is correct
49 Correct 4371 ms 160144 KB Output is correct
50 Correct 6158 ms 173500 KB Output is correct
51 Correct 3783 ms 168412 KB Output is correct
52 Correct 4573 ms 165716 KB Output is correct
53 Correct 6026 ms 142444 KB Output is correct

Subtask #7
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 736 ms 35576 KB Output is correct
2 Correct 728 ms 35320 KB Output is correct
3 Correct 304 ms 27768 KB Output is correct
4 Correct 600 ms 33148 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 638 ms 33572 KB Output is correct
7 Correct 124 ms 14456 KB Output is correct
8 Correct 122 ms 14488 KB Output is correct
9 Correct 309 ms 28792 KB Output is correct
10 Correct 746 ms 30072 KB Output is correct
11 Correct 248 ms 22264 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 2 ms 376 KB Output is correct
21 Correct 2 ms 376 KB Output is correct
22 Correct 2 ms 376 KB Output is correct
23 Correct 2 ms 400 KB Output is correct
24 Correct 2 ms 376 KB Output is correct
25 Correct 2 ms 376 KB Output is correct
26 Correct 2 ms 376 KB Output is correct
27 Correct 2 ms 376 KB Output is correct
28 Correct 6 ms 632 KB Output is correct
29 Correct 6 ms 632 KB Output is correct
30 Correct 8 ms 736 KB Output is correct
31 Correct 6 ms 760 KB Output is correct
32 Correct 7 ms 760 KB Output is correct
33 Correct 7 ms 632 KB Output is correct
34 Correct 7 ms 632 KB Output is correct
35 Correct 565 ms 25080 KB Output is correct
36 Correct 540 ms 33272 KB Output is correct
37 Correct 509 ms 33400 KB Output is correct
38 Correct 558 ms 33400 KB Output is correct
39 Correct 472 ms 33656 KB Output is correct
40 Correct 277 ms 25720 KB Output is correct
41 Correct 985 ms 33444 KB Output is correct
42 Correct 267 ms 20856 KB Output is correct
43 Correct 134 ms 12664 KB Output is correct
44 Correct 652 ms 33016 KB Output is correct
45 Correct 817 ms 33016 KB Output is correct
46 Correct 937 ms 27020 KB Output is correct
47 Correct 889 ms 27148 KB Output is correct
48 Correct 575 ms 36344 KB Output is correct
49 Correct 615 ms 36420 KB Output is correct
50 Correct 806 ms 33804 KB Output is correct
51 Correct 811 ms 33728 KB Output is correct
52 Correct 8 ms 376 KB Output is correct
53 Correct 1025 ms 36520 KB Output is correct
54 Correct 651 ms 35908 KB Output is correct
55 Correct 847 ms 35832 KB Output is correct
56 Correct 933 ms 30084 KB Output is correct
57 Correct 584 ms 36856 KB Output is correct
58 Correct 605 ms 36964 KB Output is correct
59 Correct 806 ms 34652 KB Output is correct
60 Correct 805 ms 34652 KB Output is correct
61 Correct 1016 ms 33528 KB Output is correct
62 Correct 2 ms 368 KB Output is correct
63 Correct 1069 ms 36824 KB Output is correct
64 Correct 669 ms 35916 KB Output is correct
65 Correct 862 ms 36088 KB Output is correct
66 Correct 926 ms 30284 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 736 ms 35576 KB Output is correct
2 Correct 728 ms 35320 KB Output is correct
3 Correct 304 ms 27768 KB Output is correct
4 Correct 600 ms 33148 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 638 ms 33572 KB Output is correct
7 Correct 124 ms 14456 KB Output is correct
8 Correct 122 ms 14488 KB Output is correct
9 Correct 309 ms 28792 KB Output is correct
10 Correct 746 ms 30072 KB Output is correct
11 Correct 248 ms 22264 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 2 ms 376 KB Output is correct
21 Correct 2 ms 376 KB Output is correct
22 Correct 2 ms 376 KB Output is correct
23 Correct 2 ms 400 KB Output is correct
24 Correct 2 ms 376 KB Output is correct
25 Correct 2 ms 376 KB Output is correct
26 Correct 2 ms 376 KB Output is correct
27 Correct 2 ms 376 KB Output is correct
28 Correct 6 ms 632 KB Output is correct
29 Correct 6 ms 632 KB Output is correct
30 Correct 8 ms 736 KB Output is correct
31 Correct 6 ms 760 KB Output is correct
32 Correct 7 ms 760 KB Output is correct
33 Correct 7 ms 632 KB Output is correct
34 Correct 7 ms 632 KB Output is correct
35 Correct 565 ms 25080 KB Output is correct
36 Correct 540 ms 33272 KB Output is correct
37 Correct 509 ms 33400 KB Output is correct
38 Correct 558 ms 33400 KB Output is correct
39 Correct 472 ms 33656 KB Output is correct
40 Correct 277 ms 25720 KB Output is correct
41 Correct 985 ms 33444 KB Output is correct
42 Correct 267 ms 20856 KB Output is correct
43 Correct 134 ms 12664 KB Output is correct
44 Correct 652 ms 33016 KB Output is correct
45 Correct 817 ms 33016 KB Output is correct
46 Correct 937 ms 27020 KB Output is correct
47 Correct 889 ms 27148 KB Output is correct
48 Correct 575 ms 36344 KB Output is correct
49 Correct 615 ms 36420 KB Output is correct
50 Correct 806 ms 33804 KB Output is correct
51 Correct 811 ms 33728 KB Output is correct
52 Correct 8 ms 376 KB Output is correct
53 Correct 1025 ms 36520 KB Output is correct
54 Correct 651 ms 35908 KB Output is correct
55 Correct 847 ms 35832 KB Output is correct
56 Correct 933 ms 30084 KB Output is correct
57 Correct 3177 ms 173588 KB Output is correct
58 Correct 3251 ms 173548 KB Output is correct
59 Correct 4349 ms 159964 KB Output is correct
60 Correct 4371 ms 160144 KB Output is correct
61 Correct 6158 ms 173500 KB Output is correct
62 Correct 3783 ms 168412 KB Output is correct
63 Correct 4573 ms 165716 KB Output is correct
64 Correct 6026 ms 142444 KB Output is correct
65 Correct 584 ms 36856 KB Output is correct
66 Correct 605 ms 36964 KB Output is correct
67 Correct 806 ms 34652 KB Output is correct
68 Correct 805 ms 34652 KB Output is correct
69 Correct 1016 ms 33528 KB Output is correct
70 Correct 2 ms 368 KB Output is correct
71 Correct 1069 ms 36824 KB Output is correct
72 Correct 669 ms 35916 KB Output is correct
73 Correct 862 ms 36088 KB Output is correct
74 Correct 926 ms 30284 KB Output is correct
75 Correct 3111 ms 175544 KB Output is correct
76 Correct 3231 ms 175348 KB Output is correct
77 Correct 4416 ms 162364 KB Output is correct
78 Correct 4395 ms 162368 KB Output is correct
79 Correct 6187 ms 174300 KB Output is correct
80 Correct 3763 ms 169036 KB Output is correct
81 Correct 4708 ms 167004 KB Output is correct
82 Correct 5769 ms 142048 KB Output is correct
83 Correct 5734 ms 162512 KB Output is correct