oj.uz

Submission #200278

# Submission time Handle Problem Language Result Execution time Memory
200278 2020-02-06T02:18:28 Z arnold518 Two Dishes (JOI19_dishes) C++14
8 / 100
 489 ms 30032 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 489 ms 29776 KB Output is correct
2 Correct 478 ms 29520 KB Output is correct
3 Correct 402 ms 26972 KB Output is correct
4 Correct 370 ms 28496 KB Output is correct
5 Correct 5 ms 380 KB Output is correct
6 Correct 469 ms 28624 KB Output is correct
7 Correct 253 ms 21084 KB Output is correct
8 Correct 111 ms 5880 KB Output is correct
9 Correct 381 ms 26972 KB Output is correct
10 Correct 388 ms 30032 KB Output is correct
11 Correct 333 ms 26976 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 380 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 380 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 5 ms 376 KB Output is correct
12 Correct 5 ms 376 KB Output is correct
13 Correct 5 ms 376 KB Output is correct
14 Correct 5 ms 376 KB Output is correct
15 Correct 5 ms 376 KB Output is correct
16 Correct 5 ms 376 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 380 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 380 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 5 ms 376 KB Output is correct
12 Correct 5 ms 376 KB Output is correct
13 Correct 5 ms 376 KB Output is correct
14 Correct 5 ms 376 KB Output is correct
15 Correct 5 ms 376 KB Output is correct
16 Correct 5 ms 376 KB Output is correct
17 Correct 9 ms 760 KB Output is correct
18 Correct 9 ms 936 KB Output is correct
19 Correct 10 ms 760 KB Output is correct
20 Incorrect 8 ms 760 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 380 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 380 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 5 ms 376 KB Output is correct
12 Correct 5 ms 376 KB Output is correct
13 Correct 5 ms 376 KB Output is correct
14 Correct 5 ms 376 KB Output is correct
15 Correct 5 ms 376 KB Output is correct
16 Correct 5 ms 376 KB Output is correct
17 Correct 9 ms 760 KB Output is correct
18 Correct 9 ms 936 KB Output is correct
19 Correct 10 ms 760 KB Output is correct
20 Incorrect 8 ms 760 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 380 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 380 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 5 ms 376 KB Output is correct
12 Correct 5 ms 376 KB Output is correct
13 Correct 5 ms 376 KB Output is correct
14 Correct 5 ms 376 KB Output is correct
15 Correct 5 ms 376 KB Output is correct
16 Correct 5 ms 376 KB Output is correct
17 Correct 9 ms 760 KB Output is correct
18 Correct 9 ms 936 KB Output is correct
19 Correct 10 ms 760 KB Output is correct
20 Incorrect 8 ms 760 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 380 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 380 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 5 ms 376 KB Output is correct
12 Correct 5 ms 376 KB Output is correct
13 Correct 5 ms 376 KB Output is correct
14 Correct 5 ms 376 KB Output is correct
15 Correct 5 ms 376 KB Output is correct
16 Correct 5 ms 376 KB Output is correct
17 Correct 9 ms 760 KB Output is correct
18 Correct 9 ms 936 KB Output is correct
19 Correct 10 ms 760 KB Output is correct
20 Incorrect 8 ms 760 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #7
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 489 ms 29776 KB Output is correct
2 Correct 478 ms 29520 KB Output is correct
3 Correct 402 ms 26972 KB Output is correct
4 Correct 370 ms 28496 KB Output is correct
5 Correct 5 ms 380 KB Output is correct
6 Correct 469 ms 28624 KB Output is correct
7 Correct 253 ms 21084 KB Output is correct
8 Correct 111 ms 5880 KB Output is correct
9 Correct 381 ms 26972 KB Output is correct
10 Correct 388 ms 30032 KB Output is correct
11 Correct 333 ms 26976 KB Output is correct
12 Correct 5 ms 376 KB Output is correct
13 Correct 5 ms 376 KB Output is correct
14 Correct 5 ms 380 KB Output is correct
15 Correct 5 ms 376 KB Output is correct
16 Correct 5 ms 376 KB Output is correct
17 Correct 5 ms 380 KB Output is correct
18 Correct 5 ms 376 KB Output is correct
19 Correct 5 ms 376 KB Output is correct
20 Correct 5 ms 376 KB Output is correct
21 Correct 5 ms 376 KB Output is correct
22 Correct 5 ms 376 KB Output is correct
23 Correct 5 ms 376 KB Output is correct
24 Correct 5 ms 376 KB Output is correct
25 Correct 5 ms 376 KB Output is correct
26 Correct 5 ms 376 KB Output is correct
27 Correct 5 ms 376 KB Output is correct
28 Correct 9 ms 760 KB Output is correct
29 Correct 9 ms 936 KB Output is correct
30 Correct 10 ms 760 KB Output is correct
31 Incorrect 8 ms 760 KB Output isn't correct
32 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 489 ms 29776 KB Output is correct
2 Correct 478 ms 29520 KB Output is correct
3 Correct 402 ms 26972 KB Output is correct
4 Correct 370 ms 28496 KB Output is correct
5 Correct 5 ms 380 KB Output is correct
6 Correct 469 ms 28624 KB Output is correct
7 Correct 253 ms 21084 KB Output is correct
8 Correct 111 ms 5880 KB Output is correct
9 Correct 381 ms 26972 KB Output is correct
10 Correct 388 ms 30032 KB Output is correct
11 Correct 333 ms 26976 KB Output is correct
12 Correct 5 ms 376 KB Output is correct
13 Correct 5 ms 376 KB Output is correct
14 Correct 5 ms 380 KB Output is correct
15 Correct 5 ms 376 KB Output is correct
16 Correct 5 ms 376 KB Output is correct
17 Correct 5 ms 380 KB Output is correct
18 Correct 5 ms 376 KB Output is correct
19 Correct 5 ms 376 KB Output is correct
20 Correct 5 ms 376 KB Output is correct
21 Correct 5 ms 376 KB Output is correct
22 Correct 5 ms 376 KB Output is correct
23 Correct 5 ms 376 KB Output is correct
24 Correct 5 ms 376 KB Output is correct
25 Correct 5 ms 376 KB Output is correct
26 Correct 5 ms 376 KB Output is correct
27 Correct 5 ms 376 KB Output is correct
28 Correct 9 ms 760 KB Output is correct
29 Correct 9 ms 936 KB Output is correct
30 Correct 10 ms 760 KB Output is correct
31 Incorrect 8 ms 760 KB Output isn't correct
32 Halted 0 ms 0 KB -