Submission #133376

#	Time	Username	Problem	Language	Result	Execution time	Memory
133376		TadijaSebez	Two Dishes (JOI19_dishes)	C++11	0 / 100	629 ms	75732 KiB

dishes

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
const int N=1000050;
const int M=2*N;
const ll inf=1e18;
ll a[N],s[N],p[N],b[N],t[N],q[N];
vector<pair<ll,ll>> Qs[N];
//Segment Tree Beats
int ls[M],rs[M],tsz,root;
ll mx[M],lzy_add[M],lzy[M],fir[M],sec[M];
void Build(int &c, int ss, int se)
{
	c=++tsz;mx[c]=0;lzy_add[c]=0;lzy[c]=-inf;fir[c]=0;sec[c]=inf;
	if(ss==se) return;
	int mid=ss+se>>1;
	Build(ls[c],ss,mid);
	Build(rs[c],mid+1,se);
}
void upd(int c, ll add, ll x)
{
	fir[c]+=add;sec[c]+=add;
	fir[c]=max(fir[c],x);
	sec[c]=max(sec[c],x);
	lzy_add[c]+=add;
	lzy[c]+=add;
	lzy[c]=max(lzy[c],x);
}
void push(int c)
{
	upd(ls[c],lzy_add[c],lzy[c]);
	upd(rs[c],lzy_add[c],lzy[c]);
	lzy_add[c]=0;
	lzy[c]=-inf;
}
void pull(int c)
{
	if(fir[ls[c]]>fir[rs[c]])
	{
		fir[c]=fir[rs[c]];
		sec[c]=min(fir[ls[c]],sec[rs[c]]);
	}
	else if(fir[ls[c]]<fir[rs[c]])
	{
		fir[c]=fir[ls[c]];
		sec[c]=min(sec[ls[c]],fir[rs[c]]);
	}
	else
	{
		fir[c]=fir[ls[c]];
		sec[c]=min(sec[ls[c]],sec[rs[c]]);
	}
}
void Add(int c, int ss, int se, int qs, int qe, ll add)
{
	if(qs>qe || qs>se || ss>qe) return;
	if(qs<=ss && qe>=se){ upd(c,add,-inf);return;}
	push(c);
	int mid=ss+se>>1;
	Add(ls[c],ss,mid,qs,qe,add);
	Add(rs[c],mid+1,se,qs,qe,add);
	pull(c);
}
void Set(int c, int ss, int se, int qs, int qe, ll x)
{
	if(qs>qe || qs>se || ss>qe || fir[c]>=x) return;
	if(qs<=ss && qe>=se && sec[c]>x){ upd(c,0,x);return;}
	push(c);
	int mid=ss+se>>1;
	Set(ls[c],ss,mid,qs,qe,x);
	Set(rs[c],mid+1,se,qs,qe,x);
	pull(c);
}
ll Get(int c, int ss, int se, int qi)
{
	if(ss==se) return fir[c];
	push(c);
	int mid=ss+se>>1;
	if(qi<=mid) return Get(ls[c],ss,mid,qi);
	else return Get(rs[c],mid+1,se,qi);
}
int main()
{
	int n,m;
	scanf("%i %i",&n,&m);
	for(int i=1;i<=n;i++) scanf("%lld %lld %lld",&a[i],&s[i],&p[i]),a[i]+=a[i-1];
	for(int i=1;i<=m;i++) scanf("%lld %lld %lld",&b[i],&t[i],&q[i]),b[i]+=b[i-1];
	ll sum=0;
	Build(root,0,m);
	for(int i=1;i<=m;i++)
	{
		t[i]=upper_bound(a,a+1+n,t[i]-b[i])-a;
		if(t[i])
		{
			sum+=q[i];
			Qs[t[i]].pb({i,-q[i]});
		}
	}
	for(int i=1;i<=n;i++)
	{
		s[i]=upper_bound(b,b+1+m,s[i]-a[i])-b;
		if(s[i]) Qs[i].pb({s[i],p[i]});
		sort(Qs[i].rbegin(),Qs[i].rend());
		for(auto qu:Qs[i])
		{
			int p=qu.first-1;
			ll f=qu.second;
			Add(root,0,m,0,p,f);
			ll g=Get(root,0,m,p);
			Set(root,0,m,p+1,m,g);
		}
	}
	printf("%lld\n",Get(root,0,m,m)+sum);
	return 0;
}

Compilation message (stderr)

dishes.cpp: In function 'void Build(int&, int, int)':
dishes.cpp:17:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=ss+se>>1;
          ~~^~~
dishes.cpp: In function 'void Add(int, int, int, int, int, long long int)':
dishes.cpp:60:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=ss+se>>1;
          ~~^~~
dishes.cpp: In function 'void Set(int, int, int, int, int, long long int)':
dishes.cpp:70:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=ss+se>>1;
          ~~^~~
dishes.cpp: In function 'long long int Get(int, int, int, int)':
dishes.cpp:79:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=ss+se>>1;
          ~~^~~
dishes.cpp: In function 'int main()':
dishes.cpp:86:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i",&n,&m);
  ~~~~~^~~~~~~~~~~~~~~
dishes.cpp:87:65: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;i++) scanf("%lld %lld %lld",&a[i],&s[i],&p[i]),a[i]+=a[i-1];
                        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~
dishes.cpp:88:65: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=m;i++) scanf("%lld %lld %lld",&b[i],&t[i],&q[i]),b[i]+=b[i-1];
                        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~

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