oj.uz

답안 #166486

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
166486 2019-12-02T15:23:05 Z Akashi Two Dishes (JOI19_dishes) C++14
5 / 100
 684 ms 62168 KB 
#include <bits/stdc++.h>
using namespace std;

const int SZ = 1e6 + 5;
const long long INF = 1e18;

int n, m;
long long Arb[4000005], Lazy_scad[4000005], Lazy_max[4000005];

long long a[SZ], b[SZ], s[SZ], s1[SZ], s2[SZ], t[SZ], q[SZ], p[SZ];

void propag_scad(int nod){
    if(Lazy_scad[nod] != 0){
        Arb[nod * 2] += Lazy_scad[nod];
        Arb[nod * 2 + 1] += Lazy_scad[nod];
        Lazy_scad[nod * 2] += Lazy_scad[nod];
        Lazy_scad[nod * 2 + 1] += Lazy_scad[nod];
        Lazy_scad[nod] = 0;
    }
}

void propag_max(int nod){
    if(Lazy_max[nod] != -INF){
        Arb[nod * 2] = max(Arb[nod * 2], Lazy_max[nod]);
        Arb[nod * 2 + 1] = max(Arb[nod * 2 + 1], Lazy_max[nod]);
        Lazy_max[nod * 2] = max(Lazy_max[nod * 2], Lazy_max[nod]);
        Lazy_max[nod * 2 + 1] = max(Lazy_max[nod * 2 + 1], Lazy_max[nod]);
        Lazy_max[nod] = -INF;
    }
}

void update_scad(int x, int y, long long v, int st = 1, int dr = m, int nod = 1){
    if(st != dr) propag_scad(nod), propag_max(nod);

    if(x <= st && dr <= y){
        Lazy_scad[nod] += v;
        Arb[nod] += v;
        return ;
    }

    int mij = (st + dr) / 2;
    if(x <= mij) update_scad(x, y, v, st, mij, nod * 2);
    if(mij + 1 <= y) update_scad(x, y, v, mij + 1, dr, nod * 2 + 1);

    Arb[nod] = max(Arb[nod * 2], Arb[nod * 2 + 1]);
}

void update_max(int x, int y, long long v, int st = 1, int dr = m, int nod = 1){
    if(st != dr) propag_scad(nod), propag_max(nod);

    if(x <= st && dr <= y){
        Lazy_max[nod] = max(v, Lazy_max[nod]);
        Arb[nod] = max(v, Arb[nod]);
        return ;
    }

    int mij = (st + dr) / 2;
    if(x <= mij) update_max(x, y, v, st, mij, nod * 2);
    if(mij + 1 <= y) update_max(x, y, v, mij + 1, dr, nod * 2 + 1);

    Arb[nod] = max(Arb[nod * 2], Arb[nod * 2 + 1]);
}

long long query(int x, int y, int st = 1, int dr = m, int nod = 1){
    if(x <= st && dr <= y) return Arb[nod];
    if(st != dr) propag_scad(nod), propag_max(nod);

    int mij = (st + dr) / 2;
    long long a1 = -INF, a2 = -INF;

    if(x <= mij) a1 = query(x, y, st, mij, nod * 2);
    if(mij + 1 <= y) a2 = query(x, y, mij + 1, dr, nod * 2 + 1);

    return max(a1, a2);
}

vector <pair <int, long long> > v[SZ];

void add_point(int x, int y, long long val){
    v[x].push_back({y, val});
}

int main()
{
//    freopen("1.in", "r", stdin);

    scanf("%d%d", &n, &m);

    for(int i = 1; i <= 4 * m ; ++i) Lazy_max[i] = -INF;

    for(int i = 1; i <= n ; ++i){
        scanf("%lld%lld%lld", &a[i], &s[i], &p[i]);
        s1[i] = s1[i - 1] + a[i];
    }

    for(int i = 1; i <= m ; ++i){
        scanf("%lld%lld%lld", &b[i], &t[i], &q[i]);
        s2[i] = s2[i - 1] + b[i];
    }

    long long Sum = 0;
    for(int i = 1; i <= n ; ++i){
        long long v = s[i] - s1[i];
        if(v < 0) continue ;

        int st = 1, dr = m;
        while(st <= dr){
            int mij = (st + dr) / 2;

            if(s2[mij] <= v) st = mij + 1;
            else dr = mij - 1;
        }

        if(dr < m) add_point(i - 1, dr + 1, -p[i]);
        Sum += p[i];
    }

    for(int i = 1; i <= m ; ++i){
        long long v = t[i] - s2[i];
        if(v < 0) continue ;

        int st = 1, dr = n;
        while(st <= dr){
            int mij = (st + dr) / 2;

            if(s1[mij] <= v) st = mij + 1;
            else dr = mij - 1;
        }

        add_point(dr, i, q[i]);
    }

    for(int i = 0; i <= n ; ++i){
        for(auto it : v[i]) update_scad(it.first, m, it.second);
        for(auto it : v[i]){
            long long val = -INF;
            if(it.first != 1) val = query(1, it.first - 1);
            update_max(it.first, m, val);
        }
    }

    printf("%lld", Sum + Arb[1]);

    return 0;
}

Compilation message

dishes.cpp: In function 'int main()':
dishes.cpp:87: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:92:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld%lld%lld", &a[i], &s[i], &p[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dishes.cpp:97:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld%lld%lld", &b[i], &t[i], &q[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 634 ms 61732 KB Output is correct
2 Correct 684 ms 62168 KB Output is correct
3 Correct 466 ms 55488 KB Output is correct
4 Correct 528 ms 54812 KB Output is correct
5 Correct 24 ms 23928 KB Output is correct
6 Correct 607 ms 59892 KB Output is correct
7 Correct 314 ms 48476 KB Output is correct
8 Correct 140 ms 31860 KB Output is correct
9 Correct 481 ms 55516 KB Output is correct
10 Correct 595 ms 61756 KB Output is correct
11 Correct 381 ms 55716 KB Output is correct

Subtask #2
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 23928 KB Output is correct
2 Correct 25 ms 23928 KB Output is correct
3 Correct 24 ms 23900 KB Output is correct
4 Incorrect 25 ms 23928 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 23928 KB Output is correct
2 Correct 25 ms 23928 KB Output is correct
3 Correct 24 ms 23900 KB Output is correct
4 Incorrect 25 ms 23928 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 23928 KB Output is correct
2 Correct 25 ms 23928 KB Output is correct
3 Correct 24 ms 23900 KB Output is correct
4 Incorrect 25 ms 23928 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 23928 KB Output is correct
2 Correct 25 ms 23928 KB Output is correct
3 Correct 24 ms 23900 KB Output is correct
4 Incorrect 25 ms 23928 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 23928 KB Output is correct
2 Correct 25 ms 23928 KB Output is correct
3 Correct 24 ms 23900 KB Output is correct
4 Incorrect 25 ms 23928 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 634 ms 61732 KB Output is correct
2 Correct 684 ms 62168 KB Output is correct
3 Correct 466 ms 55488 KB Output is correct
4 Correct 528 ms 54812 KB Output is correct
5 Correct 24 ms 23928 KB Output is correct
6 Correct 607 ms 59892 KB Output is correct
7 Correct 314 ms 48476 KB Output is correct
8 Correct 140 ms 31860 KB Output is correct
9 Correct 481 ms 55516 KB Output is correct
10 Correct 595 ms 61756 KB Output is correct
11 Correct 381 ms 55716 KB Output is correct
12 Correct 24 ms 23928 KB Output is correct
13 Correct 25 ms 23928 KB Output is correct
14 Correct 24 ms 23900 KB Output is correct
15 Incorrect 25 ms 23928 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 634 ms 61732 KB Output is correct
2 Correct 684 ms 62168 KB Output is correct
3 Correct 466 ms 55488 KB Output is correct
4 Correct 528 ms 54812 KB Output is correct
5 Correct 24 ms 23928 KB Output is correct
6 Correct 607 ms 59892 KB Output is correct
7 Correct 314 ms 48476 KB Output is correct
8 Correct 140 ms 31860 KB Output is correct
9 Correct 481 ms 55516 KB Output is correct
10 Correct 595 ms 61756 KB Output is correct
11 Correct 381 ms 55716 KB Output is correct
12 Correct 24 ms 23928 KB Output is correct
13 Correct 25 ms 23928 KB Output is correct
14 Correct 24 ms 23900 KB Output is correct
15 Incorrect 25 ms 23928 KB Output isn't correct
16 Halted 0 ms 0 KB -