oj.uz

Submission #102533

# Submission time Handle Problem Language Result Execution time Memory
102533 2019-03-25T18:38:34 Z ihdignite Two Dishes (JOI19_dishes) C++14
100 / 100
 7203 ms 247132 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long

const int mxN=1e6;
int n, m, p[mxN], q[mxN];
ll a[mxN+1], b[mxN+1], s[mxN], t[mxN], ans, lz[1<<21];
vector<array<ll, 2>> e[mxN+1];
array<ll, 2> st[1<<21];

void app(int i, ll x) {
	st[i][0]+=x;
	st[i][1]+=x;
	lz[i]+=x;
}

void psh(int i) {
	app(2*i, lz[i]);
	app(2*i+1, lz[i]);
	lz[i]=0;
}

void upd1(int l1, int r1, ll x, int i=1, int l2=0, int r2=m) {
	if(l1<=l2&&r2<=r1) {
		app(i, x);
		return;
	}
	int m2=(l2+r2)/2;
	psh(i);
	if(l1<=m2)
		upd1(l1, r1, x, 2*i, l2, m2);
	if(m2<r1)
		upd1(l1, r1, x, 2*i+1, m2+1, r2);
	st[i][0]=min(st[2*i][0], st[2*i+1][0]);
	st[i][1]=max(st[2*i][1], st[2*i+1][1]);
}

void upd2(int l1, int r1, ll x, int i=1, int l2=0, int r2=m) {
	if(st[i][0]>=x)
		return;
	if(l1<=l2&&r2<=r1&&st[i][0]==st[i][1]) {
		app(i, x-st[i][0]);
		return;
	}
	int m2=(l2+r2)/2;
	psh(i);
	if(l1<=m2)
		upd2(l1, r1, x, 2*i, l2, m2);
	if(m2<r1)
		upd2(l1, r1, x, 2*i+1, m2+1, r2);
	st[i][0]=min(st[2*i][0], st[2*i+1][0]);
	st[i][1]=max(st[2*i][1], st[2*i+1][1]);
}

ll qry(int l1, int i=1, int l2=0, int r2=m) {
	if(l2==r2)
		return st[i][0];
	int m2=(l2+r2)/2;
	psh(i);
	return l1<=m2?qry(l1, 2*i, l2, m2):qry(l1, 2*i+1, m2+1, r2);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	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];
		ans+=q[i];
		e[upper_bound(a, a+n+1, t[i]-b[i+1])-a].push_back({i, -q[i]});
	}
	memset(st, 0xfe, sizeof(st));
	upd2(0, 0, 0);
	e[0].push_back({0, 0});
	for(int i=0; i<=n; ++i) {
		if(i) {
			int j=upper_bound(b, b+m+1, s[i-1]-a[i])-b;
			if(j)
				e[i].push_back({j-1, p[i-1]});
		}
		sort(e[i].begin(), e[i].end());
		if(!e[i].size()||e[i].back()[0]^m)
			e[i].push_back({m, 0});
		for(int j=0; j<e[i].size(); ++j) {
			upd1(0, e[i][j][0], e[i][j][1]);
			if(j+1<e[i].size())
				upd2(e[i][j][0], e[i][j+1][0], qry(e[i][j][0]));
		}
	}
	cout << ans+qry(m);
}

Compilation message

dishes.cpp: In function 'int main()':
dishes.cpp:88:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0; j<e[i].size(); ++j) {
                ~^~~~~~~~~~~~
dishes.cpp:90:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(j+1<e[i].size())
       ~~~^~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 497 ms 96248 KB Output is correct
2 Correct 541 ms 95816 KB Output is correct
3 Correct 306 ms 87332 KB Output is correct
4 Correct 477 ms 95200 KB Output is correct
5 Correct 50 ms 56772 KB Output is correct
6 Correct 493 ms 93716 KB Output is correct
7 Correct 163 ms 71600 KB Output is correct
8 Correct 159 ms 73848 KB Output is correct
9 Correct 283 ms 88416 KB Output is correct
10 Correct 445 ms 91784 KB Output is correct
11 Correct 188 ms 81760 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 56640 KB Output is correct
2 Correct 59 ms 56696 KB Output is correct
3 Correct 50 ms 56824 KB Output is correct
4 Correct 49 ms 56824 KB Output is correct
5 Correct 49 ms 56696 KB Output is correct
6 Correct 51 ms 56776 KB Output is correct
7 Correct 48 ms 56824 KB Output is correct
8 Correct 49 ms 56764 KB Output is correct
9 Correct 47 ms 56696 KB Output is correct
10 Correct 50 ms 56696 KB Output is correct
11 Correct 48 ms 56696 KB Output is correct
12 Correct 53 ms 56696 KB Output is correct
13 Correct 55 ms 56696 KB Output is correct
14 Correct 49 ms 56696 KB Output is correct
15 Correct 52 ms 56696 KB Output is correct
16 Correct 51 ms 56696 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 56640 KB Output is correct
2 Correct 59 ms 56696 KB Output is correct
3 Correct 50 ms 56824 KB Output is correct
4 Correct 49 ms 56824 KB Output is correct
5 Correct 49 ms 56696 KB Output is correct
6 Correct 51 ms 56776 KB Output is correct
7 Correct 48 ms 56824 KB Output is correct
8 Correct 49 ms 56764 KB Output is correct
9 Correct 47 ms 56696 KB Output is correct
10 Correct 50 ms 56696 KB Output is correct
11 Correct 48 ms 56696 KB Output is correct
12 Correct 53 ms 56696 KB Output is correct
13 Correct 55 ms 56696 KB Output is correct
14 Correct 49 ms 56696 KB Output is correct
15 Correct 52 ms 56696 KB Output is correct
16 Correct 51 ms 56696 KB Output is correct
17 Correct 58 ms 57188 KB Output is correct
18 Correct 62 ms 57208 KB Output is correct
19 Correct 67 ms 57080 KB Output is correct
20 Correct 54 ms 57080 KB Output is correct
21 Correct 64 ms 57208 KB Output is correct
22 Correct 56 ms 57208 KB Output is correct
23 Correct 58 ms 57052 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 56640 KB Output is correct
2 Correct 59 ms 56696 KB Output is correct
3 Correct 50 ms 56824 KB Output is correct
4 Correct 49 ms 56824 KB Output is correct
5 Correct 49 ms 56696 KB Output is correct
6 Correct 51 ms 56776 KB Output is correct
7 Correct 48 ms 56824 KB Output is correct
8 Correct 49 ms 56764 KB Output is correct
9 Correct 47 ms 56696 KB Output is correct
10 Correct 50 ms 56696 KB Output is correct
11 Correct 48 ms 56696 KB Output is correct
12 Correct 53 ms 56696 KB Output is correct
13 Correct 55 ms 56696 KB Output is correct
14 Correct 49 ms 56696 KB Output is correct
15 Correct 52 ms 56696 KB Output is correct
16 Correct 51 ms 56696 KB Output is correct
17 Correct 58 ms 57188 KB Output is correct
18 Correct 62 ms 57208 KB Output is correct
19 Correct 67 ms 57080 KB Output is correct
20 Correct 54 ms 57080 KB Output is correct
21 Correct 64 ms 57208 KB Output is correct
22 Correct 56 ms 57208 KB Output is correct
23 Correct 58 ms 57052 KB Output is correct
24 Correct 483 ms 91704 KB Output is correct
25 Correct 389 ms 88672 KB Output is correct
26 Correct 531 ms 92100 KB Output is correct
27 Correct 401 ms 88824 KB Output is correct
28 Correct 527 ms 90048 KB Output is correct
29 Correct 227 ms 85344 KB Output is correct
30 Correct 988 ms 94660 KB Output is correct
31 Correct 236 ms 73424 KB Output is correct
32 Correct 160 ms 73720 KB Output is correct
33 Correct 716 ms 90512 KB Output is correct
34 Correct 825 ms 92736 KB Output is correct
35 Correct 973 ms 88224 KB Output is correct
36 Correct 913 ms 88060 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 56640 KB Output is correct
2 Correct 59 ms 56696 KB Output is correct
3 Correct 50 ms 56824 KB Output is correct
4 Correct 49 ms 56824 KB Output is correct
5 Correct 49 ms 56696 KB Output is correct
6 Correct 51 ms 56776 KB Output is correct
7 Correct 48 ms 56824 KB Output is correct
8 Correct 49 ms 56764 KB Output is correct
9 Correct 47 ms 56696 KB Output is correct
10 Correct 50 ms 56696 KB Output is correct
11 Correct 48 ms 56696 KB Output is correct
12 Correct 53 ms 56696 KB Output is correct
13 Correct 55 ms 56696 KB Output is correct
14 Correct 49 ms 56696 KB Output is correct
15 Correct 52 ms 56696 KB Output is correct
16 Correct 51 ms 56696 KB Output is correct
17 Correct 58 ms 57188 KB Output is correct
18 Correct 62 ms 57208 KB Output is correct
19 Correct 67 ms 57080 KB Output is correct
20 Correct 54 ms 57080 KB Output is correct
21 Correct 64 ms 57208 KB Output is correct
22 Correct 56 ms 57208 KB Output is correct
23 Correct 58 ms 57052 KB Output is correct
24 Correct 483 ms 91704 KB Output is correct
25 Correct 389 ms 88672 KB Output is correct
26 Correct 531 ms 92100 KB Output is correct
27 Correct 401 ms 88824 KB Output is correct
28 Correct 527 ms 90048 KB Output is correct
29 Correct 227 ms 85344 KB Output is correct
30 Correct 988 ms 94660 KB Output is correct
31 Correct 236 ms 73424 KB Output is correct
32 Correct 160 ms 73720 KB Output is correct
33 Correct 716 ms 90512 KB Output is correct
34 Correct 825 ms 92736 KB Output is correct
35 Correct 973 ms 88224 KB Output is correct
36 Correct 913 ms 88060 KB Output is correct
37 Correct 472 ms 94788 KB Output is correct
38 Correct 384 ms 92052 KB Output is correct
39 Correct 466 ms 95572 KB Output is correct
40 Correct 536 ms 95456 KB Output is correct
41 Correct 51 ms 56824 KB Output is correct
42 Correct 1089 ms 97528 KB Output is correct
43 Correct 925 ms 93528 KB Output is correct
44 Correct 787 ms 95496 KB Output is correct
45 Correct 965 ms 91372 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 56640 KB Output is correct
2 Correct 59 ms 56696 KB Output is correct
3 Correct 50 ms 56824 KB Output is correct
4 Correct 49 ms 56824 KB Output is correct
5 Correct 49 ms 56696 KB Output is correct
6 Correct 51 ms 56776 KB Output is correct
7 Correct 48 ms 56824 KB Output is correct
8 Correct 49 ms 56764 KB Output is correct
9 Correct 47 ms 56696 KB Output is correct
10 Correct 50 ms 56696 KB Output is correct
11 Correct 48 ms 56696 KB Output is correct
12 Correct 53 ms 56696 KB Output is correct
13 Correct 55 ms 56696 KB Output is correct
14 Correct 49 ms 56696 KB Output is correct
15 Correct 52 ms 56696 KB Output is correct
16 Correct 51 ms 56696 KB Output is correct
17 Correct 58 ms 57188 KB Output is correct
18 Correct 62 ms 57208 KB Output is correct
19 Correct 67 ms 57080 KB Output is correct
20 Correct 54 ms 57080 KB Output is correct
21 Correct 64 ms 57208 KB Output is correct
22 Correct 56 ms 57208 KB Output is correct
23 Correct 58 ms 57052 KB Output is correct
24 Correct 483 ms 91704 KB Output is correct
25 Correct 389 ms 88672 KB Output is correct
26 Correct 531 ms 92100 KB Output is correct
27 Correct 401 ms 88824 KB Output is correct
28 Correct 527 ms 90048 KB Output is correct
29 Correct 227 ms 85344 KB Output is correct
30 Correct 988 ms 94660 KB Output is correct
31 Correct 236 ms 73424 KB Output is correct
32 Correct 160 ms 73720 KB Output is correct
33 Correct 716 ms 90512 KB Output is correct
34 Correct 825 ms 92736 KB Output is correct
35 Correct 973 ms 88224 KB Output is correct
36 Correct 913 ms 88060 KB Output is correct
37 Correct 472 ms 94788 KB Output is correct
38 Correct 384 ms 92052 KB Output is correct
39 Correct 466 ms 95572 KB Output is correct
40 Correct 536 ms 95456 KB Output is correct
41 Correct 51 ms 56824 KB Output is correct
42 Correct 1089 ms 97528 KB Output is correct
43 Correct 925 ms 93528 KB Output is correct
44 Correct 787 ms 95496 KB Output is correct
45 Correct 965 ms 91372 KB Output is correct
46 Correct 2663 ms 245028 KB Output is correct
47 Correct 1955 ms 229320 KB Output is correct
48 Correct 2326 ms 247132 KB Output is correct
49 Correct 2779 ms 191736 KB Output is correct
50 Correct 6488 ms 189400 KB Output is correct
51 Correct 3966 ms 168032 KB Output is correct
52 Correct 4460 ms 174104 KB Output is correct
53 Correct 7030 ms 187236 KB Output is correct

Subtask #7
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 497 ms 96248 KB Output is correct
2 Correct 541 ms 95816 KB Output is correct
3 Correct 306 ms 87332 KB Output is correct
4 Correct 477 ms 95200 KB Output is correct
5 Correct 50 ms 56772 KB Output is correct
6 Correct 493 ms 93716 KB Output is correct
7 Correct 163 ms 71600 KB Output is correct
8 Correct 159 ms 73848 KB Output is correct
9 Correct 283 ms 88416 KB Output is correct
10 Correct 445 ms 91784 KB Output is correct
11 Correct 188 ms 81760 KB Output is correct
12 Correct 49 ms 56640 KB Output is correct
13 Correct 59 ms 56696 KB Output is correct
14 Correct 50 ms 56824 KB Output is correct
15 Correct 49 ms 56824 KB Output is correct
16 Correct 49 ms 56696 KB Output is correct
17 Correct 51 ms 56776 KB Output is correct
18 Correct 48 ms 56824 KB Output is correct
19 Correct 49 ms 56764 KB Output is correct
20 Correct 47 ms 56696 KB Output is correct
21 Correct 50 ms 56696 KB Output is correct
22 Correct 48 ms 56696 KB Output is correct
23 Correct 53 ms 56696 KB Output is correct
24 Correct 55 ms 56696 KB Output is correct
25 Correct 49 ms 56696 KB Output is correct
26 Correct 52 ms 56696 KB Output is correct
27 Correct 51 ms 56696 KB Output is correct
28 Correct 58 ms 57188 KB Output is correct
29 Correct 62 ms 57208 KB Output is correct
30 Correct 67 ms 57080 KB Output is correct
31 Correct 54 ms 57080 KB Output is correct
32 Correct 64 ms 57208 KB Output is correct
33 Correct 56 ms 57208 KB Output is correct
34 Correct 58 ms 57052 KB Output is correct
35 Correct 483 ms 91704 KB Output is correct
36 Correct 389 ms 88672 KB Output is correct
37 Correct 531 ms 92100 KB Output is correct
38 Correct 401 ms 88824 KB Output is correct
39 Correct 527 ms 90048 KB Output is correct
40 Correct 227 ms 85344 KB Output is correct
41 Correct 988 ms 94660 KB Output is correct
42 Correct 236 ms 73424 KB Output is correct
43 Correct 160 ms 73720 KB Output is correct
44 Correct 716 ms 90512 KB Output is correct
45 Correct 825 ms 92736 KB Output is correct
46 Correct 973 ms 88224 KB Output is correct
47 Correct 913 ms 88060 KB Output is correct
48 Correct 472 ms 94788 KB Output is correct
49 Correct 384 ms 92052 KB Output is correct
50 Correct 466 ms 95572 KB Output is correct
51 Correct 536 ms 95456 KB Output is correct
52 Correct 51 ms 56824 KB Output is correct
53 Correct 1089 ms 97528 KB Output is correct
54 Correct 925 ms 93528 KB Output is correct
55 Correct 787 ms 95496 KB Output is correct
56 Correct 965 ms 91372 KB Output is correct
57 Correct 554 ms 95276 KB Output is correct
58 Correct 460 ms 91896 KB Output is correct
59 Correct 606 ms 95096 KB Output is correct
60 Correct 456 ms 95096 KB Output is correct
61 Correct 784 ms 93404 KB Output is correct
62 Correct 48 ms 56696 KB Output is correct
63 Correct 984 ms 96376 KB Output is correct
64 Correct 712 ms 92012 KB Output is correct
65 Correct 820 ms 94188 KB Output is correct
66 Correct 925 ms 89912 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 497 ms 96248 KB Output is correct
2 Correct 541 ms 95816 KB Output is correct
3 Correct 306 ms 87332 KB Output is correct
4 Correct 477 ms 95200 KB Output is correct
5 Correct 50 ms 56772 KB Output is correct
6 Correct 493 ms 93716 KB Output is correct
7 Correct 163 ms 71600 KB Output is correct
8 Correct 159 ms 73848 KB Output is correct
9 Correct 283 ms 88416 KB Output is correct
10 Correct 445 ms 91784 KB Output is correct
11 Correct 188 ms 81760 KB Output is correct
12 Correct 49 ms 56640 KB Output is correct
13 Correct 59 ms 56696 KB Output is correct
14 Correct 50 ms 56824 KB Output is correct
15 Correct 49 ms 56824 KB Output is correct
16 Correct 49 ms 56696 KB Output is correct
17 Correct 51 ms 56776 KB Output is correct
18 Correct 48 ms 56824 KB Output is correct
19 Correct 49 ms 56764 KB Output is correct
20 Correct 47 ms 56696 KB Output is correct
21 Correct 50 ms 56696 KB Output is correct
22 Correct 48 ms 56696 KB Output is correct
23 Correct 53 ms 56696 KB Output is correct
24 Correct 55 ms 56696 KB Output is correct
25 Correct 49 ms 56696 KB Output is correct
26 Correct 52 ms 56696 KB Output is correct
27 Correct 51 ms 56696 KB Output is correct
28 Correct 58 ms 57188 KB Output is correct
29 Correct 62 ms 57208 KB Output is correct
30 Correct 67 ms 57080 KB Output is correct
31 Correct 54 ms 57080 KB Output is correct
32 Correct 64 ms 57208 KB Output is correct
33 Correct 56 ms 57208 KB Output is correct
34 Correct 58 ms 57052 KB Output is correct
35 Correct 483 ms 91704 KB Output is correct
36 Correct 389 ms 88672 KB Output is correct
37 Correct 531 ms 92100 KB Output is correct
38 Correct 401 ms 88824 KB Output is correct
39 Correct 527 ms 90048 KB Output is correct
40 Correct 227 ms 85344 KB Output is correct
41 Correct 988 ms 94660 KB Output is correct
42 Correct 236 ms 73424 KB Output is correct
43 Correct 160 ms 73720 KB Output is correct
44 Correct 716 ms 90512 KB Output is correct
45 Correct 825 ms 92736 KB Output is correct
46 Correct 973 ms 88224 KB Output is correct
47 Correct 913 ms 88060 KB Output is correct
48 Correct 472 ms 94788 KB Output is correct
49 Correct 384 ms 92052 KB Output is correct
50 Correct 466 ms 95572 KB Output is correct
51 Correct 536 ms 95456 KB Output is correct
52 Correct 51 ms 56824 KB Output is correct
53 Correct 1089 ms 97528 KB Output is correct
54 Correct 925 ms 93528 KB Output is correct
55 Correct 787 ms 95496 KB Output is correct
56 Correct 965 ms 91372 KB Output is correct
57 Correct 2663 ms 245028 KB Output is correct
58 Correct 1955 ms 229320 KB Output is correct
59 Correct 2326 ms 247132 KB Output is correct
60 Correct 2779 ms 191736 KB Output is correct
61 Correct 6488 ms 189400 KB Output is correct
62 Correct 3966 ms 168032 KB Output is correct
63 Correct 4460 ms 174104 KB Output is correct
64 Correct 7030 ms 187236 KB Output is correct
65 Correct 554 ms 95276 KB Output is correct
66 Correct 460 ms 91896 KB Output is correct
67 Correct 606 ms 95096 KB Output is correct
68 Correct 456 ms 95096 KB Output is correct
69 Correct 784 ms 93404 KB Output is correct
70 Correct 48 ms 56696 KB Output is correct
71 Correct 984 ms 96376 KB Output is correct
72 Correct 712 ms 92012 KB Output is correct
73 Correct 820 ms 94188 KB Output is correct
74 Correct 925 ms 89912 KB Output is correct
75 Correct 2944 ms 176612 KB Output is correct
76 Correct 1997 ms 160804 KB Output is correct
77 Correct 3400 ms 191716 KB Output is correct
78 Correct 2160 ms 191660 KB Output is correct
79 Correct 7203 ms 189332 KB Output is correct
80 Correct 4390 ms 168656 KB Output is correct
81 Correct 4507 ms 174352 KB Output is correct
82 Correct 6563 ms 188172 KB Output is correct
83 Correct 6207 ms 186364 KB Output is correct