oj.uz

Submission #123385

# Submission time Handle Problem Language Result Execution time Memory
123385 2019-07-01T10:31:03 Z gs14004 Two Dishes (JOI19_dishes) C++17
74 / 100
 3631 ms 134208 KB 
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000005;
const int MAXT = 2100000;
const int mod = 1e9 + 7;
using lint = long long;
using pi = pair<int, int>;

struct pnt{
	int x, y;
	lint c;
	bool operator<(const pnt &p)const{
		return pi(x, y) < pi(p.x, p.y);
	}
};

struct seg{
	lint lazy[MAXT], tree[MAXT];
	void lazydown(int p){
		lazy[2*p] += lazy[p];
		lazy[2*p+1] += lazy[p];
		tree[2*p] += lazy[p];
		tree[2*p+1] += lazy[p];
		lazy[p] = 0;
		tree[2*p] = max(tree[2*p], tree[p]);
		tree[2*p+1] = max(tree[2*p+1], tree[p]);
		tree[p] = 0;
	}
	void add(int s, int e, int ps, int pe, int p, lint v){
		if(e < ps || pe < s) return;
		if(s <= ps && pe <= e){
			lazy[p] += v;
			tree[p] += v;
			return;
		}
		int pm = (ps + pe) / 2;
		lazydown(p);
		add(s, e, ps, pm, 2*p, v);
		add(s, e, pm + 1, pe, 2*p + 1, v);
	}
	void upperize(int s, int e, int ps, int pe, int p, lint v){
		if(e < ps || pe < s) return;
		if(s <= ps && pe <= e){
			tree[p] = max(tree[p], v);
			return;
		}
		int pm = (ps + pe) / 2;
		lazydown(p);
		upperize(s, e, ps, pm, 2*p, v);
		upperize(s, e, pm+1, pe, 2*p+1, v);
	}
	lint query(int pos, int s, int e, int p){
		if(s == e) return tree[p];
		int m = (s + e) / 2;
		lazydown(p);
		if(pos <= m) return query(pos, s, m, 2*p);
		return query(pos, m+1, e, 2*p+1);
	}
}seg;

int n, m;
lint a[MAXN], s[MAXN], p[MAXN];
lint b[MAXN], t[MAXN], q[MAXN];
int da[MAXN], db[MAXN];
lint dp[MAXN];
vector<pnt> v, w;

int main(){
	scanf("%d %d",&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];
	}
	lint ret = 0;
	v.push_back({0, 0, 0});
	for(int i=1; i<=n; i++){
		da[i] = upper_bound(b, b + m + 1, s[i] - a[i]) - b;
		if(da[i] > 0){
			if(p[i] > 0) v.push_back({i, da[i], p[i]});
			else w.push_back({i, da[i], -p[i]}), ret += p[i];
		}
	}
	for(int i=1; i<=m; i++){
		db[i] = upper_bound(a, a + n + 1, t[i] - b[i]) - a;
		if(db[i] > 0){
			if(q[i] > 0) w.push_back({db[i], i, q[i]});
			else v.push_back({db[i], i, -q[i]}), ret += q[i];
		}
	}
	sort(v.begin(), v.end());
	sort(w.begin(), w.end());
	v.push_back({n + 1, m + 1, 0});
	int pw = 0;
	for(int i=1; i<v.size(); ){
		int e = i;
		while(e < v.size() && v[e].x == v[i].x) e++;
		for(int j = i; j < e; j++){
			seg.add(0, v[j].y - 1, 0, m, 1, v[j].c);
		}
		while(pw < w.size() && w[pw].x <= v[i].x){
			seg.add(w[pw].y, m, 0, m, 1, w[pw].c);
			pw++;
		}
		if(v[i].x <= n){
		for(int j = i; j < e; j++){
			dp[j] = seg.query(v[j].y - 1, 0, m, 1);
		}
		for(int j = i; j < e; j++){
			seg.upperize(v[j].y - 1, m, 0, m, 1, dp[j]);
		}
		}
		i = e;
	}
	lint dap = -1e18;
	for(int i=0; i<m+3; i++) dap = max(dap, seg.query(i, 0, m+1, 1));
	cout << ret + dap << endl;
}

Compilation message

dishes.cpp: In function 'int main()':
dishes.cpp:98:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=1; i<v.size(); ){
               ~^~~~~~~~~
dishes.cpp:100:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(e < v.size() && v[e].x == v[i].x) e++;
         ~~^~~~~~~~~~
dishes.cpp:104:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(pw < w.size() && w[pw].x <= v[i].x){
         ~~~^~~~~~~~~~
dishes.cpp:69: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:71:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld %lld",&a[i],&s[i],&p[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dishes.cpp:75:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld %lld",&b[i],&t[i],&q[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 412 ms 35412 KB Output is correct
2 Correct 425 ms 35540 KB Output is correct
3 Correct 392 ms 35924 KB Output is correct
4 Correct 353 ms 32820 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 416 ms 34672 KB Output is correct
7 Correct 202 ms 21440 KB Output is correct
8 Correct 125 ms 15320 KB Output is correct
9 Correct 398 ms 35128 KB Output is correct
10 Correct 372 ms 32212 KB Output is correct
11 Correct 337 ms 32108 KB Output is correct

Subtask #2
3.0 / 3.0

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

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 380 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 380 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 5 ms 888 KB Output is correct
18 Correct 5 ms 760 KB Output is correct
19 Correct 6 ms 760 KB Output is correct
20 Correct 5 ms 760 KB Output is correct
21 Correct 6 ms 760 KB Output is correct
22 Correct 5 ms 760 KB Output is correct
23 Correct 5 ms 760 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 380 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 380 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 5 ms 888 KB Output is correct
18 Correct 5 ms 760 KB Output is correct
19 Correct 6 ms 760 KB Output is correct
20 Correct 5 ms 760 KB Output is correct
21 Correct 6 ms 760 KB Output is correct
22 Correct 5 ms 760 KB Output is correct
23 Correct 5 ms 760 KB Output is correct
24 Correct 352 ms 34932 KB Output is correct
25 Correct 330 ms 31580 KB Output is correct
26 Correct 392 ms 33748 KB Output is correct
27 Correct 344 ms 31068 KB Output is correct
28 Correct 437 ms 32340 KB Output is correct
29 Correct 364 ms 33252 KB Output is correct
30 Correct 575 ms 33196 KB Output is correct
31 Correct 190 ms 20444 KB Output is correct
32 Correct 115 ms 13828 KB Output is correct
33 Correct 399 ms 29472 KB Output is correct
34 Correct 526 ms 33396 KB Output is correct
35 Correct 509 ms 31096 KB Output is correct
36 Correct 493 ms 30972 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 380 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 380 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 5 ms 888 KB Output is correct
18 Correct 5 ms 760 KB Output is correct
19 Correct 6 ms 760 KB Output is correct
20 Correct 5 ms 760 KB Output is correct
21 Correct 6 ms 760 KB Output is correct
22 Correct 5 ms 760 KB Output is correct
23 Correct 5 ms 760 KB Output is correct
24 Correct 352 ms 34932 KB Output is correct
25 Correct 330 ms 31580 KB Output is correct
26 Correct 392 ms 33748 KB Output is correct
27 Correct 344 ms 31068 KB Output is correct
28 Correct 437 ms 32340 KB Output is correct
29 Correct 364 ms 33252 KB Output is correct
30 Correct 575 ms 33196 KB Output is correct
31 Correct 190 ms 20444 KB Output is correct
32 Correct 115 ms 13828 KB Output is correct
33 Correct 399 ms 29472 KB Output is correct
34 Correct 526 ms 33396 KB Output is correct
35 Correct 509 ms 31096 KB Output is correct
36 Correct 493 ms 30972 KB Output is correct
37 Correct 427 ms 33372 KB Output is correct
38 Correct 373 ms 30644 KB Output is correct
39 Correct 416 ms 33364 KB Output is correct
40 Correct 418 ms 33180 KB Output is correct
41 Correct 2 ms 376 KB Output is correct
42 Correct 602 ms 33668 KB Output is correct
43 Correct 440 ms 29536 KB Output is correct
44 Correct 612 ms 33240 KB Output is correct
45 Correct 538 ms 32908 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 380 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 380 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 5 ms 888 KB Output is correct
18 Correct 5 ms 760 KB Output is correct
19 Correct 6 ms 760 KB Output is correct
20 Correct 5 ms 760 KB Output is correct
21 Correct 6 ms 760 KB Output is correct
22 Correct 5 ms 760 KB Output is correct
23 Correct 5 ms 760 KB Output is correct
24 Correct 352 ms 34932 KB Output is correct
25 Correct 330 ms 31580 KB Output is correct
26 Correct 392 ms 33748 KB Output is correct
27 Correct 344 ms 31068 KB Output is correct
28 Correct 437 ms 32340 KB Output is correct
29 Correct 364 ms 33252 KB Output is correct
30 Correct 575 ms 33196 KB Output is correct
31 Correct 190 ms 20444 KB Output is correct
32 Correct 115 ms 13828 KB Output is correct
33 Correct 399 ms 29472 KB Output is correct
34 Correct 526 ms 33396 KB Output is correct
35 Correct 509 ms 31096 KB Output is correct
36 Correct 493 ms 30972 KB Output is correct
37 Correct 427 ms 33372 KB Output is correct
38 Correct 373 ms 30644 KB Output is correct
39 Correct 416 ms 33364 KB Output is correct
40 Correct 418 ms 33180 KB Output is correct
41 Correct 2 ms 376 KB Output is correct
42 Correct 602 ms 33668 KB Output is correct
43 Correct 440 ms 29536 KB Output is correct
44 Correct 612 ms 33240 KB Output is correct
45 Correct 538 ms 32908 KB Output is correct
46 Correct 2208 ms 130684 KB Output is correct
47 Correct 1933 ms 117444 KB Output is correct
48 Correct 2173 ms 128732 KB Output is correct
49 Correct 2177 ms 128724 KB Output is correct
50 Correct 3631 ms 128512 KB Output is correct
51 Correct 2445 ms 106744 KB Output is correct
52 Correct 3001 ms 123844 KB Output is correct
53 Correct 3164 ms 134208 KB Output is correct

Subtask #7
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 412 ms 35412 KB Output is correct
2 Correct 425 ms 35540 KB Output is correct
3 Correct 392 ms 35924 KB Output is correct
4 Correct 353 ms 32820 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 416 ms 34672 KB Output is correct
7 Correct 202 ms 21440 KB Output is correct
8 Correct 125 ms 15320 KB Output is correct
9 Correct 398 ms 35128 KB Output is correct
10 Correct 372 ms 32212 KB Output is correct
11 Correct 337 ms 32108 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 2 ms 376 KB Output is correct
21 Correct 2 ms 380 KB Output is correct
22 Correct 2 ms 376 KB Output is correct
23 Correct 2 ms 380 KB Output is correct
24 Correct 2 ms 376 KB Output is correct
25 Correct 2 ms 376 KB Output is correct
26 Correct 2 ms 376 KB Output is correct
27 Correct 2 ms 376 KB Output is correct
28 Correct 5 ms 888 KB Output is correct
29 Correct 5 ms 760 KB Output is correct
30 Correct 6 ms 760 KB Output is correct
31 Correct 5 ms 760 KB Output is correct
32 Correct 6 ms 760 KB Output is correct
33 Correct 5 ms 760 KB Output is correct
34 Correct 5 ms 760 KB Output is correct
35 Correct 352 ms 34932 KB Output is correct
36 Correct 330 ms 31580 KB Output is correct
37 Correct 392 ms 33748 KB Output is correct
38 Correct 344 ms 31068 KB Output is correct
39 Correct 437 ms 32340 KB Output is correct
40 Correct 364 ms 33252 KB Output is correct
41 Correct 575 ms 33196 KB Output is correct
42 Correct 190 ms 20444 KB Output is correct
43 Correct 115 ms 13828 KB Output is correct
44 Correct 399 ms 29472 KB Output is correct
45 Correct 526 ms 33396 KB Output is correct
46 Correct 509 ms 31096 KB Output is correct
47 Correct 493 ms 30972 KB Output is correct
48 Correct 427 ms 33372 KB Output is correct
49 Correct 373 ms 30644 KB Output is correct
50 Correct 416 ms 33364 KB Output is correct
51 Correct 418 ms 33180 KB Output is correct
52 Correct 2 ms 376 KB Output is correct
53 Correct 602 ms 33668 KB Output is correct
54 Correct 440 ms 29536 KB Output is correct
55 Correct 612 ms 33240 KB Output is correct
56 Correct 538 ms 32908 KB Output is correct
57 Incorrect 354 ms 35188 KB Output isn't correct
58 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 412 ms 35412 KB Output is correct
2 Correct 425 ms 35540 KB Output is correct
3 Correct 392 ms 35924 KB Output is correct
4 Correct 353 ms 32820 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 416 ms 34672 KB Output is correct
7 Correct 202 ms 21440 KB Output is correct
8 Correct 125 ms 15320 KB Output is correct
9 Correct 398 ms 35128 KB Output is correct
10 Correct 372 ms 32212 KB Output is correct
11 Correct 337 ms 32108 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 2 ms 376 KB Output is correct
21 Correct 2 ms 380 KB Output is correct
22 Correct 2 ms 376 KB Output is correct
23 Correct 2 ms 380 KB Output is correct
24 Correct 2 ms 376 KB Output is correct
25 Correct 2 ms 376 KB Output is correct
26 Correct 2 ms 376 KB Output is correct
27 Correct 2 ms 376 KB Output is correct
28 Correct 5 ms 888 KB Output is correct
29 Correct 5 ms 760 KB Output is correct
30 Correct 6 ms 760 KB Output is correct
31 Correct 5 ms 760 KB Output is correct
32 Correct 6 ms 760 KB Output is correct
33 Correct 5 ms 760 KB Output is correct
34 Correct 5 ms 760 KB Output is correct
35 Correct 352 ms 34932 KB Output is correct
36 Correct 330 ms 31580 KB Output is correct
37 Correct 392 ms 33748 KB Output is correct
38 Correct 344 ms 31068 KB Output is correct
39 Correct 437 ms 32340 KB Output is correct
40 Correct 364 ms 33252 KB Output is correct
41 Correct 575 ms 33196 KB Output is correct
42 Correct 190 ms 20444 KB Output is correct
43 Correct 115 ms 13828 KB Output is correct
44 Correct 399 ms 29472 KB Output is correct
45 Correct 526 ms 33396 KB Output is correct
46 Correct 509 ms 31096 KB Output is correct
47 Correct 493 ms 30972 KB Output is correct
48 Correct 427 ms 33372 KB Output is correct
49 Correct 373 ms 30644 KB Output is correct
50 Correct 416 ms 33364 KB Output is correct
51 Correct 418 ms 33180 KB Output is correct
52 Correct 2 ms 376 KB Output is correct
53 Correct 602 ms 33668 KB Output is correct
54 Correct 440 ms 29536 KB Output is correct
55 Correct 612 ms 33240 KB Output is correct
56 Correct 538 ms 32908 KB Output is correct
57 Correct 2208 ms 130684 KB Output is correct
58 Correct 1933 ms 117444 KB Output is correct
59 Correct 2173 ms 128732 KB Output is correct
60 Correct 2177 ms 128724 KB Output is correct
61 Correct 3631 ms 128512 KB Output is correct
62 Correct 2445 ms 106744 KB Output is correct
63 Correct 3001 ms 123844 KB Output is correct
64 Correct 3164 ms 134208 KB Output is correct
65 Incorrect 354 ms 35188 KB Output isn't correct
66 Halted 0 ms 0 KB -