oj.uz

답안 #163569

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
163569 2019-11-13T22:27:15 Z TadijaSebez Two Dishes (JOI19_dishes) C++14
0 / 100
 683 ms 55748 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
const int N=1e6+50;
const int M=2*N;
const ll inf=3e18;
ll ckmx(ll &a, ll b){ return a=max(a,b);}
int ls[M],rs[M],tsz,root;
ll lzy[M][2],mx[M];
void Upd(int c, ll x, int t){ t==0?mx[c]+=x,lzy[c][0]+=x,lzy[c][1]+=x:ckmx(mx[c],x),ckmx(lzy[c][1],x);}
void Push(int c)
{
	Upd(ls[c],lzy[c][0],0);Upd(ls[c],lzy[c][1],1);
	Upd(rs[c],lzy[c][0],0);Upd(rs[c],lzy[c][1],1);
	lzy[c][0]=0;lzy[c][1]=-inf;
}
void Set(int c, int ss, int se, int qs, int qe, ll x, int t)
{
	if(qs>qe || qs>se || ss>qe) return;
	if(qs<=ss && qe>=se) return Upd(c,x,t);
	int mid=ss+se>>1;Push(c);
	Set(ls[c],ss,mid,qs,qe,x,t);
	Set(rs[c],mid+1,se,qs,qe,x,t);
	mx[c]=max(mx[ls[c]],mx[rs[c]]);
}
ll Get(int c, int ss, int se, int qi)
{
	if(ss==se) return mx[c];
	int mid=ss+se>>1;Push(c);
	return qi<=mid?Get(ls[c],ss,mid,qi):Get(rs[c],mid+1,se,qi);
}
void Build(int &c, int ss, int se)
{
	c=++tsz;mx[c]=lzy[c][0]=0;lzy[c][1]=-inf;
	if(ss==se) return;
	int mid=ss+se>>1;
	Build(ls[c],ss,mid);
	Build(rs[c],mid+1,se);
}
ll a[N],s[N],p[N],b[N],t[N],q[N];
vector<pair<int,ll>> Us[N];
int main()
{
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int n,m;
	cin>>n>>m;
	for(int i=0;i<n;i++) cin>>a[i+1]>>s[i]>>p[i],a[i+1]+=a[i];
	for(int i=0;i<m;i++) cin>>b[i+1]>>t[i]>>q[i],b[i+1]+=b[i];
	for(int i=0;i<n;i++)
	{
		int j=upper_bound(b,b+m+1,s[i]-a[i+1])-b-1;
		if(j>=0) Us[j].pb({i+1,p[i]});
	}
	ll sum=0;
	for(int i=0;i<m;i++)
	{
		sum+=q[i];
		int j=upper_bound(a,a+n+1,t[i]-b[i+1])-a-1;
		if(j<n) Us[i].pb({j+1,-q[i]});
	}
	Build(root,0,n);
	for(int i=0;i<=m;i++)
	{
		for(auto u:Us[i]) Set(root,0,n,u.first,n,u.second,0);
		if(i==m) break;
		for(auto u:Us[i]) if(u.first) Set(root,0,n,u.first,n,Get(root,0,n,u.first-1),1);
	}
	cout<<sum+Get(root,0,n,n)<<endl;
	return 0;
}

Compilation message

dishes.cpp: In function 'void Set(int, int, int, int, int, long long int, int)':
dishes.cpp:22:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=ss+se>>1;Push(c);
          ~~^~~
dishes.cpp: In function 'long long int Get(int, int, int, int)':
dishes.cpp:30:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=ss+se>>1;Push(c);
          ~~^~~
dishes.cpp: In function 'void Build(int&, int, int)':
dishes.cpp:37:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=ss+se>>1;
          ~~^~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 3.0

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

Subtask #3
0 / 7.0

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

Subtask #4
0 / 39.0

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

Subtask #5
0 / 11.0

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

Subtask #6
0 / 9.0

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

Subtask #7
0 / 17.0

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

Subtask #8
0 / 9.0

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