oj.uz

Submission #106865

# Submission time Handle Problem Language Result Execution time Memory
106865 2019-04-20T19:14:09 Z eriksuenderhauf Two Dishes (JOI19_dishes) C++11
100 / 100
 8058 ms 237416 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) {
	seg[k] += lazy[k];
	prop(l,r,k);
	if (r < a || b < l || a > b) return -INF;
	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));
}

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) {
	seg[k] += lazy[k];
	prop(l,r,k);
	if (b < l || r < a || a > b) return;
	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];
	}
	for (auto &it: pts) {
		int x, y;
		tie(x, y) = it.fi;
		ll c = it.se;
		ll tmp = qry(0, 2*MAXN-1, 1, 0, -y - 1);
		upd1(0, 2*MAXN-1, 1, -y, tmp);
		upd2(0, 2*MAXN-1, 1, 0, -y - 1, c);
	}
	prl(ans+qry(0,2*MAXN-1,1,0,2*MAXN-1));
    return 0;
}

Compilation message

dishes.cpp: In function 'int main()':
dishes.cpp:91: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:93: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:97: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 512 ms 31224 KB Output is correct
2 Correct 592 ms 30328 KB Output is correct
3 Correct 237 ms 10164 KB Output is correct
4 Correct 396 ms 22200 KB Output is correct
5 Correct 2 ms 512 KB Output is correct
6 Correct 504 ms 26756 KB Output is correct
7 Correct 97 ms 5496 KB Output is correct
8 Correct 90 ms 5368 KB Output is correct
9 Correct 217 ms 10232 KB Output is correct
10 Correct 457 ms 29304 KB Output is correct
11 Correct 130 ms 10104 KB Output is correct

Subtask #2
3.0 / 3.0

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

Subtask #3
7.0 / 7.0

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

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 484 KB Output is correct
5 Correct 2 ms 512 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 2 ms 512 KB Output is correct
8 Correct 2 ms 512 KB Output is correct
9 Correct 2 ms 512 KB Output is correct
10 Correct 2 ms 512 KB Output is correct
11 Correct 2 ms 512 KB Output is correct
12 Correct 2 ms 512 KB Output is correct
13 Correct 3 ms 512 KB Output is correct
14 Correct 2 ms 512 KB Output is correct
15 Correct 2 ms 512 KB Output is correct
16 Correct 2 ms 512 KB Output is correct
17 Correct 8 ms 896 KB Output is correct
18 Correct 6 ms 896 KB Output is correct
19 Correct 10 ms 1024 KB Output is correct
20 Correct 7 ms 896 KB Output is correct
21 Correct 9 ms 896 KB Output is correct
22 Correct 10 ms 896 KB Output is correct
23 Correct 9 ms 896 KB Output is correct
24 Correct 551 ms 33128 KB Output is correct
25 Correct 424 ms 39544 KB Output is correct
26 Correct 452 ms 39800 KB Output is correct
27 Correct 448 ms 39672 KB Output is correct
28 Correct 436 ms 33528 KB Output is correct
29 Correct 171 ms 20984 KB Output is correct
30 Correct 1247 ms 51488 KB Output is correct
31 Correct 234 ms 23288 KB Output is correct
32 Correct 235 ms 16748 KB Output is correct
33 Correct 708 ms 39012 KB Output is correct
34 Correct 1039 ms 46288 KB Output is correct
35 Correct 1159 ms 45276 KB Output is correct
36 Correct 1109 ms 44536 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 484 KB Output is correct
5 Correct 2 ms 512 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 2 ms 512 KB Output is correct
8 Correct 2 ms 512 KB Output is correct
9 Correct 2 ms 512 KB Output is correct
10 Correct 2 ms 512 KB Output is correct
11 Correct 2 ms 512 KB Output is correct
12 Correct 2 ms 512 KB Output is correct
13 Correct 3 ms 512 KB Output is correct
14 Correct 2 ms 512 KB Output is correct
15 Correct 2 ms 512 KB Output is correct
16 Correct 2 ms 512 KB Output is correct
17 Correct 8 ms 896 KB Output is correct
18 Correct 6 ms 896 KB Output is correct
19 Correct 10 ms 1024 KB Output is correct
20 Correct 7 ms 896 KB Output is correct
21 Correct 9 ms 896 KB Output is correct
22 Correct 10 ms 896 KB Output is correct
23 Correct 9 ms 896 KB Output is correct
24 Correct 551 ms 33128 KB Output is correct
25 Correct 424 ms 39544 KB Output is correct
26 Correct 452 ms 39800 KB Output is correct
27 Correct 448 ms 39672 KB Output is correct
28 Correct 436 ms 33528 KB Output is correct
29 Correct 171 ms 20984 KB Output is correct
30 Correct 1247 ms 51488 KB Output is correct
31 Correct 234 ms 23288 KB Output is correct
32 Correct 235 ms 16748 KB Output is correct
33 Correct 708 ms 39012 KB Output is correct
34 Correct 1039 ms 46288 KB Output is correct
35 Correct 1159 ms 45276 KB Output is correct
36 Correct 1109 ms 44536 KB Output is correct
37 Correct 485 ms 42200 KB Output is correct
38 Correct 503 ms 42360 KB Output is correct
39 Correct 564 ms 40108 KB Output is correct
40 Correct 503 ms 40028 KB Output is correct
41 Correct 2 ms 512 KB Output is correct
42 Correct 1286 ms 53852 KB Output is correct
43 Correct 819 ms 41724 KB Output is correct
44 Correct 1093 ms 48376 KB Output is correct
45 Correct 1208 ms 48376 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 484 KB Output is correct
5 Correct 2 ms 512 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 2 ms 512 KB Output is correct
8 Correct 2 ms 512 KB Output is correct
9 Correct 2 ms 512 KB Output is correct
10 Correct 2 ms 512 KB Output is correct
11 Correct 2 ms 512 KB Output is correct
12 Correct 2 ms 512 KB Output is correct
13 Correct 3 ms 512 KB Output is correct
14 Correct 2 ms 512 KB Output is correct
15 Correct 2 ms 512 KB Output is correct
16 Correct 2 ms 512 KB Output is correct
17 Correct 8 ms 896 KB Output is correct
18 Correct 6 ms 896 KB Output is correct
19 Correct 10 ms 1024 KB Output is correct
20 Correct 7 ms 896 KB Output is correct
21 Correct 9 ms 896 KB Output is correct
22 Correct 10 ms 896 KB Output is correct
23 Correct 9 ms 896 KB Output is correct
24 Correct 551 ms 33128 KB Output is correct
25 Correct 424 ms 39544 KB Output is correct
26 Correct 452 ms 39800 KB Output is correct
27 Correct 448 ms 39672 KB Output is correct
28 Correct 436 ms 33528 KB Output is correct
29 Correct 171 ms 20984 KB Output is correct
30 Correct 1247 ms 51488 KB Output is correct
31 Correct 234 ms 23288 KB Output is correct
32 Correct 235 ms 16748 KB Output is correct
33 Correct 708 ms 39012 KB Output is correct
34 Correct 1039 ms 46288 KB Output is correct
35 Correct 1159 ms 45276 KB Output is correct
36 Correct 1109 ms 44536 KB Output is correct
37 Correct 485 ms 42200 KB Output is correct
38 Correct 503 ms 42360 KB Output is correct
39 Correct 564 ms 40108 KB Output is correct
40 Correct 503 ms 40028 KB Output is correct
41 Correct 2 ms 512 KB Output is correct
42 Correct 1286 ms 53852 KB Output is correct
43 Correct 819 ms 41724 KB Output is correct
44 Correct 1093 ms 48376 KB Output is correct
45 Correct 1208 ms 48376 KB Output is correct
46 Correct 2573 ms 212996 KB Output is correct
47 Correct 2565 ms 213124 KB Output is correct
48 Correct 2573 ms 199276 KB Output is correct
49 Correct 2784 ms 199404 KB Output is correct
50 Correct 7860 ms 204996 KB Output is correct
51 Correct 3959 ms 204208 KB Output is correct
52 Correct 5810 ms 226188 KB Output is correct
53 Correct 7940 ms 237416 KB Output is correct

Subtask #7
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 512 ms 31224 KB Output is correct
2 Correct 592 ms 30328 KB Output is correct
3 Correct 237 ms 10164 KB Output is correct
4 Correct 396 ms 22200 KB Output is correct
5 Correct 2 ms 512 KB Output is correct
6 Correct 504 ms 26756 KB Output is correct
7 Correct 97 ms 5496 KB Output is correct
8 Correct 90 ms 5368 KB Output is correct
9 Correct 217 ms 10232 KB Output is correct
10 Correct 457 ms 29304 KB Output is correct
11 Correct 130 ms 10104 KB Output is correct
12 Correct 2 ms 512 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 2 ms 484 KB Output is correct
16 Correct 2 ms 512 KB Output is correct
17 Correct 3 ms 512 KB Output is correct
18 Correct 2 ms 512 KB Output is correct
19 Correct 2 ms 512 KB Output is correct
20 Correct 2 ms 512 KB Output is correct
21 Correct 2 ms 512 KB Output is correct
22 Correct 2 ms 512 KB Output is correct
23 Correct 2 ms 512 KB Output is correct
24 Correct 3 ms 512 KB Output is correct
25 Correct 2 ms 512 KB Output is correct
26 Correct 2 ms 512 KB Output is correct
27 Correct 2 ms 512 KB Output is correct
28 Correct 8 ms 896 KB Output is correct
29 Correct 6 ms 896 KB Output is correct
30 Correct 10 ms 1024 KB Output is correct
31 Correct 7 ms 896 KB Output is correct
32 Correct 9 ms 896 KB Output is correct
33 Correct 10 ms 896 KB Output is correct
34 Correct 9 ms 896 KB Output is correct
35 Correct 551 ms 33128 KB Output is correct
36 Correct 424 ms 39544 KB Output is correct
37 Correct 452 ms 39800 KB Output is correct
38 Correct 448 ms 39672 KB Output is correct
39 Correct 436 ms 33528 KB Output is correct
40 Correct 171 ms 20984 KB Output is correct
41 Correct 1247 ms 51488 KB Output is correct
42 Correct 234 ms 23288 KB Output is correct
43 Correct 235 ms 16748 KB Output is correct
44 Correct 708 ms 39012 KB Output is correct
45 Correct 1039 ms 46288 KB Output is correct
46 Correct 1159 ms 45276 KB Output is correct
47 Correct 1109 ms 44536 KB Output is correct
48 Correct 485 ms 42200 KB Output is correct
49 Correct 503 ms 42360 KB Output is correct
50 Correct 564 ms 40108 KB Output is correct
51 Correct 503 ms 40028 KB Output is correct
52 Correct 2 ms 512 KB Output is correct
53 Correct 1286 ms 53852 KB Output is correct
54 Correct 819 ms 41724 KB Output is correct
55 Correct 1093 ms 48376 KB Output is correct
56 Correct 1208 ms 48376 KB Output is correct
57 Correct 510 ms 42884 KB Output is correct
58 Correct 510 ms 42616 KB Output is correct
59 Correct 552 ms 41092 KB Output is correct
60 Correct 573 ms 41136 KB Output is correct
61 Correct 1390 ms 52344 KB Output is correct
62 Correct 3 ms 512 KB Output is correct
63 Correct 1404 ms 54296 KB Output is correct
64 Correct 748 ms 41592 KB Output is correct
65 Correct 1057 ms 49032 KB Output is correct
66 Correct 1219 ms 47668 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 512 ms 31224 KB Output is correct
2 Correct 592 ms 30328 KB Output is correct
3 Correct 237 ms 10164 KB Output is correct
4 Correct 396 ms 22200 KB Output is correct
5 Correct 2 ms 512 KB Output is correct
6 Correct 504 ms 26756 KB Output is correct
7 Correct 97 ms 5496 KB Output is correct
8 Correct 90 ms 5368 KB Output is correct
9 Correct 217 ms 10232 KB Output is correct
10 Correct 457 ms 29304 KB Output is correct
11 Correct 130 ms 10104 KB Output is correct
12 Correct 2 ms 512 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 2 ms 484 KB Output is correct
16 Correct 2 ms 512 KB Output is correct
17 Correct 3 ms 512 KB Output is correct
18 Correct 2 ms 512 KB Output is correct
19 Correct 2 ms 512 KB Output is correct
20 Correct 2 ms 512 KB Output is correct
21 Correct 2 ms 512 KB Output is correct
22 Correct 2 ms 512 KB Output is correct
23 Correct 2 ms 512 KB Output is correct
24 Correct 3 ms 512 KB Output is correct
25 Correct 2 ms 512 KB Output is correct
26 Correct 2 ms 512 KB Output is correct
27 Correct 2 ms 512 KB Output is correct
28 Correct 8 ms 896 KB Output is correct
29 Correct 6 ms 896 KB Output is correct
30 Correct 10 ms 1024 KB Output is correct
31 Correct 7 ms 896 KB Output is correct
32 Correct 9 ms 896 KB Output is correct
33 Correct 10 ms 896 KB Output is correct
34 Correct 9 ms 896 KB Output is correct
35 Correct 551 ms 33128 KB Output is correct
36 Correct 424 ms 39544 KB Output is correct
37 Correct 452 ms 39800 KB Output is correct
38 Correct 448 ms 39672 KB Output is correct
39 Correct 436 ms 33528 KB Output is correct
40 Correct 171 ms 20984 KB Output is correct
41 Correct 1247 ms 51488 KB Output is correct
42 Correct 234 ms 23288 KB Output is correct
43 Correct 235 ms 16748 KB Output is correct
44 Correct 708 ms 39012 KB Output is correct
45 Correct 1039 ms 46288 KB Output is correct
46 Correct 1159 ms 45276 KB Output is correct
47 Correct 1109 ms 44536 KB Output is correct
48 Correct 485 ms 42200 KB Output is correct
49 Correct 503 ms 42360 KB Output is correct
50 Correct 564 ms 40108 KB Output is correct
51 Correct 503 ms 40028 KB Output is correct
52 Correct 2 ms 512 KB Output is correct
53 Correct 1286 ms 53852 KB Output is correct
54 Correct 819 ms 41724 KB Output is correct
55 Correct 1093 ms 48376 KB Output is correct
56 Correct 1208 ms 48376 KB Output is correct
57 Correct 2573 ms 212996 KB Output is correct
58 Correct 2565 ms 213124 KB Output is correct
59 Correct 2573 ms 199276 KB Output is correct
60 Correct 2784 ms 199404 KB Output is correct
61 Correct 7860 ms 204996 KB Output is correct
62 Correct 3959 ms 204208 KB Output is correct
63 Correct 5810 ms 226188 KB Output is correct
64 Correct 7940 ms 237416 KB Output is correct
65 Correct 510 ms 42884 KB Output is correct
66 Correct 510 ms 42616 KB Output is correct
67 Correct 552 ms 41092 KB Output is correct
68 Correct 573 ms 41136 KB Output is correct
69 Correct 1390 ms 52344 KB Output is correct
70 Correct 3 ms 512 KB Output is correct
71 Correct 1404 ms 54296 KB Output is correct
72 Correct 748 ms 41592 KB Output is correct
73 Correct 1057 ms 49032 KB Output is correct
74 Correct 1219 ms 47668 KB Output is correct
75 Correct 2676 ms 144804 KB Output is correct
76 Correct 2533 ms 144680 KB Output is correct
77 Correct 2802 ms 144412 KB Output is correct
78 Correct 2860 ms 144204 KB Output is correct
79 Correct 8058 ms 204932 KB Output is correct
80 Correct 4550 ms 136528 KB Output is correct
81 Correct 5652 ms 167016 KB Output is correct
82 Correct 7782 ms 202824 KB Output is correct
83 Correct 6906 ms 195628 KB Output is correct