oj.uz

Submission #106906

# Submission time Handle Problem Language Result Execution time Memory
106906 2019-04-20T20:58:15 Z eriksuenderhauf Two Dishes (JOI19_dishes) C++11
100 / 100
 7669 ms 203848 KB 
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define mem(a,v) memset((a), (v), sizeof (a))
#define enl printf("\n")
#define case(t) printf("Case #%d: ", (t))
#define ni(n) scanf("%d", &(n))
#define nl(n) scanf("%lld", &(n))
#define nai(a, n) for (int i = 0; i < (n); i++) ni(a[i])
#define nal(a, n) for (int i = 0; i < (n); i++) nl(a[i])
#define pri(n) printf("%d\n", (n))
#define prl(n) printf("%lld\n", (n))
#define pii pair<int, int>
#define pil pair<int, long long>
#define pll pair<long long, long long>
#define vii vector<pii>
#define vil vector<pil>
#define vll vector<pll>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef cc_hash_table<int,int,hash<int>> ht;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> oset;
const double pi = acos(-1);
const int MOD = 1e9 + 7;
const ll INF = 1e18 + 7;
const int MAXN = 1e6 + 5;
const double eps = 1e-9;
ll a[MAXN], b[MAXN];
ll s[MAXN], p[MAXN], q[MAXN], t[MAXN];
map<pii,ll> pts;
ll seg[MAXN*4], lazy[MAXN*4];

void prop(int l, int r, int k) {
	if (l != r) {
		lazy[k*2]+=lazy[k];
		lazy[k*2+1]+=lazy[k];
	}
	lazy[k] = 0;
}

ll qry(int l, int r, int k, int a, int b) {
	if (r < a || b < l || a > b) return -INF;
	seg[k] += lazy[k];
	prop(l,r,k);
	if (a <= l && r <= b) return seg[k];
	int m = (l + r) / 2;
	return max(qry(l,m,k*2,a,b),qry(m+1,r,k*2+1,a,b));
}

// consider the following scenario:
//   x
//  / \
// L   R
// if L is updated and the value of R is not changed with 
// lazy-propagation then the value of x is not set correctly

void upd1(int l, int r, int k, int a, ll v) {
	seg[k] += lazy[k];
	prop(l,r,k);
	if (a < l || r < a) return;
	if (a <= l && r <= a) {
		seg[k] = max(seg[k],v);
		return;
	}
	int m = (l + r) / 2;
	upd1(l, m, k*2, a, v);
	upd1(m+1, r, k*2+1, a, v);
	seg[k] = max(seg[k*2],seg[k*2+1]);
}

void upd2(int l, int r, int k, int a, int b, ll v) {
	if (b < l || r < a || a > b) return;
	seg[k] += lazy[k];
	prop(l,r,k);
	if (a <= l && r <= b) {
		seg[k] += v;
		lazy[k] = v;
		prop(l, r, k);
		return;
	}
	int m = (l + r) / 2;
	upd2(l, m, k*2, a, b, v);
	upd2(m+1, r, k*2+1, a, b, v);
	seg[k] = max(seg[k*2],seg[k*2+1]);
}

int main() {
	int n, m;
	ll ans = 0;
	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];
	}
	for (int i = 1; i <= n; i++) {
		if (a[i] > s[i]) continue;
		if (a[i] + b[m] <= s[i]) {
			ans += p[i];
			continue;
		}
		int ind = lower_bound(b+1, b+1 + m, s[i]-a[i]+1) - b-1;
		pts[{i-1, -(ind+1)}] += p[i];
	}
	for (int i = 1; i <= m; i++) {
		if (b[i] > t[i]) continue;
		if (b[i] + a[n] <= t[i]) {
			ans += q[i];
			continue;
		}
		int ind = lower_bound(a+1, a+1 + n, t[i]-b[i]+1) - a-1;
		ans += q[i];
		pts[{ind, -i}] -= q[i];
	}
	int mx = min((m+1),2*MAXN-1);
	for (auto &it: pts) {
		int x, y;
		tie(x, y) = it.fi;
		ll c = it.se;
		ll tmp = qry(0, mx, 1, 0, -y);
		upd1(0, mx, 1, -y, tmp);
		upd2(0, mx, 1, 0, -y - 1, c);
	}
	prl(ans+qry(0,mx,1,0,mx));
    return 0;
}

Compilation message

dishes.cpp:60:1: warning: multi-line comment [-Wcomment]
 //  / \
 ^
dishes.cpp: In function 'int main()':
dishes.cpp:98: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:100: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:104: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 484 ms 32248 KB Output is correct
2 Correct 432 ms 31352 KB Output is correct
3 Correct 168 ms 9848 KB Output is correct
4 Correct 359 ms 22704 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 508 ms 27636 KB Output is correct
7 Correct 92 ms 5240 KB Output is correct
8 Correct 90 ms 5112 KB Output is correct
9 Correct 228 ms 9836 KB Output is correct
10 Correct 404 ms 30584 KB Output is correct
11 Correct 137 ms 9752 KB Output is correct

Subtask #2
3.0 / 3.0

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

Subtask #3
7.0 / 7.0

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

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 3 ms 384 KB Output is correct
16 Correct 2 ms 384 KB Output is correct
17 Correct 4 ms 768 KB Output is correct
18 Correct 5 ms 768 KB Output is correct
19 Correct 6 ms 896 KB Output is correct
20 Correct 5 ms 684 KB Output is correct
21 Correct 6 ms 768 KB Output is correct
22 Correct 6 ms 768 KB Output is correct
23 Correct 7 ms 768 KB Output is correct
24 Correct 378 ms 24340 KB Output is correct
25 Correct 378 ms 32452 KB Output is correct
26 Correct 393 ms 32376 KB Output is correct
27 Correct 389 ms 32544 KB Output is correct
28 Correct 468 ms 26196 KB Output is correct
29 Correct 166 ms 11640 KB Output is correct
30 Correct 1036 ms 44100 KB Output is correct
31 Correct 201 ms 21692 KB Output is correct
32 Correct 144 ms 13384 KB Output is correct
33 Correct 580 ms 32096 KB Output is correct
34 Correct 868 ms 39272 KB Output is correct
35 Correct 1000 ms 44452 KB Output is correct
36 Correct 1006 ms 43476 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 3 ms 384 KB Output is correct
16 Correct 2 ms 384 KB Output is correct
17 Correct 4 ms 768 KB Output is correct
18 Correct 5 ms 768 KB Output is correct
19 Correct 6 ms 896 KB Output is correct
20 Correct 5 ms 684 KB Output is correct
21 Correct 6 ms 768 KB Output is correct
22 Correct 6 ms 768 KB Output is correct
23 Correct 7 ms 768 KB Output is correct
24 Correct 378 ms 24340 KB Output is correct
25 Correct 378 ms 32452 KB Output is correct
26 Correct 393 ms 32376 KB Output is correct
27 Correct 389 ms 32544 KB Output is correct
28 Correct 468 ms 26196 KB Output is correct
29 Correct 166 ms 11640 KB Output is correct
30 Correct 1036 ms 44100 KB Output is correct
31 Correct 201 ms 21692 KB Output is correct
32 Correct 144 ms 13384 KB Output is correct
33 Correct 580 ms 32096 KB Output is correct
34 Correct 868 ms 39272 KB Output is correct
35 Correct 1000 ms 44452 KB Output is correct
36 Correct 1006 ms 43476 KB Output is correct
37 Correct 474 ms 32224 KB Output is correct
38 Correct 427 ms 32364 KB Output is correct
39 Correct 460 ms 32460 KB Output is correct
40 Correct 474 ms 32380 KB Output is correct
41 Correct 2 ms 384 KB Output is correct
42 Correct 1232 ms 43896 KB Output is correct
43 Correct 700 ms 31940 KB Output is correct
44 Correct 911 ms 38720 KB Output is correct
45 Correct 1050 ms 44552 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 3 ms 384 KB Output is correct
16 Correct 2 ms 384 KB Output is correct
17 Correct 4 ms 768 KB Output is correct
18 Correct 5 ms 768 KB Output is correct
19 Correct 6 ms 896 KB Output is correct
20 Correct 5 ms 684 KB Output is correct
21 Correct 6 ms 768 KB Output is correct
22 Correct 6 ms 768 KB Output is correct
23 Correct 7 ms 768 KB Output is correct
24 Correct 378 ms 24340 KB Output is correct
25 Correct 378 ms 32452 KB Output is correct
26 Correct 393 ms 32376 KB Output is correct
27 Correct 389 ms 32544 KB Output is correct
28 Correct 468 ms 26196 KB Output is correct
29 Correct 166 ms 11640 KB Output is correct
30 Correct 1036 ms 44100 KB Output is correct
31 Correct 201 ms 21692 KB Output is correct
32 Correct 144 ms 13384 KB Output is correct
33 Correct 580 ms 32096 KB Output is correct
34 Correct 868 ms 39272 KB Output is correct
35 Correct 1000 ms 44452 KB Output is correct
36 Correct 1006 ms 43476 KB Output is correct
37 Correct 474 ms 32224 KB Output is correct
38 Correct 427 ms 32364 KB Output is correct
39 Correct 460 ms 32460 KB Output is correct
40 Correct 474 ms 32380 KB Output is correct
41 Correct 2 ms 384 KB Output is correct
42 Correct 1232 ms 43896 KB Output is correct
43 Correct 700 ms 31940 KB Output is correct
44 Correct 911 ms 38720 KB Output is correct
45 Correct 1050 ms 44552 KB Output is correct
46 Correct 2373 ms 143272 KB Output is correct
47 Correct 2433 ms 143484 KB Output is correct
48 Correct 2496 ms 143392 KB Output is correct
49 Correct 2472 ms 143064 KB Output is correct
50 Correct 7669 ms 203800 KB Output is correct
51 Correct 4048 ms 137248 KB Output is correct
52 Correct 4893 ms 163992 KB Output is correct
53 Correct 6390 ms 198456 KB Output is correct

Subtask #7
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 484 ms 32248 KB Output is correct
2 Correct 432 ms 31352 KB Output is correct
3 Correct 168 ms 9848 KB Output is correct
4 Correct 359 ms 22704 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 508 ms 27636 KB Output is correct
7 Correct 92 ms 5240 KB Output is correct
8 Correct 90 ms 5112 KB Output is correct
9 Correct 228 ms 9836 KB Output is correct
10 Correct 404 ms 30584 KB Output is correct
11 Correct 137 ms 9752 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 3 ms 384 KB Output is correct
15 Correct 3 ms 384 KB Output is correct
16 Correct 2 ms 384 KB Output is correct
17 Correct 2 ms 384 KB Output is correct
18 Correct 2 ms 384 KB Output is correct
19 Correct 2 ms 384 KB Output is correct
20 Correct 2 ms 384 KB Output is correct
21 Correct 2 ms 384 KB Output is correct
22 Correct 2 ms 384 KB Output is correct
23 Correct 2 ms 384 KB Output is correct
24 Correct 2 ms 384 KB Output is correct
25 Correct 2 ms 384 KB Output is correct
26 Correct 3 ms 384 KB Output is correct
27 Correct 2 ms 384 KB Output is correct
28 Correct 4 ms 768 KB Output is correct
29 Correct 5 ms 768 KB Output is correct
30 Correct 6 ms 896 KB Output is correct
31 Correct 5 ms 684 KB Output is correct
32 Correct 6 ms 768 KB Output is correct
33 Correct 6 ms 768 KB Output is correct
34 Correct 7 ms 768 KB Output is correct
35 Correct 378 ms 24340 KB Output is correct
36 Correct 378 ms 32452 KB Output is correct
37 Correct 393 ms 32376 KB Output is correct
38 Correct 389 ms 32544 KB Output is correct
39 Correct 468 ms 26196 KB Output is correct
40 Correct 166 ms 11640 KB Output is correct
41 Correct 1036 ms 44100 KB Output is correct
42 Correct 201 ms 21692 KB Output is correct
43 Correct 144 ms 13384 KB Output is correct
44 Correct 580 ms 32096 KB Output is correct
45 Correct 868 ms 39272 KB Output is correct
46 Correct 1000 ms 44452 KB Output is correct
47 Correct 1006 ms 43476 KB Output is correct
48 Correct 474 ms 32224 KB Output is correct
49 Correct 427 ms 32364 KB Output is correct
50 Correct 460 ms 32460 KB Output is correct
51 Correct 474 ms 32380 KB Output is correct
52 Correct 2 ms 384 KB Output is correct
53 Correct 1232 ms 43896 KB Output is correct
54 Correct 700 ms 31940 KB Output is correct
55 Correct 911 ms 38720 KB Output is correct
56 Correct 1050 ms 44552 KB Output is correct
57 Correct 440 ms 31316 KB Output is correct
58 Correct 406 ms 31372 KB Output is correct
59 Correct 465 ms 31260 KB Output is correct
60 Correct 485 ms 31220 KB Output is correct
61 Correct 1159 ms 43824 KB Output is correct
62 Correct 2 ms 384 KB Output is correct
63 Correct 1133 ms 42836 KB Output is correct
64 Correct 675 ms 30560 KB Output is correct
65 Correct 842 ms 37688 KB Output is correct
66 Correct 975 ms 42340 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 484 ms 32248 KB Output is correct
2 Correct 432 ms 31352 KB Output is correct
3 Correct 168 ms 9848 KB Output is correct
4 Correct 359 ms 22704 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 508 ms 27636 KB Output is correct
7 Correct 92 ms 5240 KB Output is correct
8 Correct 90 ms 5112 KB Output is correct
9 Correct 228 ms 9836 KB Output is correct
10 Correct 404 ms 30584 KB Output is correct
11 Correct 137 ms 9752 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 3 ms 384 KB Output is correct
15 Correct 3 ms 384 KB Output is correct
16 Correct 2 ms 384 KB Output is correct
17 Correct 2 ms 384 KB Output is correct
18 Correct 2 ms 384 KB Output is correct
19 Correct 2 ms 384 KB Output is correct
20 Correct 2 ms 384 KB Output is correct
21 Correct 2 ms 384 KB Output is correct
22 Correct 2 ms 384 KB Output is correct
23 Correct 2 ms 384 KB Output is correct
24 Correct 2 ms 384 KB Output is correct
25 Correct 2 ms 384 KB Output is correct
26 Correct 3 ms 384 KB Output is correct
27 Correct 2 ms 384 KB Output is correct
28 Correct 4 ms 768 KB Output is correct
29 Correct 5 ms 768 KB Output is correct
30 Correct 6 ms 896 KB Output is correct
31 Correct 5 ms 684 KB Output is correct
32 Correct 6 ms 768 KB Output is correct
33 Correct 6 ms 768 KB Output is correct
34 Correct 7 ms 768 KB Output is correct
35 Correct 378 ms 24340 KB Output is correct
36 Correct 378 ms 32452 KB Output is correct
37 Correct 393 ms 32376 KB Output is correct
38 Correct 389 ms 32544 KB Output is correct
39 Correct 468 ms 26196 KB Output is correct
40 Correct 166 ms 11640 KB Output is correct
41 Correct 1036 ms 44100 KB Output is correct
42 Correct 201 ms 21692 KB Output is correct
43 Correct 144 ms 13384 KB Output is correct
44 Correct 580 ms 32096 KB Output is correct
45 Correct 868 ms 39272 KB Output is correct
46 Correct 1000 ms 44452 KB Output is correct
47 Correct 1006 ms 43476 KB Output is correct
48 Correct 474 ms 32224 KB Output is correct
49 Correct 427 ms 32364 KB Output is correct
50 Correct 460 ms 32460 KB Output is correct
51 Correct 474 ms 32380 KB Output is correct
52 Correct 2 ms 384 KB Output is correct
53 Correct 1232 ms 43896 KB Output is correct
54 Correct 700 ms 31940 KB Output is correct
55 Correct 911 ms 38720 KB Output is correct
56 Correct 1050 ms 44552 KB Output is correct
57 Correct 2373 ms 143272 KB Output is correct
58 Correct 2433 ms 143484 KB Output is correct
59 Correct 2496 ms 143392 KB Output is correct
60 Correct 2472 ms 143064 KB Output is correct
61 Correct 7669 ms 203800 KB Output is correct
62 Correct 4048 ms 137248 KB Output is correct
63 Correct 4893 ms 163992 KB Output is correct
64 Correct 6390 ms 198456 KB Output is correct
65 Correct 440 ms 31316 KB Output is correct
66 Correct 406 ms 31372 KB Output is correct
67 Correct 465 ms 31260 KB Output is correct
68 Correct 485 ms 31220 KB Output is correct
69 Correct 1159 ms 43824 KB Output is correct
70 Correct 2 ms 384 KB Output is correct
71 Correct 1133 ms 42836 KB Output is correct
72 Correct 675 ms 30560 KB Output is correct
73 Correct 842 ms 37688 KB Output is correct
74 Correct 975 ms 42340 KB Output is correct
75 Correct 2264 ms 143516 KB Output is correct
76 Correct 2395 ms 143472 KB Output is correct
77 Correct 2306 ms 143220 KB Output is correct
78 Correct 2379 ms 143408 KB Output is correct
79 Correct 6658 ms 203848 KB Output is correct
80 Correct 3510 ms 137388 KB Output is correct
81 Correct 4602 ms 165928 KB Output is correct
82 Correct 6474 ms 202300 KB Output is correct
83 Correct 6645 ms 194580 KB Output is correct