Submission #196777

#	Time	Username	Problem	Language	Result	Execution time	Memory
196777		rkm0959	Two Dishes (JOI19_dishes)	C++14	100 / 100	6891 ms	300984 KiB

dishes

#include <bits/stdc++.h>
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long double ldb;
typedef long long int ll;
typedef unsigned long long int ull;
typedef complex<double> base;

// range update (addition)
// range update (replacement)
// range query (maximum)

ll N, M, ans, inf=2e18;
ll tree[4444444];
ll lazy_1[4444444];
ll lazy_2[4444444];
ll A[1111111], B[1111111];
ll PA[1111111], PB[1111111];
ll f[1111111], g[1111111];
ll S[1111111], T[1111111];
ll P[1111111], Q[1111111];
vector< pair<ll, ll> > upd[1111111];

void workdown(int index, int s, int e)
{
    if(s==e) return;
    if(lazy_1[index])
    {
        tree[index<<1]+=lazy_1[index];
        if(lazy_2[index<<1]!=-inf) lazy_2[index<<1]+=lazy_1[index];
        else lazy_1[index<<1]+=lazy_1[index];
        tree[index<<1|1]+=lazy_1[index];
        if(lazy_2[index<<1|1]!=-inf) lazy_2[index<<1|1]+=lazy_1[index];
        else lazy_1[index<<1|1]+=lazy_1[index];
        lazy_1[index]=0;
    }
    if(lazy_2[index]!=-inf)
    {
        tree[index<<1]=tree[index];
        lazy_1[index<<1]=0; lazy_2[index<<1]=lazy_2[index];
        tree[index<<1|1]=tree[index];
        lazy_1[index<<1|1]=0; lazy_2[index<<1|1]=lazy_2[index];
        lazy_2[index]=-inf;
    }
}

void update_add(int index, int s, int e, int l, int r, ll v)
{
    if(l>e || r<s) return;
    workdown(index, s, e);
    if(l<=s && e<=r)
    {
        lazy_1[index]+=v;
        tree[index]+=v;
        return;
    }
    int m=(s+e)>>1;
    update_add(index<<1, s, m, l, r, v);
    update_add(index<<1|1, m+1, e, l, r, v);
    tree[index]=max(tree[index<<1], tree[index<<1|1]);
}

void update_repl(int index, int s, int e, int l, int r, ll v)
{
    if(l>e || r<s) return;
    workdown(index, s, e);
    if(l<=s && e<=r)
    {
        lazy_2[index]=v;
        tree[index]=v;
        return;
    }
    int m=(s+e)>>1;
    update_repl(index<<1, s, m, l, r, v);
    update_repl(index<<1|1, m+1, e, l, r, v);
    tree[index]=max(tree[index<<1], tree[index<<1|1]);
}

ll query(int index, int s, int e, int loc)
{
    if(s>loc || e<loc) return -inf;
    workdown(index, s, e);
    if(s==loc && e==loc) return tree[index];
    int m=(s+e)>>1;
    if(loc<=m) return query(index<<1, s, m, loc);
    else return query(index<<1|1, m+1, e, loc);
}

ll find_larger(int index, int s, int e, ll v)
{
    workdown(index, s, e);
    if(tree[index]<v) return M+1;
    int m=(s+e)>>1; if(s==e) return m;
    if(tree[index<<1]>=v) return find_larger(index<<1, s, m, v);
    else return find_larger(index<<1|1, m+1, e, v);
}

int main(void)
{
    fio; ll i, j, v, loc; cin>>N>>M;
    for(i=0 ; i<=4444440 ; i++) lazy_2[i]=-inf;
    for(i=1 ; i<=N ; i++) cin>>A[i]>>S[i]>>P[i];
    for(i=1 ; i<=M ; i++) cin>>B[i]>>T[i]>>Q[i];
    for(i=1 ; i<=N ; i++) PA[i]=PA[i-1]+A[i];
    for(i=1 ; i<=M ; i++) PB[i]=PB[i-1]+B[i];
    for(i=1 ; i<=N ; i++)
    {
        if(PA[i]>S[i]) { f[i]=-1; continue; }
        j=upper_bound(PB+1, PB+M+1, S[i]-PA[i])-PB; f[i]=j-1; 
    }
    for(i=1 ; i<=M ; i++)
    {
        if(PB[i]>T[i]) { g[i]=-1; continue; }
        j=upper_bound(PA+1, PA+N+1, T[i]-PB[i])-PA; g[i]=j-1;
    }
    for(i=1 ; i<=N ; i++)
    {
        if(f[i]==-1) continue;
        upd[i].push_back(make_pair(f[i], P[i]));
    }
    for(i=1 ; i<=M ; i++)
    {
        if(g[i]==-1) continue; ans+=Q[i];
        upd[g[i]+1].push_back(make_pair(i-1, -Q[i]));
    }
    upd[N+1].push_back(make_pair(M-1, -inf));
    for(i=1 ; i<=N+1 ; i++) sort(upd[i].begin(), upd[i].end());
    for(i=1 ; i<=N+1 ; i++)
    {
        for(j=0 ; j<upd[i].size() ; j++)
            update_add(1, 0, M, 0, upd[i][j].first, upd[i][j].second);
        for(j=0 ; j<upd[i].size() ; j++)
        {
            v=query(1, 0, M, upd[i][j].first);
            loc=find_larger(1, 0, M, v+1); loc--;
            if(j+1<upd[i].size()) loc=min(loc, upd[i][j+1].first);
            else loc=min(loc, M);
            if(loc>=upd[i][j].first+1) update_repl(1, 0, M, upd[i][j].first+1, loc, v);
        }
    }
    ans+=query(1, 0, M, M);
    cout<<ans; return 0;
}

Compilation message (stderr)

dishes.cpp: In function 'int main()':
dishes.cpp:123:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
         if(g[i]==-1) continue; ans+=Q[i];
         ^~
dishes.cpp:123:32: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
         if(g[i]==-1) continue; ans+=Q[i];
                                ^~~
dishes.cpp:130:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(j=0 ; j<upd[i].size() ; j++)
                   ~^~~~~~~~~~~~~~
dishes.cpp:132:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(j=0 ; j<upd[i].size() ; j++)
                   ~^~~~~~~~~~~~~~
dishes.cpp:136:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(j+1<upd[i].size()) loc=min(loc, upd[i][j+1].first);
                ~~~^~~~~~~~~~~~~~

• 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