Submission #242843

#	Time	Username	Problem	Language	Result	Execution time	Memory
242843		mhy908	Two Dishes (JOI19_dishes)	C++14	100 / 100	5796 ms	293364 KiB

dishes

#include <bits/stdc++.h>
#define eb emplace_back
#define mp make_pair
#define F first
#define S second
#define svec(x) sort(x.begin(), x.end())
using namespace std;
typedef long long LL;
typedef pair<int, LL> pil;
const LL llinf=2000000000000000000;

struct LAZY_SEGMENT_TREE{
    struct NODE{
        LL l1, l2, mx;
        NODE(){l2=-llinf;}
    }tree[4000010];
    void propogate(int point, int s, int e){
        tree[point].mx=max(tree[point].mx+tree[point].l1, tree[point].l2);
        if(s!=e){
            tree[point*2].l1+=tree[point].l1;
            tree[point*2+1].l1+=tree[point].l1;
            tree[point*2].l2+=tree[point].l1;
            tree[point*2+1].l2+=tree[point].l1;
            tree[point*2].l2=max(tree[point*2].l2, tree[point].l2);
            tree[point*2+1].l2=max(tree[point*2+1].l2, tree[point].l2);
        }
        tree[point].l1=0;
        tree[point].l2=-llinf;
    }
    LL query(int point, int s, int e, int a){
        propogate(point, s, e);
        if(s==e)return tree[point].mx;
        if(a<=(s+e)/2)return query(point*2, s, (s+e)/2, a);
        return query(point*2+1, (s+e)/2+1, e, a);
    }
    void alter(int point, int s, int e, int a, int b, LL val){
        propogate(point, s, e);
        if(e<a||s>b)return;
        if(a<=s&&e<=b){
            tree[point].l1+=val;
            tree[point].l2+=val;
            //propogate(point, s, e);
            return;
        }
        alter(point*2, s, (s+e)/2, a, b, val);
        alter(point*2+1, (s+e)/2+1, e, a, b, val);
    }
    void update(int point, int s, int e, int a, int b, LL val){
        propogate(point, s, e);
        if(e<a||s>b)return;
        if(a<=s&&e<=b){
            tree[point].l2=max(tree[point].l2, val);
            //propogate(point, s, e);
            return;
        }
        update(point*2, s, (s+e)/2, a, b, val);
        update(point*2+1, (s+e)/2+1, e, a, b, val);
    }
}seg;

int n, m;
LL suma[1000010], sumb[1000010];
LL lima[1000010], limb[1000010];
LL sca[1000010], scb[1000010], ans;
vector<pil> qu[1000010];

int main(){
    scanf("%d %d", &n, &m);
    for(int i=1; i<=n; i++){
        scanf("%lld %lld %lld", &suma[i], &lima[i], &sca[i]);
        suma[i]+=suma[i-1];
    }
    for(int i=1; i<=m; i++){
        scanf("%lld %lld %lld", &sumb[i], &limb[i], &scb[i]);
        sumb[i]+=sumb[i-1];
    }
    for(int i=1; i<=n; i++){
        int tmp=upper_bound(sumb, sumb+m+1, lima[i]-suma[i])-sumb-1;
        if(tmp>=0)qu[i].eb(tmp, sca[i]);
    }
    for(int i=1; i<=m; i++){
        int tmp=upper_bound(suma, suma+n+1, limb[i]-sumb[i])-suma-1;
        if(tmp>=0){
            qu[tmp+1].eb(i-1, -scb[i]);
            ans+=scb[i];
        }
    }
    qu[n+1].eb(m-1, -llinf);
    for(int i=1; i<=n+1; i++){
        svec(qu[i]);
        for(auto j:qu[i])seg.alter(1, 0, m, 0, j.F, j.S);
        for(auto j:qu[i]){
            LL tmp=seg.query(1, 0, m, j.F);
            seg.update(1, 0, m, j.F+1, m, tmp);
        }
    }
    printf("%lld", ans+seg.query(1, 0, m, m));
}

Compilation message (stderr)

dishes.cpp: In function 'int main()':
dishes.cpp:68: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:70:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld %lld %lld", &suma[i], &lima[i], &sca[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dishes.cpp:74:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld %lld %lld", &sumb[i], &limb[i], &scb[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 3 / 3
• Subtask 3: 7 / 7
• Subtask 4: 39 / 39
• Subtask 5: 11 / 11
• Subtask 6: 9 / 9
• Subtask 7: 17 / 17
• Subtask 8: 9 / 9