답안 #122647

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
122647 2019-06-28T23:53:54 Z duality Two Dishes (JOI19_dishes) C++11
100 / 100
4943 ms 103880 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 update2(int s,int e,int ai,int i,LLI num) {
    prop(s,e,i);
    if ((s > ai) || (e < ai)) return tree[i];
    else if (s == e) {
        tree[i] = num;
        return tree[i];
    }

    int mid = (s+e) / 2;
    tree[i] = max(update2(s,mid,ai,2*i+1,num),update2(mid+1,e,ai,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].i > N) || (events[i].i == 0) || (events[i].j < 0)) continue;
        LLI m = query(0,M,0,events[i].j+1,0);
        update2(0,M,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:119: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:124: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:112: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:113: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:114: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];
                              ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 616 ms 22008 KB Output is correct
2 Correct 614 ms 21404 KB Output is correct
3 Correct 294 ms 14584 KB Output is correct
4 Correct 512 ms 19440 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 560 ms 20216 KB Output is correct
7 Correct 124 ms 7544 KB Output is correct
8 Correct 120 ms 7440 KB Output is correct
9 Correct 303 ms 14428 KB Output is correct
10 Correct 610 ms 22720 KB Output is correct
11 Correct 244 ms 14556 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 380 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 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
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 380 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 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 5 ms 504 KB Output is correct
18 Correct 5 ms 632 KB Output is correct
19 Correct 6 ms 632 KB Output is correct
20 Correct 5 ms 636 KB Output is correct
21 Correct 6 ms 632 KB Output is correct
22 Correct 6 ms 632 KB Output is correct
23 Correct 6 ms 632 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 380 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 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 5 ms 504 KB Output is correct
18 Correct 5 ms 632 KB Output is correct
19 Correct 6 ms 632 KB Output is correct
20 Correct 5 ms 636 KB Output is correct
21 Correct 6 ms 632 KB Output is correct
22 Correct 6 ms 632 KB Output is correct
23 Correct 6 ms 632 KB Output is correct
24 Correct 500 ms 14600 KB Output is correct
25 Correct 459 ms 22780 KB Output is correct
26 Correct 435 ms 22904 KB Output is correct
27 Correct 486 ms 22736 KB Output is correct
28 Correct 410 ms 22924 KB Output is correct
29 Correct 264 ms 14584 KB Output is correct
30 Correct 771 ms 22776 KB Output is correct
31 Correct 224 ms 15736 KB Output is correct
32 Correct 129 ms 7416 KB Output is correct
33 Correct 533 ms 22648 KB Output is correct
34 Correct 694 ms 22392 KB Output is correct
35 Correct 771 ms 22904 KB Output is correct
36 Correct 753 ms 22648 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 380 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 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 5 ms 504 KB Output is correct
18 Correct 5 ms 632 KB Output is correct
19 Correct 6 ms 632 KB Output is correct
20 Correct 5 ms 636 KB Output is correct
21 Correct 6 ms 632 KB Output is correct
22 Correct 6 ms 632 KB Output is correct
23 Correct 6 ms 632 KB Output is correct
24 Correct 500 ms 14600 KB Output is correct
25 Correct 459 ms 22780 KB Output is correct
26 Correct 435 ms 22904 KB Output is correct
27 Correct 486 ms 22736 KB Output is correct
28 Correct 410 ms 22924 KB Output is correct
29 Correct 264 ms 14584 KB Output is correct
30 Correct 771 ms 22776 KB Output is correct
31 Correct 224 ms 15736 KB Output is correct
32 Correct 129 ms 7416 KB Output is correct
33 Correct 533 ms 22648 KB Output is correct
34 Correct 694 ms 22392 KB Output is correct
35 Correct 771 ms 22904 KB Output is correct
36 Correct 753 ms 22648 KB Output is correct
37 Correct 492 ms 22660 KB Output is correct
38 Correct 528 ms 22776 KB Output is correct
39 Correct 660 ms 22648 KB Output is correct
40 Correct 654 ms 22820 KB Output is correct
41 Correct 2 ms 376 KB Output is correct
42 Correct 804 ms 22904 KB Output is correct
43 Correct 536 ms 22520 KB Output is correct
44 Correct 670 ms 22392 KB Output is correct
45 Correct 738 ms 22828 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 380 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 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 5 ms 504 KB Output is correct
18 Correct 5 ms 632 KB Output is correct
19 Correct 6 ms 632 KB Output is correct
20 Correct 5 ms 636 KB Output is correct
21 Correct 6 ms 632 KB Output is correct
22 Correct 6 ms 632 KB Output is correct
23 Correct 6 ms 632 KB Output is correct
24 Correct 500 ms 14600 KB Output is correct
25 Correct 459 ms 22780 KB Output is correct
26 Correct 435 ms 22904 KB Output is correct
27 Correct 486 ms 22736 KB Output is correct
28 Correct 410 ms 22924 KB Output is correct
29 Correct 264 ms 14584 KB Output is correct
30 Correct 771 ms 22776 KB Output is correct
31 Correct 224 ms 15736 KB Output is correct
32 Correct 129 ms 7416 KB Output is correct
33 Correct 533 ms 22648 KB Output is correct
34 Correct 694 ms 22392 KB Output is correct
35 Correct 771 ms 22904 KB Output is correct
36 Correct 753 ms 22648 KB Output is correct
37 Correct 492 ms 22660 KB Output is correct
38 Correct 528 ms 22776 KB Output is correct
39 Correct 660 ms 22648 KB Output is correct
40 Correct 654 ms 22820 KB Output is correct
41 Correct 2 ms 376 KB Output is correct
42 Correct 804 ms 22904 KB Output is correct
43 Correct 536 ms 22520 KB Output is correct
44 Correct 670 ms 22392 KB Output is correct
45 Correct 738 ms 22828 KB Output is correct
46 Correct 2707 ms 103672 KB Output is correct
47 Correct 2844 ms 103648 KB Output is correct
48 Correct 3650 ms 103848 KB Output is correct
49 Correct 3588 ms 103820 KB Output is correct
50 Correct 4895 ms 103708 KB Output is correct
51 Correct 3168 ms 101288 KB Output is correct
52 Correct 3782 ms 99808 KB Output is correct
53 Correct 4379 ms 103800 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 616 ms 22008 KB Output is correct
2 Correct 614 ms 21404 KB Output is correct
3 Correct 294 ms 14584 KB Output is correct
4 Correct 512 ms 19440 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 560 ms 20216 KB Output is correct
7 Correct 124 ms 7544 KB Output is correct
8 Correct 120 ms 7440 KB Output is correct
9 Correct 303 ms 14428 KB Output is correct
10 Correct 610 ms 22720 KB Output is correct
11 Correct 244 ms 14556 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 380 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 376 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 5 ms 504 KB Output is correct
29 Correct 5 ms 632 KB Output is correct
30 Correct 6 ms 632 KB Output is correct
31 Correct 5 ms 636 KB Output is correct
32 Correct 6 ms 632 KB Output is correct
33 Correct 6 ms 632 KB Output is correct
34 Correct 6 ms 632 KB Output is correct
35 Correct 500 ms 14600 KB Output is correct
36 Correct 459 ms 22780 KB Output is correct
37 Correct 435 ms 22904 KB Output is correct
38 Correct 486 ms 22736 KB Output is correct
39 Correct 410 ms 22924 KB Output is correct
40 Correct 264 ms 14584 KB Output is correct
41 Correct 771 ms 22776 KB Output is correct
42 Correct 224 ms 15736 KB Output is correct
43 Correct 129 ms 7416 KB Output is correct
44 Correct 533 ms 22648 KB Output is correct
45 Correct 694 ms 22392 KB Output is correct
46 Correct 771 ms 22904 KB Output is correct
47 Correct 753 ms 22648 KB Output is correct
48 Correct 492 ms 22660 KB Output is correct
49 Correct 528 ms 22776 KB Output is correct
50 Correct 660 ms 22648 KB Output is correct
51 Correct 654 ms 22820 KB Output is correct
52 Correct 2 ms 376 KB Output is correct
53 Correct 804 ms 22904 KB Output is correct
54 Correct 536 ms 22520 KB Output is correct
55 Correct 670 ms 22392 KB Output is correct
56 Correct 738 ms 22828 KB Output is correct
57 Correct 514 ms 22688 KB Output is correct
58 Correct 520 ms 22676 KB Output is correct
59 Correct 669 ms 22776 KB Output is correct
60 Correct 677 ms 22816 KB Output is correct
61 Correct 778 ms 22776 KB Output is correct
62 Correct 2 ms 376 KB Output is correct
63 Correct 807 ms 22812 KB Output is correct
64 Correct 596 ms 22648 KB Output is correct
65 Correct 687 ms 22380 KB Output is correct
66 Correct 711 ms 22776 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 616 ms 22008 KB Output is correct
2 Correct 614 ms 21404 KB Output is correct
3 Correct 294 ms 14584 KB Output is correct
4 Correct 512 ms 19440 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 560 ms 20216 KB Output is correct
7 Correct 124 ms 7544 KB Output is correct
8 Correct 120 ms 7440 KB Output is correct
9 Correct 303 ms 14428 KB Output is correct
10 Correct 610 ms 22720 KB Output is correct
11 Correct 244 ms 14556 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 380 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 376 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 5 ms 504 KB Output is correct
29 Correct 5 ms 632 KB Output is correct
30 Correct 6 ms 632 KB Output is correct
31 Correct 5 ms 636 KB Output is correct
32 Correct 6 ms 632 KB Output is correct
33 Correct 6 ms 632 KB Output is correct
34 Correct 6 ms 632 KB Output is correct
35 Correct 500 ms 14600 KB Output is correct
36 Correct 459 ms 22780 KB Output is correct
37 Correct 435 ms 22904 KB Output is correct
38 Correct 486 ms 22736 KB Output is correct
39 Correct 410 ms 22924 KB Output is correct
40 Correct 264 ms 14584 KB Output is correct
41 Correct 771 ms 22776 KB Output is correct
42 Correct 224 ms 15736 KB Output is correct
43 Correct 129 ms 7416 KB Output is correct
44 Correct 533 ms 22648 KB Output is correct
45 Correct 694 ms 22392 KB Output is correct
46 Correct 771 ms 22904 KB Output is correct
47 Correct 753 ms 22648 KB Output is correct
48 Correct 492 ms 22660 KB Output is correct
49 Correct 528 ms 22776 KB Output is correct
50 Correct 660 ms 22648 KB Output is correct
51 Correct 654 ms 22820 KB Output is correct
52 Correct 2 ms 376 KB Output is correct
53 Correct 804 ms 22904 KB Output is correct
54 Correct 536 ms 22520 KB Output is correct
55 Correct 670 ms 22392 KB Output is correct
56 Correct 738 ms 22828 KB Output is correct
57 Correct 2707 ms 103672 KB Output is correct
58 Correct 2844 ms 103648 KB Output is correct
59 Correct 3650 ms 103848 KB Output is correct
60 Correct 3588 ms 103820 KB Output is correct
61 Correct 4895 ms 103708 KB Output is correct
62 Correct 3168 ms 101288 KB Output is correct
63 Correct 3782 ms 99808 KB Output is correct
64 Correct 4379 ms 103800 KB Output is correct
65 Correct 514 ms 22688 KB Output is correct
66 Correct 520 ms 22676 KB Output is correct
67 Correct 669 ms 22776 KB Output is correct
68 Correct 677 ms 22816 KB Output is correct
69 Correct 778 ms 22776 KB Output is correct
70 Correct 2 ms 376 KB Output is correct
71 Correct 807 ms 22812 KB Output is correct
72 Correct 596 ms 22648 KB Output is correct
73 Correct 687 ms 22380 KB Output is correct
74 Correct 711 ms 22776 KB Output is correct
75 Correct 2671 ms 103732 KB Output is correct
76 Correct 2814 ms 103880 KB Output is correct
77 Correct 3641 ms 103680 KB Output is correct
78 Correct 3647 ms 103748 KB Output is correct
79 Correct 4943 ms 103652 KB Output is correct
80 Correct 3049 ms 101484 KB Output is correct
81 Correct 3860 ms 100016 KB Output is correct
82 Correct 4622 ms 103696 KB Output is correct
83 Correct 4590 ms 103664 KB Output is correct