oj.uz

Submission #123456

# Submission time Handle Problem Language Result Execution time Memory
123456 2019-07-01T13:16:53 Z youngyojun Two Dishes (JOI19_dishes) C++11
82 / 100
 10000 ms 174768 KB 
#include <bits/stdc++.h>
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#define rb(x) ((x)&(-(x)))
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
 
const bool debug = 0;
 
const int MAXN = 1000055;
const int MAXM = 1000055;
 
struct BIT {
	ll d[MAXN];
 
	void upd(int x, ll r) {
		for(x += 5; x < MAXN; x += rb(x))
			d[x] += r;
	}
	ll get(int x) {
		ll r = 0; for(x += 5; x; x -= rb(x))
			r += d[x];
		return r;
	}
	ll get(int s, int e) { return s > e ? 0 : get(e) - get(s-1); }
} bit;
 
struct SEG {
	ll ds[MAXN*3];
	bitset<MAXN*3> dz;
 
	void prop(int i, int s, int e) {
		if(dz[i]) {
			ds[i] = 0;
			if(s != e) dz[i<<1] = dz[i<<1|1] = true;
			dz[i] = false;
			return;
		}
		if(s == e) return;
		ds[i] = 0;
		if(!dz[i<<1]) ds[i] += ds[i<<1];
		if(!dz[i<<1|1]) ds[i] += ds[i<<1|1];
	}
	void updz(int i, int s, int e, int p, int q) {
		prop(i, s, e); if(q < p || e < p || q < s) return;
		if(p <= s && e <= q) {
			dz[i] = true;
			prop(i, s, e);
			return;
		}
		int m = (s+e) >> 1;
		updz(i<<1, s, m, p, q);
		updz(i<<1|1, m+1, e, p, q);
		ds[i] = ds[i<<1] + ds[i<<1|1];
	}
	void updp(int i, int s, int e, int x, ll r) {
		prop(i, s, e); if(x < s || e < x) return;
		if(s == e) {
			ds[i] = r;
			return;
		}
		int m = (s+e) >> 1;
		updp(i<<1, s, m, x, r);
		updp(i<<1|1, m+1, e, x, r);
		ds[i] = ds[i<<1] + ds[i<<1|1];
	}
	void upddx(int i, int s, int e, int x, ll r) {
		prop(i, s, e); if(x < s || e < x) return;
		if(s == e) {
			ds[i] += r;
			return;
		}
		int m = (s+e) >> 1;
		upddx(i<<1, s, m, x, r);
		upddx(i<<1|1, m+1, e, x, r);
		ds[i] = ds[i<<1] + ds[i<<1|1];
	}
	ll get(int i, int s, int e, int p, int q) {
		prop(i, s, e); if(q < p || e < p || q < s) return 0;
		if(p <= s && e <= q) return ds[i];
		int m = (s+e) >> 1;
		ll ret = get(i<<1, s, m, p, q) + get(i<<1|1, m+1, e, p, q);
		ds[i] = ds[i<<1] + ds[i<<1|1];
		return ret;
	}
	ll get(int i, int s, int e, int x) { return get(1, s, e, x, x); }
} seg;

vector<pii> PopEV[MAXM];
vector<pii> PushEV[MAXM];

ll SA[MAXN], SB[MAXM];
int FI[MAXN], GI[MAXM];

ll C[MAXN], D[MAXM];
int A[MAXN], B[MAXM];
int E[MAXN], F[MAXM];

ll Delta;
int N, M;

int main() {
	ios::sync_with_stdio(false);

	cin >> N >> M;
	for(int i = 1; i <= N; i++)
		cin >> A[i] >> C[i] >> E[i];
	for(int i = 1; i <= M; i++)
		cin >> B[i] >> D[i] >> F[i];
	
	for(int i = 1; i <= N; i++) SA[i] = SA[i-1] + A[i];
	for(int i = 1; i <= M; i++) SB[i] = SB[i-1] + B[i];

	for(int i = 1; i <= N; i++)
		FI[i] = int(upper_bound(SB, SB+M+1, C[i]-SA[i])-SB) - 1;
	for(int i = 1; i <= M; i++)
		GI[i] = int(upper_bound(SA, SA+N+1, D[i]-SB[i])-SA) - 1;

	for(int i = 1; i <= N; i++) if(0 <= FI[i] && E[i]) {
		if(0 < E[i]) {
			PopEV[FI[i]+1].eb(i, E[i]);
			bit.upd(i, E[i]);
		} else {
			Delta += E[i];
			if(FI[i] < M) PushEV[FI[i]+1].eb(i-1, -E[i]);
		}
	}
	for(int i = 1; i <= M; i++) if(0 <= GI[i] && F[i]) {
		if(0 < F[i]) PushEV[i].eb(GI[i], F[i]);
		else {
			Delta += F[i];
			if(GI[i] < N) {
				PopEV[i].eb(GI[i]+1, -F[i]);
				bit.upd(GI[i]+1, -F[i]);
			}
		}
	}
	
	if(debug) {
		printf("N=%d, M=%d\n", N, M);
		for(int i = 1; i <= N; i++) printf("%d ", FI[i]);
		puts("");
		for(int i = 1; i <= M; i++) printf("%d ", GI[i]);
		puts("");
	}
	
	for(int j = 1; j <= M; j++) {
		for(auto &ev : PopEV[j]) {
			int i, ei; tie(i, ei) = ev;
			bit.upd(i, -ei);
			seg.upddx(1, 1, N, i, ei);
			if(debug) {
				printf("j=%d, pop %d %d\n", j, i, ei);
			}
		}

		for(auto &ev : PushEV[j]) {
			int i, ei; tie(i, ei) = ev;
			Delta += ei;
			int s = i+1, e = N+1; for(int m; s < e;) {
				m = (s+e) >> 1;
				if(seg.get(1, 1, N, i+1, m) < ei) s = m+1;
				else e = m;
			}
			ll t = seg.get(1, 1, N, i+1, s-1);
			seg.updz(1, 1, N, i+1, s-1);
			if(s <= N) seg.upddx(1, 1, N, s, t-ei);
		}

		if(debug) {
			printf("j=%d / %lld\n", j, Delta);
			for(int i = 1; i <= N; i++) printf("%lld ", bit.get(i, i));
			puts("");
			for(int i = 1; i <= N; i++) printf("%lld ", seg.get(1, 1, N, i));
			puts("");
		}
	}

	cout << bit.get(1, N) + seg.get(1, 1, N, 1, N) + Delta << endl;
	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2332 ms 75512 KB Output is correct
2 Correct 1878 ms 75636 KB Output is correct
3 Correct 297 ms 69224 KB Output is correct
4 Correct 1714 ms 72484 KB Output is correct
5 Correct 46 ms 47740 KB Output is correct
6 Correct 1658 ms 73560 KB Output is correct
7 Correct 165 ms 60152 KB Output is correct
8 Correct 163 ms 57832 KB Output is correct
9 Correct 309 ms 69224 KB Output is correct
10 Correct 2200 ms 78200 KB Output is correct
11 Correct 234 ms 69540 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 47864 KB Output is correct
2 Correct 45 ms 47720 KB Output is correct
3 Correct 45 ms 47736 KB Output is correct
4 Correct 44 ms 47824 KB Output is correct
5 Correct 44 ms 47864 KB Output is correct
6 Correct 45 ms 47864 KB Output is correct
7 Correct 45 ms 47736 KB Output is correct
8 Correct 45 ms 47864 KB Output is correct
9 Correct 46 ms 47864 KB Output is correct
10 Correct 45 ms 47864 KB Output is correct
11 Correct 45 ms 47864 KB Output is correct
12 Correct 45 ms 47864 KB Output is correct
13 Correct 53 ms 47868 KB Output is correct
14 Correct 52 ms 47920 KB Output is correct
15 Correct 46 ms 47864 KB Output is correct
16 Correct 50 ms 47864 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 47864 KB Output is correct
2 Correct 45 ms 47720 KB Output is correct
3 Correct 45 ms 47736 KB Output is correct
4 Correct 44 ms 47824 KB Output is correct
5 Correct 44 ms 47864 KB Output is correct
6 Correct 45 ms 47864 KB Output is correct
7 Correct 45 ms 47736 KB Output is correct
8 Correct 45 ms 47864 KB Output is correct
9 Correct 46 ms 47864 KB Output is correct
10 Correct 45 ms 47864 KB Output is correct
11 Correct 45 ms 47864 KB Output is correct
12 Correct 45 ms 47864 KB Output is correct
13 Correct 53 ms 47868 KB Output is correct
14 Correct 52 ms 47920 KB Output is correct
15 Correct 46 ms 47864 KB Output is correct
16 Correct 50 ms 47864 KB Output is correct
17 Correct 50 ms 48120 KB Output is correct
18 Correct 59 ms 48208 KB Output is correct
19 Correct 58 ms 48120 KB Output is correct
20 Correct 53 ms 48120 KB Output is correct
21 Correct 55 ms 48120 KB Output is correct
22 Correct 65 ms 48144 KB Output is correct
23 Correct 58 ms 48120 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 47864 KB Output is correct
2 Correct 45 ms 47720 KB Output is correct
3 Correct 45 ms 47736 KB Output is correct
4 Correct 44 ms 47824 KB Output is correct
5 Correct 44 ms 47864 KB Output is correct
6 Correct 45 ms 47864 KB Output is correct
7 Correct 45 ms 47736 KB Output is correct
8 Correct 45 ms 47864 KB Output is correct
9 Correct 46 ms 47864 KB Output is correct
10 Correct 45 ms 47864 KB Output is correct
11 Correct 45 ms 47864 KB Output is correct
12 Correct 45 ms 47864 KB Output is correct
13 Correct 53 ms 47868 KB Output is correct
14 Correct 52 ms 47920 KB Output is correct
15 Correct 46 ms 47864 KB Output is correct
16 Correct 50 ms 47864 KB Output is correct
17 Correct 50 ms 48120 KB Output is correct
18 Correct 59 ms 48208 KB Output is correct
19 Correct 58 ms 48120 KB Output is correct
20 Correct 53 ms 48120 KB Output is correct
21 Correct 55 ms 48120 KB Output is correct
22 Correct 65 ms 48144 KB Output is correct
23 Correct 58 ms 48120 KB Output is correct
24 Correct 333 ms 70368 KB Output is correct
25 Correct 1519 ms 68792 KB Output is correct
26 Correct 353 ms 75048 KB Output is correct
27 Correct 2341 ms 72968 KB Output is correct
28 Correct 982 ms 73452 KB Output is correct
29 Correct 269 ms 69356 KB Output is correct
30 Correct 2952 ms 75904 KB Output is correct
31 Correct 154 ms 60792 KB Output is correct
32 Correct 189 ms 61876 KB Output is correct
33 Correct 1622 ms 71064 KB Output is correct
34 Correct 2199 ms 74560 KB Output is correct
35 Correct 2942 ms 76076 KB Output is correct
36 Correct 2852 ms 75816 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 47864 KB Output is correct
2 Correct 45 ms 47720 KB Output is correct
3 Correct 45 ms 47736 KB Output is correct
4 Correct 44 ms 47824 KB Output is correct
5 Correct 44 ms 47864 KB Output is correct
6 Correct 45 ms 47864 KB Output is correct
7 Correct 45 ms 47736 KB Output is correct
8 Correct 45 ms 47864 KB Output is correct
9 Correct 46 ms 47864 KB Output is correct
10 Correct 45 ms 47864 KB Output is correct
11 Correct 45 ms 47864 KB Output is correct
12 Correct 45 ms 47864 KB Output is correct
13 Correct 53 ms 47868 KB Output is correct
14 Correct 52 ms 47920 KB Output is correct
15 Correct 46 ms 47864 KB Output is correct
16 Correct 50 ms 47864 KB Output is correct
17 Correct 50 ms 48120 KB Output is correct
18 Correct 59 ms 48208 KB Output is correct
19 Correct 58 ms 48120 KB Output is correct
20 Correct 53 ms 48120 KB Output is correct
21 Correct 55 ms 48120 KB Output is correct
22 Correct 65 ms 48144 KB Output is correct
23 Correct 58 ms 48120 KB Output is correct
24 Correct 333 ms 70368 KB Output is correct
25 Correct 1519 ms 68792 KB Output is correct
26 Correct 353 ms 75048 KB Output is correct
27 Correct 2341 ms 72968 KB Output is correct
28 Correct 982 ms 73452 KB Output is correct
29 Correct 269 ms 69356 KB Output is correct
30 Correct 2952 ms 75904 KB Output is correct
31 Correct 154 ms 60792 KB Output is correct
32 Correct 189 ms 61876 KB Output is correct
33 Correct 1622 ms 71064 KB Output is correct
34 Correct 2199 ms 74560 KB Output is correct
35 Correct 2942 ms 76076 KB Output is correct
36 Correct 2852 ms 75816 KB Output is correct
37 Correct 382 ms 75128 KB Output is correct
38 Correct 2386 ms 72736 KB Output is correct
39 Correct 2700 ms 78232 KB Output is correct
40 Correct 2104 ms 78212 KB Output is correct
41 Correct 44 ms 47864 KB Output is correct
42 Correct 2978 ms 76008 KB Output is correct
43 Correct 1641 ms 70904 KB Output is correct
44 Correct 2205 ms 74408 KB Output is correct
45 Correct 3009 ms 75848 KB Output is correct

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 47864 KB Output is correct
2 Correct 45 ms 47720 KB Output is correct
3 Correct 45 ms 47736 KB Output is correct
4 Correct 44 ms 47824 KB Output is correct
5 Correct 44 ms 47864 KB Output is correct
6 Correct 45 ms 47864 KB Output is correct
7 Correct 45 ms 47736 KB Output is correct
8 Correct 45 ms 47864 KB Output is correct
9 Correct 46 ms 47864 KB Output is correct
10 Correct 45 ms 47864 KB Output is correct
11 Correct 45 ms 47864 KB Output is correct
12 Correct 45 ms 47864 KB Output is correct
13 Correct 53 ms 47868 KB Output is correct
14 Correct 52 ms 47920 KB Output is correct
15 Correct 46 ms 47864 KB Output is correct
16 Correct 50 ms 47864 KB Output is correct
17 Correct 50 ms 48120 KB Output is correct
18 Correct 59 ms 48208 KB Output is correct
19 Correct 58 ms 48120 KB Output is correct
20 Correct 53 ms 48120 KB Output is correct
21 Correct 55 ms 48120 KB Output is correct
22 Correct 65 ms 48144 KB Output is correct
23 Correct 58 ms 48120 KB Output is correct
24 Correct 333 ms 70368 KB Output is correct
25 Correct 1519 ms 68792 KB Output is correct
26 Correct 353 ms 75048 KB Output is correct
27 Correct 2341 ms 72968 KB Output is correct
28 Correct 982 ms 73452 KB Output is correct
29 Correct 269 ms 69356 KB Output is correct
30 Correct 2952 ms 75904 KB Output is correct
31 Correct 154 ms 60792 KB Output is correct
32 Correct 189 ms 61876 KB Output is correct
33 Correct 1622 ms 71064 KB Output is correct
34 Correct 2199 ms 74560 KB Output is correct
35 Correct 2942 ms 76076 KB Output is correct
36 Correct 2852 ms 75816 KB Output is correct
37 Correct 382 ms 75128 KB Output is correct
38 Correct 2386 ms 72736 KB Output is correct
39 Correct 2700 ms 78232 KB Output is correct
40 Correct 2104 ms 78212 KB Output is correct
41 Correct 44 ms 47864 KB Output is correct
42 Correct 2978 ms 76008 KB Output is correct
43 Correct 1641 ms 70904 KB Output is correct
44 Correct 2205 ms 74408 KB Output is correct
45 Correct 3009 ms 75848 KB Output is correct
46 Correct 1775 ms 174768 KB Output is correct
47 Execution timed out 10067 ms 158160 KB Time limit exceeded
48 Halted 0 ms 0 KB -

Subtask #7
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2332 ms 75512 KB Output is correct
2 Correct 1878 ms 75636 KB Output is correct
3 Correct 297 ms 69224 KB Output is correct
4 Correct 1714 ms 72484 KB Output is correct
5 Correct 46 ms 47740 KB Output is correct
6 Correct 1658 ms 73560 KB Output is correct
7 Correct 165 ms 60152 KB Output is correct
8 Correct 163 ms 57832 KB Output is correct
9 Correct 309 ms 69224 KB Output is correct
10 Correct 2200 ms 78200 KB Output is correct
11 Correct 234 ms 69540 KB Output is correct
12 Correct 44 ms 47864 KB Output is correct
13 Correct 45 ms 47720 KB Output is correct
14 Correct 45 ms 47736 KB Output is correct
15 Correct 44 ms 47824 KB Output is correct
16 Correct 44 ms 47864 KB Output is correct
17 Correct 45 ms 47864 KB Output is correct
18 Correct 45 ms 47736 KB Output is correct
19 Correct 45 ms 47864 KB Output is correct
20 Correct 46 ms 47864 KB Output is correct
21 Correct 45 ms 47864 KB Output is correct
22 Correct 45 ms 47864 KB Output is correct
23 Correct 45 ms 47864 KB Output is correct
24 Correct 53 ms 47868 KB Output is correct
25 Correct 52 ms 47920 KB Output is correct
26 Correct 46 ms 47864 KB Output is correct
27 Correct 50 ms 47864 KB Output is correct
28 Correct 50 ms 48120 KB Output is correct
29 Correct 59 ms 48208 KB Output is correct
30 Correct 58 ms 48120 KB Output is correct
31 Correct 53 ms 48120 KB Output is correct
32 Correct 55 ms 48120 KB Output is correct
33 Correct 65 ms 48144 KB Output is correct
34 Correct 58 ms 48120 KB Output is correct
35 Correct 333 ms 70368 KB Output is correct
36 Correct 1519 ms 68792 KB Output is correct
37 Correct 353 ms 75048 KB Output is correct
38 Correct 2341 ms 72968 KB Output is correct
39 Correct 982 ms 73452 KB Output is correct
40 Correct 269 ms 69356 KB Output is correct
41 Correct 2952 ms 75904 KB Output is correct
42 Correct 154 ms 60792 KB Output is correct
43 Correct 189 ms 61876 KB Output is correct
44 Correct 1622 ms 71064 KB Output is correct
45 Correct 2199 ms 74560 KB Output is correct
46 Correct 2942 ms 76076 KB Output is correct
47 Correct 2852 ms 75816 KB Output is correct
48 Correct 382 ms 75128 KB Output is correct
49 Correct 2386 ms 72736 KB Output is correct
50 Correct 2700 ms 78232 KB Output is correct
51 Correct 2104 ms 78212 KB Output is correct
52 Correct 44 ms 47864 KB Output is correct
53 Correct 2978 ms 76008 KB Output is correct
54 Correct 1641 ms 70904 KB Output is correct
55 Correct 2205 ms 74408 KB Output is correct
56 Correct 3009 ms 75848 KB Output is correct
57 Correct 2367 ms 70808 KB Output is correct
58 Correct 372 ms 71928 KB Output is correct
59 Correct 442 ms 72056 KB Output is correct
60 Correct 4935 ms 78332 KB Output is correct
61 Correct 302 ms 67952 KB Output is correct
62 Correct 45 ms 47736 KB Output is correct
63 Correct 3045 ms 82676 KB Output is correct
64 Correct 1664 ms 78716 KB Output is correct
65 Correct 2293 ms 81324 KB Output is correct
66 Correct 2916 ms 80908 KB Output is correct

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2332 ms 75512 KB Output is correct
2 Correct 1878 ms 75636 KB Output is correct
3 Correct 297 ms 69224 KB Output is correct
4 Correct 1714 ms 72484 KB Output is correct
5 Correct 46 ms 47740 KB Output is correct
6 Correct 1658 ms 73560 KB Output is correct
7 Correct 165 ms 60152 KB Output is correct
8 Correct 163 ms 57832 KB Output is correct
9 Correct 309 ms 69224 KB Output is correct
10 Correct 2200 ms 78200 KB Output is correct
11 Correct 234 ms 69540 KB Output is correct
12 Correct 44 ms 47864 KB Output is correct
13 Correct 45 ms 47720 KB Output is correct
14 Correct 45 ms 47736 KB Output is correct
15 Correct 44 ms 47824 KB Output is correct
16 Correct 44 ms 47864 KB Output is correct
17 Correct 45 ms 47864 KB Output is correct
18 Correct 45 ms 47736 KB Output is correct
19 Correct 45 ms 47864 KB Output is correct
20 Correct 46 ms 47864 KB Output is correct
21 Correct 45 ms 47864 KB Output is correct
22 Correct 45 ms 47864 KB Output is correct
23 Correct 45 ms 47864 KB Output is correct
24 Correct 53 ms 47868 KB Output is correct
25 Correct 52 ms 47920 KB Output is correct
26 Correct 46 ms 47864 KB Output is correct
27 Correct 50 ms 47864 KB Output is correct
28 Correct 50 ms 48120 KB Output is correct
29 Correct 59 ms 48208 KB Output is correct
30 Correct 58 ms 48120 KB Output is correct
31 Correct 53 ms 48120 KB Output is correct
32 Correct 55 ms 48120 KB Output is correct
33 Correct 65 ms 48144 KB Output is correct
34 Correct 58 ms 48120 KB Output is correct
35 Correct 333 ms 70368 KB Output is correct
36 Correct 1519 ms 68792 KB Output is correct
37 Correct 353 ms 75048 KB Output is correct
38 Correct 2341 ms 72968 KB Output is correct
39 Correct 982 ms 73452 KB Output is correct
40 Correct 269 ms 69356 KB Output is correct
41 Correct 2952 ms 75904 KB Output is correct
42 Correct 154 ms 60792 KB Output is correct
43 Correct 189 ms 61876 KB Output is correct
44 Correct 1622 ms 71064 KB Output is correct
45 Correct 2199 ms 74560 KB Output is correct
46 Correct 2942 ms 76076 KB Output is correct
47 Correct 2852 ms 75816 KB Output is correct
48 Correct 382 ms 75128 KB Output is correct
49 Correct 2386 ms 72736 KB Output is correct
50 Correct 2700 ms 78232 KB Output is correct
51 Correct 2104 ms 78212 KB Output is correct
52 Correct 44 ms 47864 KB Output is correct
53 Correct 2978 ms 76008 KB Output is correct
54 Correct 1641 ms 70904 KB Output is correct
55 Correct 2205 ms 74408 KB Output is correct
56 Correct 3009 ms 75848 KB Output is correct
57 Correct 1775 ms 174768 KB Output is correct
58 Execution timed out 10067 ms 158160 KB Time limit exceeded
59 Halted 0 ms 0 KB -