Submission #213252

#	Time	Username	Problem	Language	Result	Execution time	Memory
213252		zscoder	Two Dishes (JOI19_dishes)	C++17	100 / 100	8130 ms	369528 KiB

dishes

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
 
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<ll> vi;
typedef unsigned long long ull;
typedef long double ld; 
typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> pbds;

vector<ll> a,b,s,p,q,t;
vector<ii> F[1001111];
const ll INF = ll(3e18);
vector<pair<ii,ll> > G[1001111];

struct node
{
	ll v;
	ll upd,add;
};

node st[4000011];

void build(int id, int l, int r)
{
	st[id].v=st[id].add=0; //i shouldn't have -ves anyway, or should I?
	st[id].upd=-INF;
	if(r-l<2) return ;
	int mid=(l+r)>>1;
	build(id*2,l,mid); build(id*2+1,mid,r);
}

void combine(int id)
{
	st[id].v=max(st[id*2].v,st[id*2+1].v);
}

void push(int id, int l, int r)
{
	if(st[id].upd!=-INF)
	{
		st[id].v=st[id].upd;
		if(r-l>=2)
		{
			st[id*2].upd=st[id].upd; st[id*2].add=0;
			st[id*2+1].upd=st[id].upd; st[id*2+1].add=0;
		}
	}
	if(st[id].add!=0)
	{
		st[id].v+=st[id].add;
		if(r-l>=2)
		{
			st[id*2].add+=st[id].add;
			st[id*2+1].add+=st[id].add; 
		}
	}
	st[id].upd=-INF; st[id].add=0;
}

void update(int id, int l, int r, int ql, int qr, ll v)
{
	push(id,l,r);
	if(ql>=r||l>=qr) return ;
	if(l>=ql&&r<=qr) 
	{
		//cerr<<l<<' '<<r<<' '<<ql<<' '<<qr<<' '<<v<<'\n';
		st[id].upd=v; st[id].add=0;
		push(id,l,r); return ;
	}
	int mid=(l+r)>>1;
	update(id*2,l,mid,ql,qr,v); update(id*2+1,mid,r,ql,qr,v);
	combine(id);
}

void add(int id, int l, int r, int ql, int qr, ll v)
{
	push(id,l,r);
	if(ql>=r||l>=qr) return ;
	if(l>=ql&&r<=qr) 
	{
		//assert(st[id].upd==-INF);
		st[id].add+=v;
		push(id,l,r); return ;
	}
	int mid=(l+r)>>1;
	add(id*2,l,mid,ql,qr,v); add(id*2+1,mid,r,ql,qr,v);
	combine(id);
}

int find_left(int id, int l, int r, ll x) //or none?
{
	push(id,l,r);
	if(st[id].v<x) return -1;
	if(r-l<2) return l;
	int mid=(l+r)>>1;
	ll val = st[id*2].v;
	if(st[id*2].upd!=-INF) val=st[id*2].upd;
	val+=st[id*2].add;
	if(val>=x)
	{
		return find_left(id*2,l,mid,x);
	}
	else
	{
		return find_left(id*2+1,mid,r,x);
	}
}

ll query(int id, int l, int r, int ql, int qr)
{
	push(id,l,r);
	if(ql>=r||l>=qr) return -INF;
	if(l>=ql&&r<=qr) return st[id].v;
	int mid=(l+r)>>1;
	return max(query(id*2,l,mid,ql,qr),query(id*2+1,mid,r,ql,qr));
}

ll dp[2111][2111];

int main()
{
	//freopen("03-03.txt","r",stdin);
	int n,m; scanf("%d %d",&n,&m);
	a.resize(n); s.resize(n); p.resize(n);
	b.resize(m); t.resize(m); q.resize(m);
	for(int i=0;i<n;i++)
	{
		scanf("%lld %lld %lld",&a[i],&s[i],&p[i]);
		if(i>0) a[i]+=a[i-1];
	}
	for(int i=0;i<m;i++)
	{
		scanf("%lld %lld %lld",&b[i],&t[i],&q[i]);
		if(i>0) b[i]+=b[i-1];
	}
	ll ans = 0;
	for(int i=0;i<m;i++)
	{
		if(b[i]>t[i]) continue;
		if(b[i]+a[n-1]<=t[i]) {ans+=q[i]; continue;}
		//min j such that b_i+a_j>t[i]
		int ptr = upper_bound(a.begin(),a.end(),t[i]-b[i])-a.begin();
		ans+=q[i];
		//cerr<<i<<' '<<ptr+1<<'\n';
		F[i].pb({ptr+1,-q[i]});
	}
	for(int i=0;i<n;i++)
	{
		if(a[i]>s[i]) continue;
		if(a[i]+b[m-1]<=s[i]){ans+=p[i]; continue;}
		int ptr = upper_bound(b.begin(),b.end(),s[i]-a[i])-b.begin();
		ptr--;
		//cerr<<ptr+1<<' '<<i+1<<' '<<p[i]<<'\n';
		F[ptr+1].pb({i+1,p[i]});
	}
	for(int i=0;i<m;i++)
	{
		sort(F[i].begin(),F[i].end());
		ll sum=0; int l=0;
		for(int j=0;j<F[i].size();j++)
		{
			//cerr<<i<<' '<<F[i][j].fi<<' '<<F[i][j].se<<'\n';
			if(j+1<F[i].size()&&F[i][j+1].fi==F[i][j].fi)
			{
				F[i][j+1].se+=F[i][j].se; continue;
			}
			if(l<=F[i][j].fi-1)
			{
				G[i].pb({{l,F[i][j].fi-1},sum});
			}
			l=F[i][j].fi;
			sum+=F[i][j].se;
		}
		if(l<=n) G[i].pb({{l,n},sum});
	}
	build(1,0,n+1);
	for(int i=0;i<m;i++)
	{
		vector<pair<ii,ii> > updates;
		ll lasnum = -INF*2;
		
		for(int j=0;j<G[i].size();j++)
		{
			int l = G[i][j].fi.fi; int r = G[i][j].fi.se; ll v = G[i][j].se;
			//cerr<<"UPDATE : "<<i<<' '<<l<<' '<<r<<' '<<v<<'\n'; cerr<<"LASNUM = "<<lasnum<<'\n';
			
			int gleft = find_left(1,0,n+1,lasnum-v+1);
			//cerr<<"GLEFT : "<<gleft<<'\n';
			if(gleft==-1) gleft=n+100;
			
			if(l<=gleft-1) updates.pb({{l,min(r,gleft-1)},{1,lasnum}});
			if(gleft<=r) updates.pb({{max(gleft,l),r},{0,v}});
			if(gleft<=r) lasnum=max(lasnum,v+query(1,0,n+1,r,r+1));
		}
		for(auto X:updates)
		{
			if(X.se.fi) update(1,0,n+1,X.fi.fi,X.fi.se+1,X.se.se); //update
			else add(1,0,n+1,X.fi.fi,X.fi.se+1,X.se.se);
		}
		
		/*
		for(int j=0;j<G[i].size();j++)
		{
			int l = G[i][j].fi.fi; int r = G[i][j].fi.se; ll v = G[i][j].se;
			for(int k=l;k<=r;k++)
			{
				dp[i+1][k]=dp[i][k]+v;
			}
		}
		for(int k=1;k<=n;k++) dp[i+1][k]=max(dp[i+1][k],dp[i+1][k-1]);
		
		bool problem=0;
		for(int j=0;j<=n;j++)
		{
			if(dp[i+1][j]!=query(1,0,n+1,j,j+1)){problem=1; break;}
		}
		if(problem)
		{
			cerr<<"ROW "<<i+1<<'\n';
			for(int j=0;j<=n;j++)
			{
				cerr<<dp[i+1][j]<<' ';
			}
			cerr<<'\n';
			for(int j=0;j<=n;j++)
			{
				cerr<<query(1,0,n+1,j,j+1)<<' ';
			}
			cerr<<'\n';
			cerr<<'\n';
		}
		*/
		/*
		for(int j=0;j<=n;j++)
		{
			query(1,0,n+1,j,j+1);
		}
		*/
	}
	//cout<<ans+dp[m][n]<<'\n';
	cout<<query(1,0,n+1,0,n+1)+ans<<'\n';
}

Compilation message (stderr)

dishes.cpp: In function 'int main()':
dishes.cpp:172:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<F[i].size();j++)
               ~^~~~~~~~~~~~
dishes.cpp:175:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(j+1<F[i].size()&&F[i][j+1].fi==F[i][j].fi)
       ~~~^~~~~~~~~~~~
dishes.cpp:194:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<G[i].size();j++)
               ~^~~~~~~~~~~~
dishes.cpp:135:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int n,m; scanf("%d %d",&n,&m);
           ~~~~~^~~~~~~~~~~~~~~
dishes.cpp:140:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld %lld",&a[i],&s[i],&p[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dishes.cpp:145:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld %lld",&b[i],&t[i],&q[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• 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