oj.uz

Submission #166491

# Submission time Handle Problem Language Result Execution time Memory
166491 2019-12-02T15:34:23 Z Akashi Two Dishes (JOI19_dishes) C++14
5 / 100
 625 ms 63508 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){
        if(i > 0){
            for(auto it : v[i - 1]){
                long long val = -INF;
                if(it.first != 1) val = query(1, it.first - 1);
                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 625 ms 60548 KB Output is correct
2 Correct 622 ms 61164 KB Output is correct
3 Correct 329 ms 54388 KB Output is correct
4 Correct 497 ms 53672 KB Output is correct
5 Correct 25 ms 23928 KB Output is correct
6 Correct 568 ms 59268 KB Output is correct
7 Correct 212 ms 47096 KB Output is correct
8 Correct 129 ms 33528 KB Output is correct
9 Correct 402 ms 57148 KB Output is correct
10 Correct 586 ms 63508 KB Output is correct
11 Correct 259 ms 57308 KB Output is correct

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 23856 KB Output is correct
2 Correct 24 ms 23912 KB Output is correct
3 Correct 27 ms 23928 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

# Verdict Execution time Memory Grader output
1 Correct 27 ms 23856 KB Output is correct
2 Correct 24 ms 23912 KB Output is correct
3 Correct 27 ms 23928 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

# Verdict Execution time Memory Grader output
1 Correct 27 ms 23856 KB Output is correct
2 Correct 24 ms 23912 KB Output is correct
3 Correct 27 ms 23928 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

# Verdict Execution time Memory Grader output
1 Correct 27 ms 23856 KB Output is correct
2 Correct 24 ms 23912 KB Output is correct
3 Correct 27 ms 23928 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

# Verdict Execution time Memory Grader output
1 Correct 27 ms 23856 KB Output is correct
2 Correct 24 ms 23912 KB Output is correct
3 Correct 27 ms 23928 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

# Verdict Execution time Memory Grader output
1 Correct 625 ms 60548 KB Output is correct
2 Correct 622 ms 61164 KB Output is correct
3 Correct 329 ms 54388 KB Output is correct
4 Correct 497 ms 53672 KB Output is correct
5 Correct 25 ms 23928 KB Output is correct
6 Correct 568 ms 59268 KB Output is correct
7 Correct 212 ms 47096 KB Output is correct
8 Correct 129 ms 33528 KB Output is correct
9 Correct 402 ms 57148 KB Output is correct
10 Correct 586 ms 63508 KB Output is correct
11 Correct 259 ms 57308 KB Output is correct
12 Correct 27 ms 23856 KB Output is correct
13 Correct 24 ms 23912 KB Output is correct
14 Correct 27 ms 23928 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

# Verdict Execution time Memory Grader output
1 Correct 625 ms 60548 KB Output is correct
2 Correct 622 ms 61164 KB Output is correct
3 Correct 329 ms 54388 KB Output is correct
4 Correct 497 ms 53672 KB Output is correct
5 Correct 25 ms 23928 KB Output is correct
6 Correct 568 ms 59268 KB Output is correct
7 Correct 212 ms 47096 KB Output is correct
8 Correct 129 ms 33528 KB Output is correct
9 Correct 402 ms 57148 KB Output is correct
10 Correct 586 ms 63508 KB Output is correct
11 Correct 259 ms 57308 KB Output is correct
12 Correct 27 ms 23856 KB Output is correct
13 Correct 24 ms 23912 KB Output is correct
14 Correct 27 ms 23928 KB Output is correct
15 Incorrect 25 ms 23928 KB Output isn't correct
16 Halted 0 ms 0 KB -