oj.uz

Submission #166500

# Submission time Handle Problem Language Result Execution time Memory
166500 2019-12-02T15:44:48 Z Akashi Two Dishes (JOI19_dishes) C++14
5 / 100
 630 ms 62064 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_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 = 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 <= 4 * m + 4 ; ++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);
    }

    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

# Verdict Execution time Memory Grader output
1 Correct 630 ms 61240 KB Output is correct
2 Correct 620 ms 62064 KB Output is correct
3 Correct 329 ms 55388 KB Output is correct
4 Correct 517 ms 54652 KB Output is correct
5 Correct 25 ms 23928 KB Output is correct
6 Correct 557 ms 59792 KB Output is correct
7 Correct 207 ms 47964 KB Output is correct
8 Correct 136 ms 31292 KB Output is correct
9 Correct 335 ms 55604 KB Output is correct
10 Correct 600 ms 61712 KB Output is correct
11 Correct 264 ms 55504 KB Output is correct

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 23872 KB Output is correct
2 Correct 25 ms 23924 KB Output is correct
3 Correct 24 ms 23928 KB Output is correct
4 Correct 25 ms 23928 KB Output is correct
5 Correct 26 ms 23892 KB Output is correct
6 Correct 24 ms 23824 KB Output is correct
7 Correct 24 ms 23876 KB Output is correct
8 Correct 25 ms 23928 KB Output is correct
9 Correct 24 ms 23852 KB Output is correct
10 Incorrect 24 ms 23932 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 23872 KB Output is correct
2 Correct 25 ms 23924 KB Output is correct
3 Correct 24 ms 23928 KB Output is correct
4 Correct 25 ms 23928 KB Output is correct
5 Correct 26 ms 23892 KB Output is correct
6 Correct 24 ms 23824 KB Output is correct
7 Correct 24 ms 23876 KB Output is correct
8 Correct 25 ms 23928 KB Output is correct
9 Correct 24 ms 23852 KB Output is correct
10 Incorrect 24 ms 23932 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 23872 KB Output is correct
2 Correct 25 ms 23924 KB Output is correct
3 Correct 24 ms 23928 KB Output is correct
4 Correct 25 ms 23928 KB Output is correct
5 Correct 26 ms 23892 KB Output is correct
6 Correct 24 ms 23824 KB Output is correct
7 Correct 24 ms 23876 KB Output is correct
8 Correct 25 ms 23928 KB Output is correct
9 Correct 24 ms 23852 KB Output is correct
10 Incorrect 24 ms 23932 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 23872 KB Output is correct
2 Correct 25 ms 23924 KB Output is correct
3 Correct 24 ms 23928 KB Output is correct
4 Correct 25 ms 23928 KB Output is correct
5 Correct 26 ms 23892 KB Output is correct
6 Correct 24 ms 23824 KB Output is correct
7 Correct 24 ms 23876 KB Output is correct
8 Correct 25 ms 23928 KB Output is correct
9 Correct 24 ms 23852 KB Output is correct
10 Incorrect 24 ms 23932 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 23872 KB Output is correct
2 Correct 25 ms 23924 KB Output is correct
3 Correct 24 ms 23928 KB Output is correct
4 Correct 25 ms 23928 KB Output is correct
5 Correct 26 ms 23892 KB Output is correct
6 Correct 24 ms 23824 KB Output is correct
7 Correct 24 ms 23876 KB Output is correct
8 Correct 25 ms 23928 KB Output is correct
9 Correct 24 ms 23852 KB Output is correct
10 Incorrect 24 ms 23932 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #7
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 630 ms 61240 KB Output is correct
2 Correct 620 ms 62064 KB Output is correct
3 Correct 329 ms 55388 KB Output is correct
4 Correct 517 ms 54652 KB Output is correct
5 Correct 25 ms 23928 KB Output is correct
6 Correct 557 ms 59792 KB Output is correct
7 Correct 207 ms 47964 KB Output is correct
8 Correct 136 ms 31292 KB Output is correct
9 Correct 335 ms 55604 KB Output is correct
10 Correct 600 ms 61712 KB Output is correct
11 Correct 264 ms 55504 KB Output is correct
12 Correct 24 ms 23872 KB Output is correct
13 Correct 25 ms 23924 KB Output is correct
14 Correct 24 ms 23928 KB Output is correct
15 Correct 25 ms 23928 KB Output is correct
16 Correct 26 ms 23892 KB Output is correct
17 Correct 24 ms 23824 KB Output is correct
18 Correct 24 ms 23876 KB Output is correct
19 Correct 25 ms 23928 KB Output is correct
20 Correct 24 ms 23852 KB Output is correct
21 Incorrect 24 ms 23932 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 630 ms 61240 KB Output is correct
2 Correct 620 ms 62064 KB Output is correct
3 Correct 329 ms 55388 KB Output is correct
4 Correct 517 ms 54652 KB Output is correct
5 Correct 25 ms 23928 KB Output is correct
6 Correct 557 ms 59792 KB Output is correct
7 Correct 207 ms 47964 KB Output is correct
8 Correct 136 ms 31292 KB Output is correct
9 Correct 335 ms 55604 KB Output is correct
10 Correct 600 ms 61712 KB Output is correct
11 Correct 264 ms 55504 KB Output is correct
12 Correct 24 ms 23872 KB Output is correct
13 Correct 25 ms 23924 KB Output is correct
14 Correct 24 ms 23928 KB Output is correct
15 Correct 25 ms 23928 KB Output is correct
16 Correct 26 ms 23892 KB Output is correct
17 Correct 24 ms 23824 KB Output is correct
18 Correct 24 ms 23876 KB Output is correct
19 Correct 25 ms 23928 KB Output is correct
20 Correct 24 ms 23852 KB Output is correct
21 Incorrect 24 ms 23932 KB Output isn't correct
22 Halted 0 ms 0 KB -