Submission #1038955

#	Time	Username	Problem	Language	Result	Execution time	Memory
1038955		ibm2006	Two Dishes (JOI19_dishes)	C++17	100 / 100	3369 ms	268396 KiB

dishes

#include<bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
typedef long long int ll;
const ll inf=1e18;
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<pair<int,int>> chain;
pair<ll,ll> p,q;
#include <cassert>
#include <cstdio>
#include <cinttypes>
#include <unistd.h>
#include <sys/stat.h>
#include <sys/mman.h>
class strictInput
{
	char *p;
	off_t cur = 0;
	off_t len = 0;

public:
	explicit strictInput(int fd = 0)
	{
		struct stat st;
		fstat(fd, &st);
		p = (char *)mmap(NULL, st.st_size, PROT_READ, MAP_SHARED, fd, 0);
		len = st.st_size;
	}

	char readChar()
	{
		assert(cur != len);
		return p[cur++];
	}

	void unreadChar()
	{
		assert(cur != 0);
		--cur;
	}

	bool isEOF() { return cur == len; }
	void readEOF() { assert(isEOF()); }
	void readSpace() { assert(readChar() == ' '); }
	void readEoln() { assert(readChar() == '\n'); }

	// reads uint64_t in range [from, to]
	uint64_t readU64(uint64_t from = 0, uint64_t to = UINT64_MAX)
	{
		uint64_t cur = 0;
		off_t read_cnt = 0;
		bool leading_zero = false;
		while (!isEOF())
		{
			char p = readChar();
			if (!('0' <= p && p <= '9'))
			{
				unreadChar();
				break;
			}
			uint64_t v = p - '0';
			assert(cur <= UINT64_MAX / 10);
			cur *= 10;
			assert(cur <= UINT64_MAX - v);
			cur += v;
			if (read_cnt == 0 && v == 0)
				leading_zero = true;
			++read_cnt;
		}
		if (cur == 0)
			assert(read_cnt == 1);
		else
			assert(!leading_zero);
		return cur;
	}

	// reads int64_t in range [from, to]
	int64_t readI64(int64_t from = INT64_MIN, int64_t to = INT64_MAX)
	{
		uint64_t cur = 0;
		off_t read_cnt = 0;
		bool leading_zero = false;
		bool leading_minus = readChar() == '-';
		if (!leading_minus)
			unreadChar();
		while (!isEOF())
		{
			char p = readChar();
			if (!('0' <= p && p <= '9'))
			{
				unreadChar();
				break;
			}
			uint64_t v = p - '0';
			assert(cur <= UINT64_MAX / 10);
			cur *= 10;
			assert(cur <= UINT64_MAX - v);
			cur += v;
			if (read_cnt == 0 && v == 0)
				leading_zero = true;
			++read_cnt;
		}
		if (cur == 0)
			assert(read_cnt == 1 && !leading_minus);
		else
			assert(!leading_zero);

		if (cur <= INT64_MAX)
		{
			int64_t ret = cur;
			if (leading_minus)
				ret = -ret;
			return ret;
		}
		else
		{
			assert(leading_minus && cur == uint64_t(INT64_MIN));
			return INT64_MIN;
		}
	}
};

pair<int,int> find_chain(int x)
{
    pair<int,int> p=*(--chain.lower_bound(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(ll x)
{
    while(x)
    {seg[x]=seg[x<<1]+seg[(x<<1)+1];
    x>>=1;
    }
}
/*ll g(ll x,ll y,ll z)
{
    if(y<l||x>r)
        return 0;
    if(l<=x&&y<=r)
        return seg[z];
    return g(x,(x+y)>>1,z<<1)+g(((x+y)>>1)+1,y,(z<<1)+1);
}*/
ll g(ll x,ll y,ll z) {
	x=l;
	y=r;
	ll res = 0;
	for(x+=1048575,y+=1048575; 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+1048575]+=z;
    f((l+1048575)/2);
    l=y+2;
    seg[l+1048575]-=z;
    f((l+1048575)/2);
}
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(p)!=chain.end())
    {
        pair<int,int> q=(*chain.upper_bound(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(p);
            chain.erase(q);
            chain.insert({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");
}
void init(){
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(false);
}*/
int main()
{
    strictInput inp;
    //cin >> n >> m;
    n=inp.readI64(-inf,inf);
    inp.readSpace();
    m=inp.readI64(-inf,inf);
    inp.readEoln();
    for(i=1;i<=n;i++)
    {
       // scanf("%lld %lld %lld",&a[i],&c[i],&add_cost[i]);
        //cin >> a[i] >> c[i] >> add_cost[i];
        a[i]=inp.readI64(-inf,inf);inp.readSpace();
        c[i]=inp.readI64(-inf,inf);inp.readSpace();
        add_cost[i]=inp.readI64(-inf,inf);inp.readEoln();
        sum1[i]=sum1[i-1]+a[i];
    }
    for(i=1;i<=m;i++)
    {
        //scanf("%lld %lld %lld",&b[i],&d[i],&cost[i-1]);
        //cin >> b[i] >> d[i] >> cost[i-1];
        b[i]=inp.readI64(-inf,inf);inp.readSpace();
        d[i]=inp.readI64(-inf,inf);inp.readSpace();
        cost[i-1]=inp.readI64(-inf,inf);inp.readEoln();
        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({0,m});
    for(i=1;i<=n;i++)
    {
    v.clear();
        for(auto xx:del_list[i])
        {
            p=find_chain(xx);
            chain.erase(p);
            chain.insert({p.first,xx});
            if(xx+1<=p.second)
            chain.insert({xx+1,p.second});
            cost[xx]=0;
            v.push_back(xx);
        }
        x=range[i];
        p=find_chain(x);
        if(x>=0)
        {
            chain.erase(p);
            chain.insert({p.first,x});
            if(x+1<=p.second)
            chain.insert({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;
    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:328: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]
  328 |         for(j=0;j<v.size();j++)
      |                 ~^~~~~~~~~

• 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