oj.uz

Submission #123285

# Submission time Handle Problem Language Result Execution time Memory
123285 2019-07-01T05:44:49 Z 윤교준(#3020) Two Dishes (JOI19_dishes) C++14
65 / 100
 10000 ms 136228 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;

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<int> PopEV[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++) PopEV[FI[i]+1].eb(i);
	for(int i = 1; i <= N; i++)
		if(0 <= FI[i]) bit.upd(i, E[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(int i : PopEV[j]) {
			bit.upd(i, -E[i]);
			seg.upddx(1, 1, N, i, E[i]);
			if(debug) {
				printf("j=%d, pop %d %d\n", j, i, E[i]);
			}
		}

		if(0 <= GI[j]) {
			Delta += F[j];
			int s = GI[j]+1, e = N+1; for(int m; s < e;) {
				m = (s+e) >> 1;
				if(seg.get(1, 1, N, GI[j]+1, m) < F[j]) s = m+1;
				else e = m;
			}
			ll t = seg.get(1, 1, N, GI[j]+1, s-1);
			if(debug) {
				printf("j=%d, GI=%d, s=%d, t=%lld / %lld\n", j, GI[j], s, t, seg.get(1, 1, N, GI[j]+1, s));
			}
			seg.updz(1, 1, N, GI[j]+1, s-1);
			if(s <= N) seg.upddx(1, 1, N, s, t-F[j]);
		}

		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 2298 ms 47816 KB Output is correct
2 Correct 1842 ms 46932 KB Output is correct
3 Correct 264 ms 40544 KB Output is correct
4 Correct 1691 ms 46964 KB Output is correct
5 Correct 24 ms 24312 KB Output is correct
6 Correct 1631 ms 44972 KB Output is correct
7 Correct 129 ms 34680 KB Output is correct
8 Correct 143 ms 37120 KB Output is correct
9 Correct 268 ms 40280 KB Output is correct
10 Correct 2165 ms 51960 KB Output is correct
11 Correct 198 ms 42248 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 24312 KB Output is correct
2 Correct 24 ms 24312 KB Output is correct
3 Correct 28 ms 24312 KB Output is correct
4 Correct 28 ms 24284 KB Output is correct
5 Correct 28 ms 24316 KB Output is correct
6 Correct 25 ms 24312 KB Output is correct
7 Correct 28 ms 24312 KB Output is correct
8 Correct 28 ms 24312 KB Output is correct
9 Correct 28 ms 24312 KB Output is correct
10 Correct 23 ms 24312 KB Output is correct
11 Correct 24 ms 24312 KB Output is correct
12 Correct 23 ms 24312 KB Output is correct
13 Correct 23 ms 24312 KB Output is correct
14 Correct 24 ms 24312 KB Output is correct
15 Correct 24 ms 24312 KB Output is correct
16 Correct 24 ms 24312 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 24312 KB Output is correct
2 Correct 24 ms 24312 KB Output is correct
3 Correct 28 ms 24312 KB Output is correct
4 Correct 28 ms 24284 KB Output is correct
5 Correct 28 ms 24316 KB Output is correct
6 Correct 25 ms 24312 KB Output is correct
7 Correct 28 ms 24312 KB Output is correct
8 Correct 28 ms 24312 KB Output is correct
9 Correct 28 ms 24312 KB Output is correct
10 Correct 23 ms 24312 KB Output is correct
11 Correct 24 ms 24312 KB Output is correct
12 Correct 23 ms 24312 KB Output is correct
13 Correct 23 ms 24312 KB Output is correct
14 Correct 24 ms 24312 KB Output is correct
15 Correct 24 ms 24312 KB Output is correct
16 Correct 24 ms 24312 KB Output is correct
17 Correct 26 ms 24568 KB Output is correct
18 Correct 29 ms 24696 KB Output is correct
19 Correct 37 ms 24672 KB Output is correct
20 Correct 31 ms 24532 KB Output is correct
21 Correct 33 ms 24568 KB Output is correct
22 Correct 36 ms 24568 KB Output is correct
23 Correct 37 ms 24568 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 24312 KB Output is correct
2 Correct 24 ms 24312 KB Output is correct
3 Correct 28 ms 24312 KB Output is correct
4 Correct 28 ms 24284 KB Output is correct
5 Correct 28 ms 24316 KB Output is correct
6 Correct 25 ms 24312 KB Output is correct
7 Correct 28 ms 24312 KB Output is correct
8 Correct 28 ms 24312 KB Output is correct
9 Correct 28 ms 24312 KB Output is correct
10 Correct 23 ms 24312 KB Output is correct
11 Correct 24 ms 24312 KB Output is correct
12 Correct 23 ms 24312 KB Output is correct
13 Correct 23 ms 24312 KB Output is correct
14 Correct 24 ms 24312 KB Output is correct
15 Correct 24 ms 24312 KB Output is correct
16 Correct 24 ms 24312 KB Output is correct
17 Correct 26 ms 24568 KB Output is correct
18 Correct 29 ms 24696 KB Output is correct
19 Correct 37 ms 24672 KB Output is correct
20 Correct 31 ms 24532 KB Output is correct
21 Correct 33 ms 24568 KB Output is correct
22 Correct 36 ms 24568 KB Output is correct
23 Correct 37 ms 24568 KB Output is correct
24 Correct 298 ms 44396 KB Output is correct
25 Correct 1489 ms 40648 KB Output is correct
26 Correct 318 ms 49656 KB Output is correct
27 Correct 2317 ms 44576 KB Output is correct
28 Correct 950 ms 45424 KB Output is correct
29 Correct 242 ms 40304 KB Output is correct
30 Correct 2954 ms 47524 KB Output is correct
31 Correct 118 ms 35064 KB Output is correct
32 Correct 164 ms 41708 KB Output is correct
33 Correct 1615 ms 45744 KB Output is correct
34 Correct 2171 ms 45104 KB Output is correct
35 Correct 2956 ms 49296 KB Output is correct
36 Correct 2972 ms 49248 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 24312 KB Output is correct
2 Correct 24 ms 24312 KB Output is correct
3 Correct 28 ms 24312 KB Output is correct
4 Correct 28 ms 24284 KB Output is correct
5 Correct 28 ms 24316 KB Output is correct
6 Correct 25 ms 24312 KB Output is correct
7 Correct 28 ms 24312 KB Output is correct
8 Correct 28 ms 24312 KB Output is correct
9 Correct 28 ms 24312 KB Output is correct
10 Correct 23 ms 24312 KB Output is correct
11 Correct 24 ms 24312 KB Output is correct
12 Correct 23 ms 24312 KB Output is correct
13 Correct 23 ms 24312 KB Output is correct
14 Correct 24 ms 24312 KB Output is correct
15 Correct 24 ms 24312 KB Output is correct
16 Correct 24 ms 24312 KB Output is correct
17 Correct 26 ms 24568 KB Output is correct
18 Correct 29 ms 24696 KB Output is correct
19 Correct 37 ms 24672 KB Output is correct
20 Correct 31 ms 24532 KB Output is correct
21 Correct 33 ms 24568 KB Output is correct
22 Correct 36 ms 24568 KB Output is correct
23 Correct 37 ms 24568 KB Output is correct
24 Correct 298 ms 44396 KB Output is correct
25 Correct 1489 ms 40648 KB Output is correct
26 Correct 318 ms 49656 KB Output is correct
27 Correct 2317 ms 44576 KB Output is correct
28 Correct 950 ms 45424 KB Output is correct
29 Correct 242 ms 40304 KB Output is correct
30 Correct 2954 ms 47524 KB Output is correct
31 Correct 118 ms 35064 KB Output is correct
32 Correct 164 ms 41708 KB Output is correct
33 Correct 1615 ms 45744 KB Output is correct
34 Correct 2171 ms 45104 KB Output is correct
35 Correct 2956 ms 49296 KB Output is correct
36 Correct 2972 ms 49248 KB Output is correct
37 Correct 354 ms 48976 KB Output is correct
38 Correct 2340 ms 43824 KB Output is correct
39 Correct 2684 ms 49128 KB Output is correct
40 Correct 2066 ms 49004 KB Output is correct
41 Correct 24 ms 24312 KB Output is correct
42 Correct 2951 ms 46704 KB Output is correct
43 Correct 1595 ms 45456 KB Output is correct
44 Correct 2177 ms 45012 KB Output is correct
45 Correct 2965 ms 48120 KB Output is correct

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 24312 KB Output is correct
2 Correct 24 ms 24312 KB Output is correct
3 Correct 28 ms 24312 KB Output is correct
4 Correct 28 ms 24284 KB Output is correct
5 Correct 28 ms 24316 KB Output is correct
6 Correct 25 ms 24312 KB Output is correct
7 Correct 28 ms 24312 KB Output is correct
8 Correct 28 ms 24312 KB Output is correct
9 Correct 28 ms 24312 KB Output is correct
10 Correct 23 ms 24312 KB Output is correct
11 Correct 24 ms 24312 KB Output is correct
12 Correct 23 ms 24312 KB Output is correct
13 Correct 23 ms 24312 KB Output is correct
14 Correct 24 ms 24312 KB Output is correct
15 Correct 24 ms 24312 KB Output is correct
16 Correct 24 ms 24312 KB Output is correct
17 Correct 26 ms 24568 KB Output is correct
18 Correct 29 ms 24696 KB Output is correct
19 Correct 37 ms 24672 KB Output is correct
20 Correct 31 ms 24532 KB Output is correct
21 Correct 33 ms 24568 KB Output is correct
22 Correct 36 ms 24568 KB Output is correct
23 Correct 37 ms 24568 KB Output is correct
24 Correct 298 ms 44396 KB Output is correct
25 Correct 1489 ms 40648 KB Output is correct
26 Correct 318 ms 49656 KB Output is correct
27 Correct 2317 ms 44576 KB Output is correct
28 Correct 950 ms 45424 KB Output is correct
29 Correct 242 ms 40304 KB Output is correct
30 Correct 2954 ms 47524 KB Output is correct
31 Correct 118 ms 35064 KB Output is correct
32 Correct 164 ms 41708 KB Output is correct
33 Correct 1615 ms 45744 KB Output is correct
34 Correct 2171 ms 45104 KB Output is correct
35 Correct 2956 ms 49296 KB Output is correct
36 Correct 2972 ms 49248 KB Output is correct
37 Correct 354 ms 48976 KB Output is correct
38 Correct 2340 ms 43824 KB Output is correct
39 Correct 2684 ms 49128 KB Output is correct
40 Correct 2066 ms 49004 KB Output is correct
41 Correct 24 ms 24312 KB Output is correct
42 Correct 2951 ms 46704 KB Output is correct
43 Correct 1595 ms 45456 KB Output is correct
44 Correct 2177 ms 45012 KB Output is correct
45 Correct 2965 ms 48120 KB Output is correct
46 Correct 1680 ms 136228 KB Output is correct
47 Execution timed out 10043 ms 124852 KB Time limit exceeded
48 Halted 0 ms 0 KB -

Subtask #7
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2298 ms 47816 KB Output is correct
2 Correct 1842 ms 46932 KB Output is correct
3 Correct 264 ms 40544 KB Output is correct
4 Correct 1691 ms 46964 KB Output is correct
5 Correct 24 ms 24312 KB Output is correct
6 Correct 1631 ms 44972 KB Output is correct
7 Correct 129 ms 34680 KB Output is correct
8 Correct 143 ms 37120 KB Output is correct
9 Correct 268 ms 40280 KB Output is correct
10 Correct 2165 ms 51960 KB Output is correct
11 Correct 198 ms 42248 KB Output is correct
12 Correct 24 ms 24312 KB Output is correct
13 Correct 24 ms 24312 KB Output is correct
14 Correct 28 ms 24312 KB Output is correct
15 Correct 28 ms 24284 KB Output is correct
16 Correct 28 ms 24316 KB Output is correct
17 Correct 25 ms 24312 KB Output is correct
18 Correct 28 ms 24312 KB Output is correct
19 Correct 28 ms 24312 KB Output is correct
20 Correct 28 ms 24312 KB Output is correct
21 Correct 23 ms 24312 KB Output is correct
22 Correct 24 ms 24312 KB Output is correct
23 Correct 23 ms 24312 KB Output is correct
24 Correct 23 ms 24312 KB Output is correct
25 Correct 24 ms 24312 KB Output is correct
26 Correct 24 ms 24312 KB Output is correct
27 Correct 24 ms 24312 KB Output is correct
28 Correct 26 ms 24568 KB Output is correct
29 Correct 29 ms 24696 KB Output is correct
30 Correct 37 ms 24672 KB Output is correct
31 Correct 31 ms 24532 KB Output is correct
32 Correct 33 ms 24568 KB Output is correct
33 Correct 36 ms 24568 KB Output is correct
34 Correct 37 ms 24568 KB Output is correct
35 Correct 298 ms 44396 KB Output is correct
36 Correct 1489 ms 40648 KB Output is correct
37 Correct 318 ms 49656 KB Output is correct
38 Correct 2317 ms 44576 KB Output is correct
39 Correct 950 ms 45424 KB Output is correct
40 Correct 242 ms 40304 KB Output is correct
41 Correct 2954 ms 47524 KB Output is correct
42 Correct 118 ms 35064 KB Output is correct
43 Correct 164 ms 41708 KB Output is correct
44 Correct 1615 ms 45744 KB Output is correct
45 Correct 2171 ms 45104 KB Output is correct
46 Correct 2956 ms 49296 KB Output is correct
47 Correct 2972 ms 49248 KB Output is correct
48 Correct 354 ms 48976 KB Output is correct
49 Correct 2340 ms 43824 KB Output is correct
50 Correct 2684 ms 49128 KB Output is correct
51 Correct 2066 ms 49004 KB Output is correct
52 Correct 24 ms 24312 KB Output is correct
53 Correct 2951 ms 46704 KB Output is correct
54 Correct 1595 ms 45456 KB Output is correct
55 Correct 2177 ms 45012 KB Output is correct
56 Correct 2965 ms 48120 KB Output is correct
57 Incorrect 350 ms 48912 KB Output isn't correct
58 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2298 ms 47816 KB Output is correct
2 Correct 1842 ms 46932 KB Output is correct
3 Correct 264 ms 40544 KB Output is correct
4 Correct 1691 ms 46964 KB Output is correct
5 Correct 24 ms 24312 KB Output is correct
6 Correct 1631 ms 44972 KB Output is correct
7 Correct 129 ms 34680 KB Output is correct
8 Correct 143 ms 37120 KB Output is correct
9 Correct 268 ms 40280 KB Output is correct
10 Correct 2165 ms 51960 KB Output is correct
11 Correct 198 ms 42248 KB Output is correct
12 Correct 24 ms 24312 KB Output is correct
13 Correct 24 ms 24312 KB Output is correct
14 Correct 28 ms 24312 KB Output is correct
15 Correct 28 ms 24284 KB Output is correct
16 Correct 28 ms 24316 KB Output is correct
17 Correct 25 ms 24312 KB Output is correct
18 Correct 28 ms 24312 KB Output is correct
19 Correct 28 ms 24312 KB Output is correct
20 Correct 28 ms 24312 KB Output is correct
21 Correct 23 ms 24312 KB Output is correct
22 Correct 24 ms 24312 KB Output is correct
23 Correct 23 ms 24312 KB Output is correct
24 Correct 23 ms 24312 KB Output is correct
25 Correct 24 ms 24312 KB Output is correct
26 Correct 24 ms 24312 KB Output is correct
27 Correct 24 ms 24312 KB Output is correct
28 Correct 26 ms 24568 KB Output is correct
29 Correct 29 ms 24696 KB Output is correct
30 Correct 37 ms 24672 KB Output is correct
31 Correct 31 ms 24532 KB Output is correct
32 Correct 33 ms 24568 KB Output is correct
33 Correct 36 ms 24568 KB Output is correct
34 Correct 37 ms 24568 KB Output is correct
35 Correct 298 ms 44396 KB Output is correct
36 Correct 1489 ms 40648 KB Output is correct
37 Correct 318 ms 49656 KB Output is correct
38 Correct 2317 ms 44576 KB Output is correct
39 Correct 950 ms 45424 KB Output is correct
40 Correct 242 ms 40304 KB Output is correct
41 Correct 2954 ms 47524 KB Output is correct
42 Correct 118 ms 35064 KB Output is correct
43 Correct 164 ms 41708 KB Output is correct
44 Correct 1615 ms 45744 KB Output is correct
45 Correct 2171 ms 45104 KB Output is correct
46 Correct 2956 ms 49296 KB Output is correct
47 Correct 2972 ms 49248 KB Output is correct
48 Correct 354 ms 48976 KB Output is correct
49 Correct 2340 ms 43824 KB Output is correct
50 Correct 2684 ms 49128 KB Output is correct
51 Correct 2066 ms 49004 KB Output is correct
52 Correct 24 ms 24312 KB Output is correct
53 Correct 2951 ms 46704 KB Output is correct
54 Correct 1595 ms 45456 KB Output is correct
55 Correct 2177 ms 45012 KB Output is correct
56 Correct 2965 ms 48120 KB Output is correct
57 Correct 1680 ms 136228 KB Output is correct
58 Execution timed out 10043 ms 124852 KB Time limit exceeded
59 Halted 0 ms 0 KB -