Submission #157340

#	Time	Username	Problem	Language	Result	Execution time	Memory
157340		combi1k1	Two Dishes (JOI19_dishes)	C++14	100 / 100	6717 ms	218964 KiB

dishes

#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,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,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 (stderr)

dishes.cpp: In function 'long long int push(long long int, long long int, long long int)':
dishes.cpp:34:1: 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:47:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

• Subtask 1: 5 / 5
• Subtask 2: 3 / 3
• Subtask 3: 7 / 7
• Subtask 4: 39 / 39
• Subtask 5: 11 / 11
• Subtask 6: 9 / 9
• Subtask 7: 17 / 17
• Subtask 8: 9 / 9