oj.uz

Submission #166509

# Submission time Handle Problem Language Result Execution time Memory
166509 2019-12-02T16:10:56 Z Akashi Two Dishes (JOI19_dishes) C++14
3 / 100
 664 ms 90244 KB 
#include <bits/stdc++.h>
using namespace std;

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

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

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_max[nod * 2] += Lazy_scad[nod];
        Lazy_max[nod * 2 + 1] += Lazy_scad[nod];
        Lazy_scad[nod] = 0;
    }
}

void propag_max(int nod){
    if(Lazy_max[nod] != -INF){
        if(Arb[nod * 2] < Lazy_max[nod]){
            Arb[nod * 2] = Lazy_max[nod];
            Lazy_scad[nod * 2] = 0;
        }
        if(Arb[nod * 2 + 1] < Lazy_max[nod]){
            Arb[nod * 2 + 1] = Lazy_max[nod];
            Lazy_scad[nod * 2 + 1] = 0;
        }
        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 = 0, 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 = 0, 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 = 0, 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 <= 4000014 ; ++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){
        if(i > 0){
            for(auto it : v[i - 1]){
                long long val = query(0, it.first);
                update_max(it.first, m, val);
            }
        }

        for(auto it : v[i]) update_scad(it.first, m, it.second);
    }

    long long val = query(m, m);
    printf("%lld", Sum + val);

    return 0;
}

Compilation message

dishes.cpp: In function 'int main()':
dishes.cpp:96: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: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:106: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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 661 ms 89660 KB Output is correct
2 Correct 664 ms 90244 KB Output is correct
3 Correct 358 ms 83696 KB Output is correct
4 Correct 534 ms 82924 KB Output is correct
5 Correct 50 ms 55160 KB Output is correct
6 Incorrect 593 ms 88536 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 55132 KB Output is correct
2 Correct 52 ms 55212 KB Output is correct
3 Correct 51 ms 55160 KB Output is correct
4 Correct 49 ms 55152 KB Output is correct
5 Correct 50 ms 55160 KB Output is correct
6 Correct 49 ms 55212 KB Output is correct
7 Correct 49 ms 55160 KB Output is correct
8 Correct 50 ms 55196 KB Output is correct
9 Correct 52 ms 55288 KB Output is correct
10 Correct 49 ms 55152 KB Output is correct
11 Correct 49 ms 55160 KB Output is correct
12 Correct 49 ms 55288 KB Output is correct
13 Correct 50 ms 55160 KB Output is correct
14 Correct 49 ms 55160 KB Output is correct
15 Correct 49 ms 55132 KB Output is correct
16 Correct 49 ms 55228 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 55132 KB Output is correct
2 Correct 52 ms 55212 KB Output is correct
3 Correct 51 ms 55160 KB Output is correct
4 Correct 49 ms 55152 KB Output is correct
5 Correct 50 ms 55160 KB Output is correct
6 Correct 49 ms 55212 KB Output is correct
7 Correct 49 ms 55160 KB Output is correct
8 Correct 50 ms 55196 KB Output is correct
9 Correct 52 ms 55288 KB Output is correct
10 Correct 49 ms 55152 KB Output is correct
11 Correct 49 ms 55160 KB Output is correct
12 Correct 49 ms 55288 KB Output is correct
13 Correct 50 ms 55160 KB Output is correct
14 Correct 49 ms 55160 KB Output is correct
15 Correct 49 ms 55132 KB Output is correct
16 Correct 49 ms 55228 KB Output is correct
17 Correct 54 ms 55608 KB Output is correct
18 Correct 72 ms 55516 KB Output is correct
19 Incorrect 55 ms 55544 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 55132 KB Output is correct
2 Correct 52 ms 55212 KB Output is correct
3 Correct 51 ms 55160 KB Output is correct
4 Correct 49 ms 55152 KB Output is correct
5 Correct 50 ms 55160 KB Output is correct
6 Correct 49 ms 55212 KB Output is correct
7 Correct 49 ms 55160 KB Output is correct
8 Correct 50 ms 55196 KB Output is correct
9 Correct 52 ms 55288 KB Output is correct
10 Correct 49 ms 55152 KB Output is correct
11 Correct 49 ms 55160 KB Output is correct
12 Correct 49 ms 55288 KB Output is correct
13 Correct 50 ms 55160 KB Output is correct
14 Correct 49 ms 55160 KB Output is correct
15 Correct 49 ms 55132 KB Output is correct
16 Correct 49 ms 55228 KB Output is correct
17 Correct 54 ms 55608 KB Output is correct
18 Correct 72 ms 55516 KB Output is correct
19 Incorrect 55 ms 55544 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 55132 KB Output is correct
2 Correct 52 ms 55212 KB Output is correct
3 Correct 51 ms 55160 KB Output is correct
4 Correct 49 ms 55152 KB Output is correct
5 Correct 50 ms 55160 KB Output is correct
6 Correct 49 ms 55212 KB Output is correct
7 Correct 49 ms 55160 KB Output is correct
8 Correct 50 ms 55196 KB Output is correct
9 Correct 52 ms 55288 KB Output is correct
10 Correct 49 ms 55152 KB Output is correct
11 Correct 49 ms 55160 KB Output is correct
12 Correct 49 ms 55288 KB Output is correct
13 Correct 50 ms 55160 KB Output is correct
14 Correct 49 ms 55160 KB Output is correct
15 Correct 49 ms 55132 KB Output is correct
16 Correct 49 ms 55228 KB Output is correct
17 Correct 54 ms 55608 KB Output is correct
18 Correct 72 ms 55516 KB Output is correct
19 Incorrect 55 ms 55544 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 55132 KB Output is correct
2 Correct 52 ms 55212 KB Output is correct
3 Correct 51 ms 55160 KB Output is correct
4 Correct 49 ms 55152 KB Output is correct
5 Correct 50 ms 55160 KB Output is correct
6 Correct 49 ms 55212 KB Output is correct
7 Correct 49 ms 55160 KB Output is correct
8 Correct 50 ms 55196 KB Output is correct
9 Correct 52 ms 55288 KB Output is correct
10 Correct 49 ms 55152 KB Output is correct
11 Correct 49 ms 55160 KB Output is correct
12 Correct 49 ms 55288 KB Output is correct
13 Correct 50 ms 55160 KB Output is correct
14 Correct 49 ms 55160 KB Output is correct
15 Correct 49 ms 55132 KB Output is correct
16 Correct 49 ms 55228 KB Output is correct
17 Correct 54 ms 55608 KB Output is correct
18 Correct 72 ms 55516 KB Output is correct
19 Incorrect 55 ms 55544 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #7
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 661 ms 89660 KB Output is correct
2 Correct 664 ms 90244 KB Output is correct
3 Correct 358 ms 83696 KB Output is correct
4 Correct 534 ms 82924 KB Output is correct
5 Correct 50 ms 55160 KB Output is correct
6 Incorrect 593 ms 88536 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 661 ms 89660 KB Output is correct
2 Correct 664 ms 90244 KB Output is correct
3 Correct 358 ms 83696 KB Output is correct
4 Correct 534 ms 82924 KB Output is correct
5 Correct 50 ms 55160 KB Output is correct
6 Incorrect 593 ms 88536 KB Output isn't correct
7 Halted 0 ms 0 KB -