oj.uz

Submission #767805

# Submission time Handle Problem Language Result Execution time Memory
767805 2023-06-27T07:45:39 Z qwerasdfzxcl Two Dishes (JOI19_dishes) C++17
74 / 100
 7151 ms 214592 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

struct Block{
	int s, e;
	ll a0;

	Block(){}
	Block(int _s, int _e, ll _a0): s(_s), e(_e), a0(_a0) {}
};

vector<Block> buf;

struct Seg{
	ll treeV[2202000];
	int treeB[2202000];

	ll lazyBadd[2202000], lazyBidx[2202000];

	void init(int i, int l, int r, ll a[]){
		lazyBadd[i] = 0, lazyBidx[i] = -1;
		if (l==r){
			treeV[i] = a[l];
			treeB[i] = 1;
			return;
		}

		int m = (l+r)>>1;
		init(i<<1, l, m, a); init(i<<1|1, m+1, r, a);
		treeV[i] = treeV[i<<1] + treeV[i<<1|1];
	}

	void propagate(int i, int l, int r){
		if (l==r){
			if (lazyBidx[i]!=-1) treeB[i] = lazyBidx[i];
			if (buf[treeB[i]].s==l) buf[treeB[i]].a0 += lazyBadd[i];
		}

		else{
			if (lazyBidx[i]!=-1){
				lazyBidx[i<<1] = lazyBidx[i];
				lazyBadd[i<<1] = 0;
				lazyBidx[i<<1|1] = lazyBidx[i];
				lazyBadd[i<<1|1] = 0;
			}

			lazyBadd[i<<1] += lazyBadd[i];
			lazyBadd[i<<1|1] += lazyBadd[i];
		}

		lazyBidx[i] = -1;
		lazyBadd[i] = 0;
	}

	void update(int i, int l, int r, int p, int v){
		// propagate(i, l, r);
		if (r<p || p<l) return;
		if (l==r){
			treeV[i] = v;
			return;
		}

		int m = (l+r)>>1;
		update(i<<1, l, m, p, v); update(i<<1|1, m+1, r, p, v);
		treeV[i] = treeV[i<<1] + treeV[i<<1|1];
	}

	void updateB(int i, int l, int r, int s, int e, int x){
		propagate(i, l, r);
		if (r<s || e<l) return;
		if (s<=l && r<=e){
			lazyBidx[i] = x;
			propagate(i, l, r);
			return;
		}

		int m = (l+r)>>1;
		updateB(i<<1, l, m, s, e, x); updateB(i<<1|1, m+1, r, s, e, x);
		// treeV[i] = treeV[i<<1] + treeV[i<<1|1];
	}

	void add(int i, int l, int r, int s, int e, int x){
		propagate(i, l, r);
		if (r<s || e<l) return;
		if (s<=l && r<=e){
			lazyBadd[i] += x;
			propagate(i, l, r);
			return;
		}

		int m = (l+r)>>1;
		add(i<<1, l, m, s, e, x); add(i<<1|1, m+1, r, s, e, x);
		// treeV[i] = treeV[i<<1] + treeV[i<<1|1];
	}

	ll queryV(int i, int l, int r, int s, int e){
		// propagate(i, l, r);
		if (r<s || e<l) return 0;
		if (s<=l && r<=e) return treeV[i];

		int m = (l+r)>>1;
		return queryV(i<<1, l, m, s, e) + queryV(i<<1|1, m+1, r, s, e);
	}

	int queryB(int i, int l, int r, int p){
		propagate(i, l, r);
		if (r<p || p<l) return 0;
		if (l==r) return treeB[i];

		int m = (l+r)>>1;
		return queryB(i<<1, l, m, p) | queryB(i<<1|1, m+1, r, p);
	}
}tree;

int n, m;
ll A[1001000], B[1001000], S[1001000], T[1001000], P[1001000], Q[1001000];
ll sumA[1001000], sumB[1001000], W[1001000], mxA[1001000], mxB[1001000];
vector<int> Vp[1001000];

void init(){
	for (int i=1;i<=n;i++) sumA[i] = sumA[i-1] + A[i];
	for (int i=1;i<=m;i++) sumB[i] = sumB[i-1] + B[i];

	for (int i=1;i<=n;i++){
		mxB[i] = upper_bound(sumB, sumB+m+1, S[i] - sumA[i]) - sumB - 1;
		
		if (mxB[i]==-1) W[i] = 0;
		else{
			W[i] = P[i];
			Vp[mxB[i]].push_back(i);
		}
	}
	for (int i=1;i<=m;i++){
		mxA[i] = upper_bound(sumA, sumA+n+1, T[i] - sumB[i]) - sumA - 1;
	}

	// printf("mxB: ");
	// for (int i=1;i<=n;i++) printf("%lld ", mxB[i]);
	// printf("\nmxA: ");
	// for (int i=1;i<=m;i++) printf("%lld ", mxA[i]);
	// printf("\nW: ");
	// for (int i=1;i<=n;i++) printf("%lld ", W[i]);
	// printf("\n");

	buf.emplace_back();
	buf.emplace_back(0, n, 0);
	tree.init(1, 0, n, W);
}


int getidx(int x){
	int ret = tree.queryB(1, 0, n, x);
	tree.queryB(1, 0, n, buf[ret].s);
	return ret;
}

ll calc(int x){
	int idx = getidx(x);
	return buf[idx].a0 + tree.queryV(1, 0, n, buf[idx].s+1, x);
}

void split(int x){
	int idx = getidx(x);
	
	if (buf[idx].s==x) return;

	buf.emplace_back(buf[idx].s, x-1, buf[idx].a0);
	buf[idx].a0 = calc(x);
	buf[idx].s = x;

	tree.updateB(1, 0, n, buf.back().s, x-1, (int)buf.size()-1);
}

void merge(int cur, int nxt){
	buf[cur].e = buf[nxt].e;
	tree.updateB(1, 0, n, buf[nxt].s, buf[nxt].e, cur);
}

void refresh(int x){
	int cur = getidx(x);
	while(true){
		if (buf[cur].e==n) return;
		
		int nxt = getidx(buf[cur].e+1);
		// printf("cur: (%d, %d, %lld) / nxt: (%d, %d, %lld) / w = %lld\n", buf[cur].s, buf[cur].e, buf[cur].a0, buf[nxt].s, buf[nxt].e, buf[nxt].a0, tree.queryV(1, 0, n, buf[cur].e+1, buf[cur].e+1));
		if (calc(buf[cur].e) + tree.queryV(1, 0, n, buf[cur].e+1, buf[cur].e+1) >= buf[nxt].a0) merge(cur, nxt);
		else return;
	}
}

void updateXp(int x, int w){ // between x-1 and x
	// printf("updateXp: %d\n", x);
	split(x);
	tree.update(1, 0, n, x, w);
}

void updateYp(int x, int q){
	// printf("updateYp: %d %d\n", x, q);
	tree.add(1, 0, n, 0, x, q);
	refresh(x);
}


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

	cin >> n >> m;
	for (int i=1;i<=n;i++) cin >> A[i] >> S[i] >> P[i];
	for (int i=1;i<=m;i++) cin >> B[i] >> T[i] >> Q[i];

	init();

	for (int y=1;y<=m;y++){
		for (auto &x:Vp[y-1]) updateXp(x, 0);
		
		if (Q[y] > 0 && mxA[y] >= 0) updateYp(mxA[y], Q[y]);
		// else if (Q[y] < 0) updateYm(Q[y]);

		// for (auto &x:Vm[y]) updateXm(x);
		// for (int x=0;x<=n;x++) printf("%lld ", calc(x));
		// printf("\n");
	}

	printf("%lld\n", calc(n));
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 585 ms 63288 KB Output is correct
2 Correct 553 ms 71412 KB Output is correct
3 Correct 189 ms 64688 KB Output is correct
4 Correct 441 ms 69348 KB Output is correct
5 Correct 12 ms 23892 KB Output is correct
6 Correct 602 ms 70576 KB Output is correct
7 Correct 72 ms 38436 KB Output is correct
8 Correct 74 ms 55020 KB Output is correct
9 Correct 200 ms 64572 KB Output is correct
10 Correct 786 ms 72820 KB Output is correct
11 Correct 163 ms 63648 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23944 KB Output is correct
2 Correct 12 ms 23852 KB Output is correct
3 Correct 13 ms 23852 KB Output is correct
4 Correct 12 ms 23876 KB Output is correct
5 Correct 12 ms 23892 KB Output is correct
6 Correct 12 ms 23868 KB Output is correct
7 Correct 11 ms 23832 KB Output is correct
8 Correct 12 ms 23924 KB Output is correct
9 Correct 12 ms 23892 KB Output is correct
10 Correct 12 ms 23892 KB Output is correct
11 Correct 15 ms 23880 KB Output is correct
12 Correct 12 ms 23836 KB Output is correct
13 Correct 12 ms 23892 KB Output is correct
14 Correct 12 ms 23948 KB Output is correct
15 Correct 12 ms 23892 KB Output is correct
16 Correct 12 ms 23836 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23944 KB Output is correct
2 Correct 12 ms 23852 KB Output is correct
3 Correct 13 ms 23852 KB Output is correct
4 Correct 12 ms 23876 KB Output is correct
5 Correct 12 ms 23892 KB Output is correct
6 Correct 12 ms 23868 KB Output is correct
7 Correct 11 ms 23832 KB Output is correct
8 Correct 12 ms 23924 KB Output is correct
9 Correct 12 ms 23892 KB Output is correct
10 Correct 12 ms 23892 KB Output is correct
11 Correct 15 ms 23880 KB Output is correct
12 Correct 12 ms 23836 KB Output is correct
13 Correct 12 ms 23892 KB Output is correct
14 Correct 12 ms 23948 KB Output is correct
15 Correct 12 ms 23892 KB Output is correct
16 Correct 12 ms 23836 KB Output is correct
17 Correct 14 ms 24404 KB Output is correct
18 Correct 13 ms 24264 KB Output is correct
19 Correct 17 ms 24432 KB Output is correct
20 Correct 16 ms 24312 KB Output is correct
21 Correct 16 ms 24360 KB Output is correct
22 Correct 17 ms 24276 KB Output is correct
23 Correct 18 ms 24360 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23944 KB Output is correct
2 Correct 12 ms 23852 KB Output is correct
3 Correct 13 ms 23852 KB Output is correct
4 Correct 12 ms 23876 KB Output is correct
5 Correct 12 ms 23892 KB Output is correct
6 Correct 12 ms 23868 KB Output is correct
7 Correct 11 ms 23832 KB Output is correct
8 Correct 12 ms 23924 KB Output is correct
9 Correct 12 ms 23892 KB Output is correct
10 Correct 12 ms 23892 KB Output is correct
11 Correct 15 ms 23880 KB Output is correct
12 Correct 12 ms 23836 KB Output is correct
13 Correct 12 ms 23892 KB Output is correct
14 Correct 12 ms 23948 KB Output is correct
15 Correct 12 ms 23892 KB Output is correct
16 Correct 12 ms 23836 KB Output is correct
17 Correct 14 ms 24404 KB Output is correct
18 Correct 13 ms 24264 KB Output is correct
19 Correct 17 ms 24432 KB Output is correct
20 Correct 16 ms 24312 KB Output is correct
21 Correct 16 ms 24360 KB Output is correct
22 Correct 17 ms 24276 KB Output is correct
23 Correct 18 ms 24360 KB Output is correct
24 Correct 311 ms 69068 KB Output is correct
25 Correct 191 ms 64540 KB Output is correct
26 Correct 343 ms 74540 KB Output is correct
27 Correct 229 ms 64588 KB Output is correct
28 Correct 394 ms 67088 KB Output is correct
29 Correct 183 ms 64928 KB Output is correct
30 Correct 1074 ms 72140 KB Output is correct
31 Correct 76 ms 36984 KB Output is correct
32 Correct 156 ms 55312 KB Output is correct
33 Correct 649 ms 68456 KB Output is correct
34 Correct 678 ms 70680 KB Output is correct
35 Correct 1051 ms 67424 KB Output is correct
36 Correct 1020 ms 67448 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23944 KB Output is correct
2 Correct 12 ms 23852 KB Output is correct
3 Correct 13 ms 23852 KB Output is correct
4 Correct 12 ms 23876 KB Output is correct
5 Correct 12 ms 23892 KB Output is correct
6 Correct 12 ms 23868 KB Output is correct
7 Correct 11 ms 23832 KB Output is correct
8 Correct 12 ms 23924 KB Output is correct
9 Correct 12 ms 23892 KB Output is correct
10 Correct 12 ms 23892 KB Output is correct
11 Correct 15 ms 23880 KB Output is correct
12 Correct 12 ms 23836 KB Output is correct
13 Correct 12 ms 23892 KB Output is correct
14 Correct 12 ms 23948 KB Output is correct
15 Correct 12 ms 23892 KB Output is correct
16 Correct 12 ms 23836 KB Output is correct
17 Correct 14 ms 24404 KB Output is correct
18 Correct 13 ms 24264 KB Output is correct
19 Correct 17 ms 24432 KB Output is correct
20 Correct 16 ms 24312 KB Output is correct
21 Correct 16 ms 24360 KB Output is correct
22 Correct 17 ms 24276 KB Output is correct
23 Correct 18 ms 24360 KB Output is correct
24 Correct 311 ms 69068 KB Output is correct
25 Correct 191 ms 64540 KB Output is correct
26 Correct 343 ms 74540 KB Output is correct
27 Correct 229 ms 64588 KB Output is correct
28 Correct 394 ms 67088 KB Output is correct
29 Correct 183 ms 64928 KB Output is correct
30 Correct 1074 ms 72140 KB Output is correct
31 Correct 76 ms 36984 KB Output is correct
32 Correct 156 ms 55312 KB Output is correct
33 Correct 649 ms 68456 KB Output is correct
34 Correct 678 ms 70680 KB Output is correct
35 Correct 1051 ms 67424 KB Output is correct
36 Correct 1020 ms 67448 KB Output is correct
37 Correct 376 ms 74276 KB Output is correct
38 Correct 223 ms 64348 KB Output is correct
39 Correct 790 ms 74520 KB Output is correct
40 Correct 796 ms 74724 KB Output is correct
41 Correct 12 ms 23892 KB Output is correct
42 Correct 1142 ms 72068 KB Output is correct
43 Correct 600 ms 68032 KB Output is correct
44 Correct 721 ms 70156 KB Output is correct
45 Correct 1114 ms 70424 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23944 KB Output is correct
2 Correct 12 ms 23852 KB Output is correct
3 Correct 13 ms 23852 KB Output is correct
4 Correct 12 ms 23876 KB Output is correct
5 Correct 12 ms 23892 KB Output is correct
6 Correct 12 ms 23868 KB Output is correct
7 Correct 11 ms 23832 KB Output is correct
8 Correct 12 ms 23924 KB Output is correct
9 Correct 12 ms 23892 KB Output is correct
10 Correct 12 ms 23892 KB Output is correct
11 Correct 15 ms 23880 KB Output is correct
12 Correct 12 ms 23836 KB Output is correct
13 Correct 12 ms 23892 KB Output is correct
14 Correct 12 ms 23948 KB Output is correct
15 Correct 12 ms 23892 KB Output is correct
16 Correct 12 ms 23836 KB Output is correct
17 Correct 14 ms 24404 KB Output is correct
18 Correct 13 ms 24264 KB Output is correct
19 Correct 17 ms 24432 KB Output is correct
20 Correct 16 ms 24312 KB Output is correct
21 Correct 16 ms 24360 KB Output is correct
22 Correct 17 ms 24276 KB Output is correct
23 Correct 18 ms 24360 KB Output is correct
24 Correct 311 ms 69068 KB Output is correct
25 Correct 191 ms 64540 KB Output is correct
26 Correct 343 ms 74540 KB Output is correct
27 Correct 229 ms 64588 KB Output is correct
28 Correct 394 ms 67088 KB Output is correct
29 Correct 183 ms 64928 KB Output is correct
30 Correct 1074 ms 72140 KB Output is correct
31 Correct 76 ms 36984 KB Output is correct
32 Correct 156 ms 55312 KB Output is correct
33 Correct 649 ms 68456 KB Output is correct
34 Correct 678 ms 70680 KB Output is correct
35 Correct 1051 ms 67424 KB Output is correct
36 Correct 1020 ms 67448 KB Output is correct
37 Correct 376 ms 74276 KB Output is correct
38 Correct 223 ms 64348 KB Output is correct
39 Correct 790 ms 74520 KB Output is correct
40 Correct 796 ms 74724 KB Output is correct
41 Correct 12 ms 23892 KB Output is correct
42 Correct 1142 ms 72068 KB Output is correct
43 Correct 600 ms 68032 KB Output is correct
44 Correct 721 ms 70156 KB Output is correct
45 Correct 1114 ms 70424 KB Output is correct
46 Correct 2007 ms 214592 KB Output is correct
47 Correct 1162 ms 169172 KB Output is correct
48 Correct 4309 ms 214532 KB Output is correct
49 Correct 4152 ms 214428 KB Output is correct
50 Correct 7151 ms 202788 KB Output is correct
51 Correct 3740 ms 183444 KB Output is correct
52 Correct 3799 ms 189692 KB Output is correct
53 Correct 6685 ms 201672 KB Output is correct

Subtask #7
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 585 ms 63288 KB Output is correct
2 Correct 553 ms 71412 KB Output is correct
3 Correct 189 ms 64688 KB Output is correct
4 Correct 441 ms 69348 KB Output is correct
5 Correct 12 ms 23892 KB Output is correct
6 Correct 602 ms 70576 KB Output is correct
7 Correct 72 ms 38436 KB Output is correct
8 Correct 74 ms 55020 KB Output is correct
9 Correct 200 ms 64572 KB Output is correct
10 Correct 786 ms 72820 KB Output is correct
11 Correct 163 ms 63648 KB Output is correct
12 Correct 12 ms 23944 KB Output is correct
13 Correct 12 ms 23852 KB Output is correct
14 Correct 13 ms 23852 KB Output is correct
15 Correct 12 ms 23876 KB Output is correct
16 Correct 12 ms 23892 KB Output is correct
17 Correct 12 ms 23868 KB Output is correct
18 Correct 11 ms 23832 KB Output is correct
19 Correct 12 ms 23924 KB Output is correct
20 Correct 12 ms 23892 KB Output is correct
21 Correct 12 ms 23892 KB Output is correct
22 Correct 15 ms 23880 KB Output is correct
23 Correct 12 ms 23836 KB Output is correct
24 Correct 12 ms 23892 KB Output is correct
25 Correct 12 ms 23948 KB Output is correct
26 Correct 12 ms 23892 KB Output is correct
27 Correct 12 ms 23836 KB Output is correct
28 Correct 14 ms 24404 KB Output is correct
29 Correct 13 ms 24264 KB Output is correct
30 Correct 17 ms 24432 KB Output is correct
31 Correct 16 ms 24312 KB Output is correct
32 Correct 16 ms 24360 KB Output is correct
33 Correct 17 ms 24276 KB Output is correct
34 Correct 18 ms 24360 KB Output is correct
35 Correct 311 ms 69068 KB Output is correct
36 Correct 191 ms 64540 KB Output is correct
37 Correct 343 ms 74540 KB Output is correct
38 Correct 229 ms 64588 KB Output is correct
39 Correct 394 ms 67088 KB Output is correct
40 Correct 183 ms 64928 KB Output is correct
41 Correct 1074 ms 72140 KB Output is correct
42 Correct 76 ms 36984 KB Output is correct
43 Correct 156 ms 55312 KB Output is correct
44 Correct 649 ms 68456 KB Output is correct
45 Correct 678 ms 70680 KB Output is correct
46 Correct 1051 ms 67424 KB Output is correct
47 Correct 1020 ms 67448 KB Output is correct
48 Correct 376 ms 74276 KB Output is correct
49 Correct 223 ms 64348 KB Output is correct
50 Correct 790 ms 74520 KB Output is correct
51 Correct 796 ms 74724 KB Output is correct
52 Correct 12 ms 23892 KB Output is correct
53 Correct 1142 ms 72068 KB Output is correct
54 Correct 600 ms 68032 KB Output is correct
55 Correct 721 ms 70156 KB Output is correct
56 Correct 1114 ms 70424 KB Output is correct
57 Incorrect 326 ms 66420 KB Output isn't correct
58 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 585 ms 63288 KB Output is correct
2 Correct 553 ms 71412 KB Output is correct
3 Correct 189 ms 64688 KB Output is correct
4 Correct 441 ms 69348 KB Output is correct
5 Correct 12 ms 23892 KB Output is correct
6 Correct 602 ms 70576 KB Output is correct
7 Correct 72 ms 38436 KB Output is correct
8 Correct 74 ms 55020 KB Output is correct
9 Correct 200 ms 64572 KB Output is correct
10 Correct 786 ms 72820 KB Output is correct
11 Correct 163 ms 63648 KB Output is correct
12 Correct 12 ms 23944 KB Output is correct
13 Correct 12 ms 23852 KB Output is correct
14 Correct 13 ms 23852 KB Output is correct
15 Correct 12 ms 23876 KB Output is correct
16 Correct 12 ms 23892 KB Output is correct
17 Correct 12 ms 23868 KB Output is correct
18 Correct 11 ms 23832 KB Output is correct
19 Correct 12 ms 23924 KB Output is correct
20 Correct 12 ms 23892 KB Output is correct
21 Correct 12 ms 23892 KB Output is correct
22 Correct 15 ms 23880 KB Output is correct
23 Correct 12 ms 23836 KB Output is correct
24 Correct 12 ms 23892 KB Output is correct
25 Correct 12 ms 23948 KB Output is correct
26 Correct 12 ms 23892 KB Output is correct
27 Correct 12 ms 23836 KB Output is correct
28 Correct 14 ms 24404 KB Output is correct
29 Correct 13 ms 24264 KB Output is correct
30 Correct 17 ms 24432 KB Output is correct
31 Correct 16 ms 24312 KB Output is correct
32 Correct 16 ms 24360 KB Output is correct
33 Correct 17 ms 24276 KB Output is correct
34 Correct 18 ms 24360 KB Output is correct
35 Correct 311 ms 69068 KB Output is correct
36 Correct 191 ms 64540 KB Output is correct
37 Correct 343 ms 74540 KB Output is correct
38 Correct 229 ms 64588 KB Output is correct
39 Correct 394 ms 67088 KB Output is correct
40 Correct 183 ms 64928 KB Output is correct
41 Correct 1074 ms 72140 KB Output is correct
42 Correct 76 ms 36984 KB Output is correct
43 Correct 156 ms 55312 KB Output is correct
44 Correct 649 ms 68456 KB Output is correct
45 Correct 678 ms 70680 KB Output is correct
46 Correct 1051 ms 67424 KB Output is correct
47 Correct 1020 ms 67448 KB Output is correct
48 Correct 376 ms 74276 KB Output is correct
49 Correct 223 ms 64348 KB Output is correct
50 Correct 790 ms 74520 KB Output is correct
51 Correct 796 ms 74724 KB Output is correct
52 Correct 12 ms 23892 KB Output is correct
53 Correct 1142 ms 72068 KB Output is correct
54 Correct 600 ms 68032 KB Output is correct
55 Correct 721 ms 70156 KB Output is correct
56 Correct 1114 ms 70424 KB Output is correct
57 Correct 2007 ms 214592 KB Output is correct
58 Correct 1162 ms 169172 KB Output is correct
59 Correct 4309 ms 214532 KB Output is correct
60 Correct 4152 ms 214428 KB Output is correct
61 Correct 7151 ms 202788 KB Output is correct
62 Correct 3740 ms 183444 KB Output is correct
63 Correct 3799 ms 189692 KB Output is correct
64 Correct 6685 ms 201672 KB Output is correct
65 Incorrect 326 ms 66420 KB Output isn't correct
66 Halted 0 ms 0 KB -