oj.uz

Submission #170396

# Submission time Handle Problem Language Result Execution time Memory
170396 2019-12-25T03:57:06 Z puppies_and_rainbows Two Dishes (JOI19_dishes) C++14
0 / 100
 760 ms 123164 KB 
//test    
#include<bits/stdc++.h>

    using namespace std;

    #define X       first
    #define Y       second
    #define int     long long
    #define pb      push_back
    #define lch     i << 1
    #define rch     i << 1 | 1

    const int   N   = 1e6 + 5;
    const int   inf = 1e18;

    typedef pair<int,int>  ii;

    ii  operator + (const ii &a,const ii &b)    {
        return  ii(a.X + b.X,max(a.Y + b.X,b.Y));
    }

    int n, m;
    int res = 0;

    int tr[N << 2];
    ii  lz[N << 2];

    int push(int i,int l,int r) {
        tr[i] = max(tr[i] + lz[i].X,lz[i].Y);
        if (l < r)  {
            lz[lch] = lz[lch] + lz[i];
            lz[rch] = lz[rch] + lz[i];
        }
        lz[i] = ii(0,-inf);
    }
    int _upd(int i,int l,int r,int L,int R,ii  v)   {
        push(i,l,r);
        if (R <  l || r <  L)   return  0;
        if (L <= l && r <= R)   {
            lz[i] = v;
            push(i,l,r);
            return  1;
        }
        int m = (l + r) / 2;
        _upd(lch,l,m,L,R,v);    ++m;
        _upd(rch,m,r,L,R,v);
        tr[i] = max(tr[lch],tr[rch]);
    }
    int _get(int i,int l,int r,int p)   {
        push(i,l,r);
        if (l == r) return  tr[i];
        int m = (l + r) / 2;
        if (p <= m) return  _get(lch,l,m,p);
        else    return ++m, _get(rch,m,r,p);
    }

    int a[N], s[N], p[N];
    int b[N], t[N], q[N];

    vector<ii>  v[N];

    signed main()   {
        ios_base::sync_with_stdio(0);
        cin.tie(0); cout.tie(0);

        cin >> n >> m;

        for(int i = 1 ; i <= n ; ++i)   cin >> a[i] >> s[i] >> p[i], a[i] += a[i - 1];
        for(int i = 1 ; i <= m ; ++i)   cin >> b[i] >> t[i] >> q[i], b[i] += b[i - 1];

        for(int i = 1 ; i <= n ; ++i)   {
            int x = upper_bound(b,b + 1 + m,s[i] - a[i]) - b;
            if (x >= 1) v[x - 1].pb({i-1,p[i]});
        }
        for(int i = 1 ; i <= m ; ++i)   {
            res  += q[i];
            q[i] = -q[i];
            int x = upper_bound(a,a + 1 + n,t[i] - b[i]) - a;
            if (x <= n) v[i - 1].pb({x-1,q[i]});
        }

        n++;
        fill(lz,lz + N * 4,ii(0,-inf));

        for(int i = 0 ; i < m ; ++i)    {
            for(ii  x : v[i])
                _upd(1,1,n,x.X + 1,n,{x.Y,-inf});
            for(ii  x : v[i])   if (x.X)
                _upd(1,1,n,x.X + 1,n,{0,_get(1,1,n,x.X)});
        }
        for(ii  x : v[m])   _upd(1,1,n,x.X + 1,n,{x.Y,-inf});

        cout << res + _get(1,1,n,n);
    }

Compilation message

dishes.cpp: In function 'long long int push(long long int, long long int, long long int)':
dishes.cpp:35:5: warning: no return statement in function returning non-void [-Wreturn-type]
     }
     ^
dishes.cpp: In function 'long long int _upd(long long int, long long int, long long int, long long int, long long int, ii)':
dishes.cpp:48:5: warning: control reaches end of non-void function [-Wreturn-type]
     }
     ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 760 ms 123148 KB Output is correct
2 Correct 741 ms 123164 KB Output is correct
3 Correct 409 ms 116704 KB Output is correct
4 Incorrect 626 ms 120492 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 86520 KB Output is correct
2 Correct 82 ms 86520 KB Output is correct
3 Correct 74 ms 86596 KB Output is correct
4 Correct 73 ms 86520 KB Output is correct
5 Incorrect 73 ms 86520 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 86520 KB Output is correct
2 Correct 82 ms 86520 KB Output is correct
3 Correct 74 ms 86596 KB Output is correct
4 Correct 73 ms 86520 KB Output is correct
5 Incorrect 73 ms 86520 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 86520 KB Output is correct
2 Correct 82 ms 86520 KB Output is correct
3 Correct 74 ms 86596 KB Output is correct
4 Correct 73 ms 86520 KB Output is correct
5 Incorrect 73 ms 86520 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 86520 KB Output is correct
2 Correct 82 ms 86520 KB Output is correct
3 Correct 74 ms 86596 KB Output is correct
4 Correct 73 ms 86520 KB Output is correct
5 Incorrect 73 ms 86520 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 86520 KB Output is correct
2 Correct 82 ms 86520 KB Output is correct
3 Correct 74 ms 86596 KB Output is correct
4 Correct 73 ms 86520 KB Output is correct
5 Incorrect 73 ms 86520 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 760 ms 123148 KB Output is correct
2 Correct 741 ms 123164 KB Output is correct
3 Correct 409 ms 116704 KB Output is correct
4 Incorrect 626 ms 120492 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 760 ms 123148 KB Output is correct
2 Correct 741 ms 123164 KB Output is correct
3 Correct 409 ms 116704 KB Output is correct
4 Incorrect 626 ms 120492 KB Output isn't correct
5 Halted 0 ms 0 KB -