Submission #1038896

#	Time	Username	Problem	Language	Result	Execution time	Memory
1038896		ibm2006	Two Dishes (JOI19_dishes)	C++17	100 / 100	3626 ms	253524 KiB

dishes

#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("avx")
using namespace std;
typedef long long int ll;
const ll inf=1e18;
const ll siz=1048575;
ll n,m,i,j,k,l,r,x,y,z,w,t,range[1100000];
ll sum1[1100000],sum2[1100000],dp[1100000],add_cost[1100000],cost[1100000],c[1100000],d[1100000],seg[2200000],lazy[2200000],a[1100000],b[1100000],s;
vector<int> del_list[1100000],v;
set<ll> chain;
pair<ll,ll> p,q;
ll ptl(pair<ll,ll> p)
{
    return p.first*10000000+p.second;
}
pair<ll,ll> ltp(ll x)
{
    return {x/10000000,x%10000000};
}
pair<int,int> find_chain(int x)
{
    pair<int,int> p=ltp(*(--chain.lower_bound(ptl((make_pair(x,m+10))))));
    return p;
}
/*void propagate(int x,int y,int z)
{
    if(z<1048576)
    {
        lazy[z*2]+=lazy[z];
        lazy[z*2+1]+=lazy[z];
    }
    seg[z]+=lazy[z];
    lazy[z]=0;
}
void f(int x,int y,int z,ll w)
{
    propagate(x,y,z);
    if(y<l||x>r)
        return;
    if(l<=x&&y<=r)
    {
        lazy[z]+=w;
        propagate(x,y,z);
        return;
    }
    f(x,(x+y)/2,z*2,w);
    f((x+y)/2+1,y,z*2+1,w);
    seg[z]=max(seg[z*2],seg[z*2+1]);
}
ll g(int x,int y,int z)
{
    propagate(x,y,z);
    if(y<l||x>r)
    {
        return -inf;
    }
    if(l<=x&&y<=r)
    {
        return seg[z];
    }
    return max(g(x,(x+y)/2,z*2),g((x+y)/2+1,y,z*2+1));
}*/
void f(int x)
{
    while(x)
    {seg[x]=seg[x<<1]+seg[(x<<1)+1];
    x>>=1;
    }
}
ll g(int x,int y,int z) {
	x=l;
	y=r;
	ll res = 0;
	for(x+=siz,y+=siz; x<=y; x>>=1,y>>=1) {
    	if(x&1) res += seg[x--];
        if(~y&1) res += seg[y--];
    }
    return res;
}
void add(int x,int y,ll z)
{
    /*l=x+1;
    r=y+1;
    f(1,1048576,1,z);*/
    l=x+1;
    seg[l+siz]+=z;
    f((l+siz)>>1);
    l=y+2;
    seg[l+siz]-=z;
    f((l+siz)>>1);
}
ll get_val(int x)
{
    //l=x+1;
    l=1;
    r=x+1;
    return g(1,1048576,1);
}
void reconstruct_chain(int x)
{
    pair<int,int> p=find_chain(x);
    while(chain.upper_bound(ptl(p))!=chain.end())
    {
        pair<int,int> q=ltp(*chain.upper_bound(ptl(p)));
        y=get_val(p.second);
        z=get_val(q.first);
        //printf("(%lld,%lld,%lld,%lld)\n",p.first,p.second,q.first,q.second);
        if(z<=y+cost[p.second])
        {
            add(q.first,q.second,y+cost[p.second]-z);
            chain.erase(ptl(p));
            chain.erase(ptl(q));
            chain.insert(ptl({p.first,q.second}));
            p.second=q.second;
        }
        else
            return;
    }
}
void show()
{
    return;
    ll i;
    for(i=0;i<=m;i++)
        printf("%lld ",get_val(i));
    printf("\n");
}
int main()
{
    scanf("%d %d",&n,&m);
    for(i=1;i<=n;i++)
    {
        scanf("%lld %lld %lld",&a[i],&c[i],&add_cost[i]);
        sum1[i]=sum1[i-1]+a[i];
    }
    for(i=1;i<=m;i++)
    {
        scanf("%lld %lld %lld",&b[i],&d[i],&cost[i-1]);
        sum2[i]=sum2[i-1]+b[i];
    }
    for(i=1;i<=n;i++)
    {
        range[i]=upper_bound(sum2,sum2+m+1,c[i]-sum1[i])-sum2-1;
        //printf("(%lld) ",range[i]);
    }
    //printf("\n");
    for(i=1;i<=m;i++)
    {
        x=upper_bound(sum1,sum1+n+1,d[i]-sum2[i])-sum1;
        del_list[x].push_back(i-1);
        //printf("(%lld)",x);
    }
    //printf("\n");
    for(auto xx:del_list[0])
    {
        cost[xx]=0;
    }
    for(i=1;i<=m;i++)
    {
        dp[i]=dp[i-1]+cost[i-1];
    }
    for(i=0;i<=m;i++)
    {
        add(i,i,dp[i]);
    }
    /*for(i=0;i<=m;i++)
    {
        printf("(%lld)",cost[i]);
    }
    printf("\n");
    */chain.insert(ptl({0,m}));
    for(i=1;i<=n;i++)
    {show();
    v.clear();
        for(auto xx:del_list[i])
        {
            p=find_chain(xx);
            chain.erase(ptl(p));
            chain.insert(ptl({p.first,xx}));
            if(xx+1<=p.second)
            chain.insert(ptl({xx+1,p.second}));
            cost[xx]=0;
            v.push_back(xx);
        }
        x=range[i];
        p=find_chain(x);
        if(x>=0)
        {
            chain.erase(ptl(p));
            chain.insert(ptl({p.first,x}));
            if(x+1<=p.second)
            chain.insert(ptl({x+1,p.second}));
            add(0,x,add_cost[i]);
        v.push_back(x);
        }
        sort(v.begin(),v.end());
        for(j=0;j<v.size();j++)
            reconstruct_chain(v[j]);
    }
    s=-inf;
    show();
    for(i=m;i<=m;i++)
    {
        s=max(s,get_val(i));
    }
    printf("%lld",s);
}

Compilation message (stderr)

dishes.cpp: In function 'int main()':
dishes.cpp:131:13: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'll*' {aka 'long long int*'} [-Wformat=]
  131 |     scanf("%d %d",&n,&m);
      |            ~^     ~~
      |             |     |
      |             int*  ll* {aka long long int*}
      |            %lld
dishes.cpp:131:16: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'll*' {aka 'long long int*'} [-Wformat=]
  131 |     scanf("%d %d",&n,&m);
      |               ~^     ~~
      |                |     |
      |                int*  ll* {aka long long int*}
      |               %lld
dishes.cpp:198:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  198 |         for(j=0;j<v.size();j++)
      |                 ~^~~~~~~~~
dishes.cpp:131:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  131 |     scanf("%d %d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~~
dishes.cpp:134:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  134 |         scanf("%lld %lld %lld",&a[i],&c[i],&add_cost[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dishes.cpp:139:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  139 |         scanf("%lld %lld %lld",&b[i],&d[i],&cost[i-1]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• 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