oj.uz

답안 #136521

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
136521 2019-07-25T12:20:06 Z TadijaSebez Two Dishes (JOI19_dishes) C++11
0 / 100
 1910 ms 69420 KB 
#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];
struct SegmentTreeBeats
{
	int root,tsz,ls[M],rs[M],n;
	ll fir[M],sec[M],lzy[M],lzy_add[M];
	SegmentTreeBeats(){}
	void upd(int c, ll add, ll x)
	{
		fir[c]+=add;
		sec[c]+=add;
		fir[c]=max(fir[c],x);
		lzy_add[c]+=add;
		if(lzy[c]!=-inf) lzy[c]+=add;
		lzy[c]=max(lzy[c],x);
	}
	void push(int c)
	{
		if(lzy_add[c]!=0 || lzy[c]!=-inf)
		{
			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)
	{
		set<ll> st;
		st.insert(fir[ls[c]]);
		st.insert(sec[ls[c]]);
		st.insert(fir[rs[c]]);
		st.insert(sec[rs[c]]);
		auto it=st.begin();
		fir[c]=*it;
		it++;
		sec[c]=*it;
	}
	void Build(int &c, int ss, int se)
	{
		c=++tsz;fir[c]=0;sec[c]=inf;lzy_add[c]=0;lzy[c]=-inf;
		if(ss==se) return;
		int mid=ss+se>>1;
		Build(ls[c],ss,mid);
		Build(rs[c],mid+1,se);
	}
	void Add(int c, int ss, int se, int qs, int qe, ll f)
	{
		if(qs>qe || qs>se || ss>qe) return;
		if(qs<=ss && qe>=se){ upd(c,f,-inf);return;}
		push(c);
		int mid=ss+se>>1;
		Add(ls[c],ss,mid,qs,qe,f);
		Add(rs[c],mid+1,se,qs,qe,f);
		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);
	}
	void init(int _n){ n=_n;Build(root,0,n);}
	void Add(int qs, int qe, ll f){ Add(root,0,n,qs,qe,f);}
	void Set(int qs, int qe, ll x){ Set(root,0,n,qs,qe,x);}
	ll Get(int qi){ return Get(root,0,n,qi);}
} STB;
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;
	STB.init(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;
			STB.Add(0,p,f);
			ll g=STB.Get(p);
			STB.Set(p-1,m,g);
		}
	}
	printf("%lld\n",STB.Get(m)+sum);
	return 0;
}

Compilation message

dishes.cpp: In member function 'void SegmentTreeBeats::Build(int&, int, int)':
dishes.cpp:50:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid=ss+se>>1;
           ~~^~~
dishes.cpp: In member function 'void SegmentTreeBeats::Add(int, int, int, int, int, long long int)':
dishes.cpp:59:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid=ss+se>>1;
           ~~^~~
dishes.cpp: In member function 'void SegmentTreeBeats::Set(int, int, int, int, int, long long int)':
dishes.cpp:69:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid=ss+se>>1;
           ~~^~~
dishes.cpp: In member function 'long long int SegmentTreeBeats::Get(int, int, int, int)':
dishes.cpp:78:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid=ss+se>>1;
           ~~^~~
dishes.cpp: In function 'int main()':
dishes.cpp:90: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:91: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:92: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.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1831 ms 58364 KB Output is correct
2 Incorrect 1910 ms 69420 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 24 ms 23928 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 24 ms 23928 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 24 ms 23928 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 24 ms 23928 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 24 ms 23928 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1831 ms 58364 KB Output is correct
2 Incorrect 1910 ms 69420 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1831 ms 58364 KB Output is correct
2 Incorrect 1910 ms 69420 KB Output isn't correct
3 Halted 0 ms 0 KB -