Submission #767906

#	Time	Username	Problem	Language	Result	Execution time	Memory
767906		79brue	Two Dishes (JOI19_dishes)	C++17	100 / 100	3080 ms	173752 KiB

dishes

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const ll INF = 1e18;

void input();
void solve();

int main(){
    input();
    solve();
}

struct Point{
    int x; ll v;
    Point(){}
    Point(int x, ll v): x(x), v(v){}
};

int n, m;
Point a[1000002], b[1000002];

void input(){
    scanf("%d %d", &n, &m);
    vector<ll> A (n+1), S (n+1), P(n+1);
    vector<ll> B (m+1), T (m+1), Q(m+1);
    vector<ll> Asum(n+1), Bsum(m+1);
    for(int i=1; i<=n; i++) scanf("%lld %lld %lld", &A[i], &S[i], &P[i]);
    for(int i=1; i<=m; i++) scanf("%lld %lld %lld", &B[i], &T[i], &Q[i]);
    for(int i=1; i<=n; i++) Asum[i] = Asum[i-1] + A[i];
    for(int i=1; i<=m; i++) Bsum[i] = Bsum[i-1] + B[i];

    for(int i=1; i<=n; i++) a[i] = Point(upper_bound(Bsum.begin(), Bsum.end(), S[i] - Asum[i]) - Bsum.begin() - 1, P[i]);
    for(int i=1; i<=m; i++) b[i] = Point(upper_bound(Asum.begin(), Asum.end(), T[i] - Bsum[i]) - Asum.begin() - 1, Q[i]);
}

struct segTree{
    struct Node{
        ll val, lazy; /// 구간 최대 val, 거기에 lazy
        ll extra, ans; /// extra: 구간 extra의 합, ans: 구간 적당한 점 val + 그 오른쪽 extra 합의 최댓값

        Node(){}
        Node(ll val, ll extra, ll ans): val(val), extra(extra), ans(ans){lazy = 0;}
        Node operator+(const Node &r)const{
            return Node(max(val, r.val), extra + r.extra, max(ans + r.extra, r.ans));
        }
    } tree[1<<21];

    void init(int i, int l, int r){
        tree[i].val = tree[i].lazy = tree[i].extra = tree[i].ans = 0;
        if(l==r) return;
        int m = (l+r)>>1;
        init(i*2, l, m);
        init(i*2+1, m+1, r);
    }

    void propagate(int i, int l, int r){
        tree[i].val += tree[i].lazy;
        tree[i].ans += tree[i].lazy;
        if(l!=r){
            tree[i*2].lazy += tree[i].lazy;
            tree[i*2+1].lazy += tree[i].lazy;
        }
        tree[i].lazy = 0;
    }

    Node query(int i, int l, int r, int s, int e){ /// 구간의 ans를 확인
        propagate(i, l, r);
        if(r<s || e<l) return Node(-INF, 0, -INF);
        if(s<=l && r<=e) return tree[i];
        int m = (l+r)>>1;
        return query(i*2, l, m, s, e) + query(i*2+1, m+1, r, s, e);
    }

    void updateVal(int i, int l, int r, int x, ll v){ /// 한 위치의 val을 수정
        propagate(i, l, r);
        if(x<l || r<x) return;
        if(l==r){
            tree[i].val = tree[i].ans = v;
            return;
        }
        int m = (l+r)>>1;
        updateVal(i*2, l, m, x, v);
        updateVal(i*2+1, m+1, r, x, v);
        tree[i] = tree[i*2] + tree[i*2+1];
    }

    void updateExtra(int i, int l, int r, int x, ll v){ /// 한 위치의 extra를 수정
        propagate(i, l, r);
        if(x<l || r<x) return;
        if(l==r){
            tree[i].extra += v;
            return;
        }
        int m = (l+r)>>1;
        updateExtra(i*2, l, m, x, v);
        updateExtra(i*2+1, m+1, r, x, v);
        tree[i] = tree[i*2] + tree[i*2+1];
    }

    void add(int i, int l, int r, int s, int e, ll v){ /// 구간의 val을 수정
        propagate(i, l, r);
        if(r<s || e<l) return;
        if(s<=l && r<=e){
            tree[i].lazy = v;
            propagate(i, l, r);
            return;
        }
        int m = (l+r)>>1;
        add(i*2, l, m, s, e, v);
        add(i*2+1, m+1, r, s, e, v);
        tree[i] = tree[i*2] + tree[i*2+1];
    }
} tree;

struct Event{
    int type; /// 0: 가로, 1: 세로
    int time; /// 시간
    int x; /// 추가 인자
    ll v; /// 막대 길이

    Event(int type, int time, int x, ll v): type(type), time(time), x(x), v(v){}
    bool operator<(const Event &r)const{
        if(time != r.time) return time < r.time;
        if(type != r.type) return type < r.type;
        return x < r.x;
    }
};

ll added = 0;

void solve(){
    vector<Event> vec;
    tree.init(1, 0, n);
    for(int i=1; i<=n; i++){
        if(a[i].x < 0) continue;
        if(a[i].x >= m){
            added += a[i].v;
            continue;
        }
        if(a[i].v > 0){
            vec.push_back(Event(1, a[i].x, i, a[i].v)); /// 세로 막대
            tree.updateExtra(1, 0, n, i, a[i].v);
        }
        if(a[i].v < 0){
            added += a[i].v;
            vec.push_back(Event(0, a[i].x+1, i-1, -a[i].v));
        }
    }
    for(int i=1; i<=m; i++){
        if(b[i].x < 0) continue;
        if(b[i].x >= n){
            added += b[i].v;
            continue;
        }
        if(b[i].v > 0) vec.push_back(Event(0, i, b[i].x, b[i].v));
        if(b[i].v < 0){
            added += b[i].v;
            vec.push_back(Event(1, i-1, b[i].x+1, -b[i].v));
            tree.updateExtra(1, 0, n, b[i].x+1, -b[i].v);
        }
    }
    sort(vec.begin(), vec.end());

    for(int i=1; i<=n; i++){
        if(a[i].x < 0) continue;
    }
    for(Event &p: vec){
//        printf("Event %d %d %d %lld\n", p.type, p.time, p.x, p.v);
        if(p.type == 0){ /// 가로 막대
            tree.add(1, 0, n, 0, p.x, p.v);
        }
        else{ /// 세로 막대
            ll v = tree.query(1, 0, n, 0, p.x).ans;
//            printf("Query %d %lld: value %lld\n", p.x, p.v, v);
            tree.updateExtra(1, 0, n, p.x, -p.v);
            tree.updateVal(1, 0, n, p.x, v);
        }
//        for(int j=0; j<=n; j++) printf("%2lld ", tree.query(1, 0, j, 0, j).ans);
//        puts("");
    }

    printf("%lld", tree.query(1, 0, n, 0, n).ans + added);
}

Compilation message (stderr)

dishes.cpp: In function 'void input()':
dishes.cpp:26:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
dishes.cpp:30:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |     for(int i=1; i<=n; i++) scanf("%lld %lld %lld", &A[i], &S[i], &P[i]);
      |                             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dishes.cpp:31:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |     for(int i=1; i<=m; i++) scanf("%lld %lld %lld", &B[i], &T[i], &Q[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