Submission #200278

#	Time	Username	Problem	Language	Result	Execution time	Memory
200278		arnold518	Two Dishes (JOI19_dishes)	C++14	8 / 100	489 ms	30032 KiB

dishes

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e6;
const ll INF = 1e18;

int N, M;
ll A[MAXN+10], S[MAXN+10], P[MAXN+10];
ll B[MAXN+10], T[MAXN+10], Q[MAXN+10];
int X[MAXN+10], Y[MAXN+10];
ll ans;

struct Point
{
	int x, y; ll val;
	bool operator < (const Point &p)
	{
		if(x==p.x) return y>p.y;
		return x<p.x;
	}
};
vector<Point> V;

ll tree[MAXN*4+10], maxv[MAXN*4+10], add[MAXN*4+10];

void init(int node, int tl, int tr)
{
	add[node]=0; maxv[node]=-INF; tree[node]=0;
	if(tl==tr) return;
	int mid=tl+tr>>1;
	init(node*2, tl, mid);
	init(node*2+1, mid+1, tr);
}

void busy(int node, int tl, int tr)
{
	tree[node]=max(maxv[node], tree[node])+add[node];
	if(tl!=tr)
	{
		ll a, b, c, d;
		a=maxv[node*2], b=add[node*2], c=maxv[node], d=add[node];
		c-=b; swap(b, c);
		maxv[node*2]=max(a, b); add[node*2]=c+d;

		a=maxv[node*2+1], b=add[node*2+1], c=maxv[node], d=add[node];
		c-=b; swap(b, c);
		maxv[node*2+1]=max(a, b); add[node*2+1]=c+d;
	}
	add[node]=0; maxv[node]=-INF;
}

void update1(int node, int tl, int tr, int l, int r, ll k)
{
	busy(node, tl, tr);
	if(r<tl || tr<l) return;
	if(l<=tl && tr<=r)
	{
		maxv[node]=k;
		busy(node, tl, tr);
		return;
	}
	int mid=tl+tr>>1;
	update1(node*2, tl, mid, l, r, k);
	update1(node*2+1, mid+1, tr, l, r, max(tree[node*2], k));
	tree[node]=max(tree[node*2], tree[node*2+1]);
}

void update2(int node, int tl, int tr, int l, int r, ll k)
{
	busy(node, tl, tr);
	if(r<tl || tr<l) return;
	if(l<=tl && tr<=r)
	{
		add[node]=k;
		busy(node, tl, tr);
		return;
	}
	int mid=tl+tr>>1;
	update2(node*2, tl, mid, l, r, k);
	update2(node*2+1, mid+1, tr, l, r, k);
	tree[node]=max(tree[node*2], tree[node*2+1]);
}

ll query(int node, int tl, int tr, int pos)
{
	busy(node, tl, tr);
	if(tl==tr) return tree[node];
	int mid=tl+tr>>1;
	if(pos<=mid) return query(node*2, tl, mid, pos);
	else return query(node*2+1, mid+1, tr, pos);
}

int main()
{
	int i, j, k;

	scanf("%d%d", &N, &M);
	for(i=1; i<=N; i++) scanf("%lld%lld%lld", &A[i], &S[i], &P[i]);
	for(i=1; i<=M; i++) scanf("%lld%lld%lld", &B[i], &T[i], &Q[i]);

	for(i=1; i<=N; i++) A[i]+=A[i-1];
	for(i=1; i<=M; i++) B[i]+=B[i-1];

	for(i=1; i<=N; i++) X[i]=upper_bound(B, B+M+1, S[i]-A[i])-B-1;
	for(i=1; i<=M; i++) Y[i]=upper_bound(A, A+N+1, T[i]-B[i])-A-1;

	for(i=1; i<=N; i++) ans+=P[i];
	for(i=1; i<=N; i++) if(X[i]+1<=M) V.push_back({i-1, X[i]+1, -P[i]});
	for(i=1; i<=M; i++) if(Y[i]>=0) V.push_back({Y[i], i, Q[i]});

	sort(V.begin(), V.end());
	
	init(1, 0, M);
	for(j=0; j<V.size(); j++)
	{
		if(j+1<V.size() && V[j].x==V[j+1].x && V[j].y==V[j+1].y) { V[j+1].val+=V[j].val; continue; }
		Point it=V[j];
		
		//D[0]=C[0]; for(i=1; i<=M; i++) D[i]=max(D[i-1], C[i]);
		//for(i=it.y; i<=M; i++) C[i]=D[i]+it.val;

		update1(1, 0, M, it.y, M, -INF);
		update2(1, 0, M, it.y, M, it.val);
	}
	ans+=query(1, 0, M, M);
	printf("%lld\n", ans);
}

Compilation message (stderr)

dishes.cpp: In function 'void init(int, int, int)':
dishes.cpp:34:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=tl+tr>>1;
          ~~^~~
dishes.cpp: In function 'void update1(int, int, int, int, int, ll)':
dishes.cpp:66:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=tl+tr>>1;
          ~~^~~
dishes.cpp: In function 'void update2(int, int, int, int, int, ll)':
dishes.cpp:82:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=tl+tr>>1;
          ~~^~~
dishes.cpp: In function 'll query(int, int, int, int)':
dishes.cpp:92:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=tl+tr>>1;
          ~~^~~
dishes.cpp: In function 'int main()':
dishes.cpp:118:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(j=0; j<V.size(); j++)
           ~^~~~~~~~~
dishes.cpp:120:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(j+1<V.size() && V[j].x==V[j+1].x && V[j].y==V[j+1].y) { V[j+1].val+=V[j].val; continue; }
      ~~~^~~~~~~~~
dishes.cpp:99:12: warning: unused variable 'k' [-Wunused-variable]
  int i, j, k;
            ^
dishes.cpp:101:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &M);
  ~~~~~^~~~~~~~~~~~~~~~
dishes.cpp:102:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(i=1; i<=N; i++) scanf("%lld%lld%lld", &A[i], &S[i], &P[i]);
                      ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dishes.cpp:103:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(i=1; i<=M; i++) scanf("%lld%lld%lld", &B[i], &T[i], &Q[i]);
                      ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 3 / 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