oj.uz

Submission #522640

# Submission time Handle Problem Language Result Execution time Memory
522640 2022-02-05T09:58:55 Z blue Two Dishes (JOI19_dishes) C++17
82 / 100
 10000 ms 255588 KB 
#include <iostream>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
using namespace std;

#define sz(x) int(x.size())
using vi = vector<int>;
using vvi = vector<vi>;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;

const int mx = 1'000'000;
const ll INF = 1'000'000'000'000'000'000LL;

int N, M;
vll A(1+mx), S(1+mx), P(1+mx);
vll B(1+mx), T(1+mx), Q(1+mx);

vll Asum(1+mx, 0);
vll Bsum(1+mx, 0);


bool dbg = 1;




struct delta
{
	int p;
	ll v;
};

bool operator < (delta A, delta B)
{
	if(A.p == B.p) return A.v < B.v;
	return A.p < B.p;
}




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

	int N, M;
	cin >> N >> M;

	for(int i = 1; i <= N; i++)
	{
		cin >> A[i] >> S[i] >> P[i];
		Asum[i] = Asum[i-1] + A[i];
	}

	for(int j = 1; j <= M; j++)
	{
		cin >> B[j] >> T[j] >> Q[j];
		Bsum[j] = Bsum[j-1] + B[j];
	}

















	multiset<delta> hi_points[1+M], lo_points[1+M];

	ll basicCost = 0;




	for(int i = 1; i <= N; i++)
	{
		if(Asum[i] > S[i]) continue;

		int lo = 0, hi = M;
		while(lo != hi)
		{
			int mid = (lo+hi)/2 + 1;

			if(Bsum[mid] + Asum[i] <= S[i])
				lo = mid;
			else
				hi = mid-1;
		}

		if(lo == M)
		{
			basicCost += P[i];

			if(dbg) cerr << i << " : " << "basicCost += " << P[i] << '\n';
		}
		else
		{
			delta cr{i, +P[i]};
			if(dbg) cerr << lo+1 << " : " << i << ' ' << P[i] << '\n';
			// cerr << lo+1 << ' ' << i << ' ' << +P[i] << '\n';

			if(cr.v >= 0) hi_points[lo+1].insert(cr);
			else 
			{
				cr.v *= -1;
				lo_points[lo+1].insert(cr);
			}
		}
	}

	if(dbg)cerr << "-----\n";









	for(int j = 1; j <= M; j++)
	{
		if(Bsum[j] > T[j]) continue;

		int lo = 0, hi = N;
		while(lo != hi)
		{
			int mid = (lo+hi)/2+1;

			if(Asum[mid] + Bsum[j] <= T[j])
				lo = mid;
			else
				hi = mid-1;
		}

		// cerr << j << " : " << lo << '\n';

		if(lo == N)
		{
			basicCost += Q[j];
			if(dbg) cerr << j << " : " << "basicCost += " << Q[j] << '\n';
		}
		else
		{
			basicCost += Q[j];
			delta cr{lo+1, -Q[j]};

			if(dbg) cerr << j << ' ' << lo+1 << ' ' << -T[j] << '\n';

			if(cr.v >= 0) hi_points[j].insert(cr);
			else 
			{
				cr.v *= -1;
				lo_points[j].insert(cr);
			}
		}
	}




	vi init_size(1+M, 0);
	for(int j = 1; j <= M; j++) init_size[j] = sz(hi_points[j]) + sz(lo_points[j]);







	multiset<delta>* hp[1+M];
	multiset<delta>* lp[1+M];
	for(int j = 1; j <= M; j++)
	{
		hp[j] = &hi_points[j];
		lp[j] = &lo_points[j];
	}

	for(int j = 1; j <= M; j++)
	{
		while(!lp[j]->empty())
		{
			auto lit = lp[j]->begin();

			delta lpv = *lit;


			auto hit = hp[j]->lower_bound({lpv.p, -INF});

			if(hit == hp[j]->end())
			{
				lp[j]->clear();
				break;
			}

			delta hpv = *hit;


			ll cng = min(lpv.v, hpv.v);


			lp[j]->erase(lit);
			if(lpv.v != cng)
				lp[j]->insert({lpv.p, lpv.v - cng});

			hp[j]->erase(hit);
			if(hpv.v != cng)
				hp[j]->insert({hpv.p, hpv.v - cng});
		}

		if(j < M)
		{
			if(init_size[j] > init_size[j+1])
			{
				swap(lp[j], lp[j+1]);
				swap(hp[j], hp[j+1]);
				swap(init_size[j], init_size[j+1]);
			}

			init_size[j+1] += init_size[j];

			for(delta x : *lp[j])
				lp[j+1]->insert(x);

			for(delta y : *hp[j])
				hp[j+1]->insert(y);

			lp[j]->clear();
			hp[j]->clear();
		}
	}

	// cerr << "basicCost = "<< basicCost << '\n';





	ll ans = basicCost;

	for(delta z : *hp[M])
		ans += z.v;

	cout << ans << '\n';
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2751 ms 117744 KB Output is correct
2 Correct 3227 ms 118984 KB Output is correct
3 Correct 2521 ms 98180 KB Output is correct
4 Correct 1938 ms 107388 KB Output is correct
5 Correct 27 ms 62988 KB Output is correct
6 Correct 2828 ms 126560 KB Output is correct
7 Correct 1177 ms 98064 KB Output is correct
8 Correct 1272 ms 76316 KB Output is correct
9 Correct 2770 ms 112540 KB Output is correct
10 Correct 3329 ms 127236 KB Output is correct
11 Correct 2805 ms 98268 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 62880 KB Output is correct
2 Correct 28 ms 62916 KB Output is correct
3 Correct 29 ms 62912 KB Output is correct
4 Correct 26 ms 62928 KB Output is correct
5 Correct 29 ms 62904 KB Output is correct
6 Correct 29 ms 62924 KB Output is correct
7 Correct 24 ms 62900 KB Output is correct
8 Correct 23 ms 62976 KB Output is correct
9 Correct 24 ms 62984 KB Output is correct
10 Correct 25 ms 62924 KB Output is correct
11 Correct 26 ms 62948 KB Output is correct
12 Correct 27 ms 62880 KB Output is correct
13 Correct 24 ms 62900 KB Output is correct
14 Correct 28 ms 62924 KB Output is correct
15 Correct 33 ms 62896 KB Output is correct
16 Correct 27 ms 62852 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 62880 KB Output is correct
2 Correct 28 ms 62916 KB Output is correct
3 Correct 29 ms 62912 KB Output is correct
4 Correct 26 ms 62928 KB Output is correct
5 Correct 29 ms 62904 KB Output is correct
6 Correct 29 ms 62924 KB Output is correct
7 Correct 24 ms 62900 KB Output is correct
8 Correct 23 ms 62976 KB Output is correct
9 Correct 24 ms 62984 KB Output is correct
10 Correct 25 ms 62924 KB Output is correct
11 Correct 26 ms 62948 KB Output is correct
12 Correct 27 ms 62880 KB Output is correct
13 Correct 24 ms 62900 KB Output is correct
14 Correct 28 ms 62924 KB Output is correct
15 Correct 33 ms 62896 KB Output is correct
16 Correct 27 ms 62852 KB Output is correct
17 Correct 54 ms 63256 KB Output is correct
18 Correct 52 ms 63304 KB Output is correct
19 Correct 53 ms 63412 KB Output is correct
20 Correct 40 ms 63300 KB Output is correct
21 Correct 64 ms 63376 KB Output is correct
22 Correct 56 ms 63412 KB Output is correct
23 Correct 61 ms 63464 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 62880 KB Output is correct
2 Correct 28 ms 62916 KB Output is correct
3 Correct 29 ms 62912 KB Output is correct
4 Correct 26 ms 62928 KB Output is correct
5 Correct 29 ms 62904 KB Output is correct
6 Correct 29 ms 62924 KB Output is correct
7 Correct 24 ms 62900 KB Output is correct
8 Correct 23 ms 62976 KB Output is correct
9 Correct 24 ms 62984 KB Output is correct
10 Correct 25 ms 62924 KB Output is correct
11 Correct 26 ms 62948 KB Output is correct
12 Correct 27 ms 62880 KB Output is correct
13 Correct 24 ms 62900 KB Output is correct
14 Correct 28 ms 62924 KB Output is correct
15 Correct 33 ms 62896 KB Output is correct
16 Correct 27 ms 62852 KB Output is correct
17 Correct 54 ms 63256 KB Output is correct
18 Correct 52 ms 63304 KB Output is correct
19 Correct 53 ms 63412 KB Output is correct
20 Correct 40 ms 63300 KB Output is correct
21 Correct 64 ms 63376 KB Output is correct
22 Correct 56 ms 63412 KB Output is correct
23 Correct 61 ms 63464 KB Output is correct
24 Correct 2299 ms 102920 KB Output is correct
25 Correct 2298 ms 105460 KB Output is correct
26 Correct 2399 ms 103832 KB Output is correct
27 Correct 2448 ms 106384 KB Output is correct
28 Correct 2591 ms 100100 KB Output is correct
29 Correct 2608 ms 95120 KB Output is correct
30 Correct 3303 ms 118784 KB Output is correct
31 Correct 1492 ms 96632 KB Output is correct
32 Correct 1546 ms 72772 KB Output is correct
33 Correct 1754 ms 102340 KB Output is correct
34 Correct 3238 ms 113452 KB Output is correct
35 Correct 3274 ms 117732 KB Output is correct
36 Correct 3137 ms 116612 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 62880 KB Output is correct
2 Correct 28 ms 62916 KB Output is correct
3 Correct 29 ms 62912 KB Output is correct
4 Correct 26 ms 62928 KB Output is correct
5 Correct 29 ms 62904 KB Output is correct
6 Correct 29 ms 62924 KB Output is correct
7 Correct 24 ms 62900 KB Output is correct
8 Correct 23 ms 62976 KB Output is correct
9 Correct 24 ms 62984 KB Output is correct
10 Correct 25 ms 62924 KB Output is correct
11 Correct 26 ms 62948 KB Output is correct
12 Correct 27 ms 62880 KB Output is correct
13 Correct 24 ms 62900 KB Output is correct
14 Correct 28 ms 62924 KB Output is correct
15 Correct 33 ms 62896 KB Output is correct
16 Correct 27 ms 62852 KB Output is correct
17 Correct 54 ms 63256 KB Output is correct
18 Correct 52 ms 63304 KB Output is correct
19 Correct 53 ms 63412 KB Output is correct
20 Correct 40 ms 63300 KB Output is correct
21 Correct 64 ms 63376 KB Output is correct
22 Correct 56 ms 63412 KB Output is correct
23 Correct 61 ms 63464 KB Output is correct
24 Correct 2299 ms 102920 KB Output is correct
25 Correct 2298 ms 105460 KB Output is correct
26 Correct 2399 ms 103832 KB Output is correct
27 Correct 2448 ms 106384 KB Output is correct
28 Correct 2591 ms 100100 KB Output is correct
29 Correct 2608 ms 95120 KB Output is correct
30 Correct 3303 ms 118784 KB Output is correct
31 Correct 1492 ms 96632 KB Output is correct
32 Correct 1546 ms 72772 KB Output is correct
33 Correct 1754 ms 102340 KB Output is correct
34 Correct 3238 ms 113452 KB Output is correct
35 Correct 3274 ms 117732 KB Output is correct
36 Correct 3137 ms 116612 KB Output is correct
37 Correct 2653 ms 106192 KB Output is correct
38 Correct 2583 ms 107044 KB Output is correct
39 Correct 3538 ms 119836 KB Output is correct
40 Correct 3419 ms 120436 KB Output is correct
41 Correct 26 ms 62948 KB Output is correct
42 Correct 3892 ms 120452 KB Output is correct
43 Correct 1855 ms 103148 KB Output is correct
44 Correct 3196 ms 114872 KB Output is correct
45 Correct 3324 ms 119304 KB Output is correct

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 62880 KB Output is correct
2 Correct 28 ms 62916 KB Output is correct
3 Correct 29 ms 62912 KB Output is correct
4 Correct 26 ms 62928 KB Output is correct
5 Correct 29 ms 62904 KB Output is correct
6 Correct 29 ms 62924 KB Output is correct
7 Correct 24 ms 62900 KB Output is correct
8 Correct 23 ms 62976 KB Output is correct
9 Correct 24 ms 62984 KB Output is correct
10 Correct 25 ms 62924 KB Output is correct
11 Correct 26 ms 62948 KB Output is correct
12 Correct 27 ms 62880 KB Output is correct
13 Correct 24 ms 62900 KB Output is correct
14 Correct 28 ms 62924 KB Output is correct
15 Correct 33 ms 62896 KB Output is correct
16 Correct 27 ms 62852 KB Output is correct
17 Correct 54 ms 63256 KB Output is correct
18 Correct 52 ms 63304 KB Output is correct
19 Correct 53 ms 63412 KB Output is correct
20 Correct 40 ms 63300 KB Output is correct
21 Correct 64 ms 63376 KB Output is correct
22 Correct 56 ms 63412 KB Output is correct
23 Correct 61 ms 63464 KB Output is correct
24 Correct 2299 ms 102920 KB Output is correct
25 Correct 2298 ms 105460 KB Output is correct
26 Correct 2399 ms 103832 KB Output is correct
27 Correct 2448 ms 106384 KB Output is correct
28 Correct 2591 ms 100100 KB Output is correct
29 Correct 2608 ms 95120 KB Output is correct
30 Correct 3303 ms 118784 KB Output is correct
31 Correct 1492 ms 96632 KB Output is correct
32 Correct 1546 ms 72772 KB Output is correct
33 Correct 1754 ms 102340 KB Output is correct
34 Correct 3238 ms 113452 KB Output is correct
35 Correct 3274 ms 117732 KB Output is correct
36 Correct 3137 ms 116612 KB Output is correct
37 Correct 2653 ms 106192 KB Output is correct
38 Correct 2583 ms 107044 KB Output is correct
39 Correct 3538 ms 119836 KB Output is correct
40 Correct 3419 ms 120436 KB Output is correct
41 Correct 26 ms 62948 KB Output is correct
42 Correct 3892 ms 120452 KB Output is correct
43 Correct 1855 ms 103148 KB Output is correct
44 Correct 3196 ms 114872 KB Output is correct
45 Correct 3324 ms 119304 KB Output is correct
46 Execution timed out 10064 ms 255588 KB Time limit exceeded
47 Halted 0 ms 0 KB -

Subtask #7
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2751 ms 117744 KB Output is correct
2 Correct 3227 ms 118984 KB Output is correct
3 Correct 2521 ms 98180 KB Output is correct
4 Correct 1938 ms 107388 KB Output is correct
5 Correct 27 ms 62988 KB Output is correct
6 Correct 2828 ms 126560 KB Output is correct
7 Correct 1177 ms 98064 KB Output is correct
8 Correct 1272 ms 76316 KB Output is correct
9 Correct 2770 ms 112540 KB Output is correct
10 Correct 3329 ms 127236 KB Output is correct
11 Correct 2805 ms 98268 KB Output is correct
12 Correct 29 ms 62880 KB Output is correct
13 Correct 28 ms 62916 KB Output is correct
14 Correct 29 ms 62912 KB Output is correct
15 Correct 26 ms 62928 KB Output is correct
16 Correct 29 ms 62904 KB Output is correct
17 Correct 29 ms 62924 KB Output is correct
18 Correct 24 ms 62900 KB Output is correct
19 Correct 23 ms 62976 KB Output is correct
20 Correct 24 ms 62984 KB Output is correct
21 Correct 25 ms 62924 KB Output is correct
22 Correct 26 ms 62948 KB Output is correct
23 Correct 27 ms 62880 KB Output is correct
24 Correct 24 ms 62900 KB Output is correct
25 Correct 28 ms 62924 KB Output is correct
26 Correct 33 ms 62896 KB Output is correct
27 Correct 27 ms 62852 KB Output is correct
28 Correct 54 ms 63256 KB Output is correct
29 Correct 52 ms 63304 KB Output is correct
30 Correct 53 ms 63412 KB Output is correct
31 Correct 40 ms 63300 KB Output is correct
32 Correct 64 ms 63376 KB Output is correct
33 Correct 56 ms 63412 KB Output is correct
34 Correct 61 ms 63464 KB Output is correct
35 Correct 2299 ms 102920 KB Output is correct
36 Correct 2298 ms 105460 KB Output is correct
37 Correct 2399 ms 103832 KB Output is correct
38 Correct 2448 ms 106384 KB Output is correct
39 Correct 2591 ms 100100 KB Output is correct
40 Correct 2608 ms 95120 KB Output is correct
41 Correct 3303 ms 118784 KB Output is correct
42 Correct 1492 ms 96632 KB Output is correct
43 Correct 1546 ms 72772 KB Output is correct
44 Correct 1754 ms 102340 KB Output is correct
45 Correct 3238 ms 113452 KB Output is correct
46 Correct 3274 ms 117732 KB Output is correct
47 Correct 3137 ms 116612 KB Output is correct
48 Correct 2653 ms 106192 KB Output is correct
49 Correct 2583 ms 107044 KB Output is correct
50 Correct 3538 ms 119836 KB Output is correct
51 Correct 3419 ms 120436 KB Output is correct
52 Correct 26 ms 62948 KB Output is correct
53 Correct 3892 ms 120452 KB Output is correct
54 Correct 1855 ms 103148 KB Output is correct
55 Correct 3196 ms 114872 KB Output is correct
56 Correct 3324 ms 119304 KB Output is correct
57 Correct 2238 ms 107620 KB Output is correct
58 Correct 2269 ms 108240 KB Output is correct
59 Correct 3204 ms 121540 KB Output is correct
60 Correct 3080 ms 121860 KB Output is correct
61 Correct 3860 ms 121308 KB Output is correct
62 Correct 28 ms 62916 KB Output is correct
63 Correct 3484 ms 123264 KB Output is correct
64 Correct 1760 ms 104904 KB Output is correct
65 Correct 3127 ms 118768 KB Output is correct
66 Correct 3071 ms 121880 KB Output is correct

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2751 ms 117744 KB Output is correct
2 Correct 3227 ms 118984 KB Output is correct
3 Correct 2521 ms 98180 KB Output is correct
4 Correct 1938 ms 107388 KB Output is correct
5 Correct 27 ms 62988 KB Output is correct
6 Correct 2828 ms 126560 KB Output is correct
7 Correct 1177 ms 98064 KB Output is correct
8 Correct 1272 ms 76316 KB Output is correct
9 Correct 2770 ms 112540 KB Output is correct
10 Correct 3329 ms 127236 KB Output is correct
11 Correct 2805 ms 98268 KB Output is correct
12 Correct 29 ms 62880 KB Output is correct
13 Correct 28 ms 62916 KB Output is correct
14 Correct 29 ms 62912 KB Output is correct
15 Correct 26 ms 62928 KB Output is correct
16 Correct 29 ms 62904 KB Output is correct
17 Correct 29 ms 62924 KB Output is correct
18 Correct 24 ms 62900 KB Output is correct
19 Correct 23 ms 62976 KB Output is correct
20 Correct 24 ms 62984 KB Output is correct
21 Correct 25 ms 62924 KB Output is correct
22 Correct 26 ms 62948 KB Output is correct
23 Correct 27 ms 62880 KB Output is correct
24 Correct 24 ms 62900 KB Output is correct
25 Correct 28 ms 62924 KB Output is correct
26 Correct 33 ms 62896 KB Output is correct
27 Correct 27 ms 62852 KB Output is correct
28 Correct 54 ms 63256 KB Output is correct
29 Correct 52 ms 63304 KB Output is correct
30 Correct 53 ms 63412 KB Output is correct
31 Correct 40 ms 63300 KB Output is correct
32 Correct 64 ms 63376 KB Output is correct
33 Correct 56 ms 63412 KB Output is correct
34 Correct 61 ms 63464 KB Output is correct
35 Correct 2299 ms 102920 KB Output is correct
36 Correct 2298 ms 105460 KB Output is correct
37 Correct 2399 ms 103832 KB Output is correct
38 Correct 2448 ms 106384 KB Output is correct
39 Correct 2591 ms 100100 KB Output is correct
40 Correct 2608 ms 95120 KB Output is correct
41 Correct 3303 ms 118784 KB Output is correct
42 Correct 1492 ms 96632 KB Output is correct
43 Correct 1546 ms 72772 KB Output is correct
44 Correct 1754 ms 102340 KB Output is correct
45 Correct 3238 ms 113452 KB Output is correct
46 Correct 3274 ms 117732 KB Output is correct
47 Correct 3137 ms 116612 KB Output is correct
48 Correct 2653 ms 106192 KB Output is correct
49 Correct 2583 ms 107044 KB Output is correct
50 Correct 3538 ms 119836 KB Output is correct
51 Correct 3419 ms 120436 KB Output is correct
52 Correct 26 ms 62948 KB Output is correct
53 Correct 3892 ms 120452 KB Output is correct
54 Correct 1855 ms 103148 KB Output is correct
55 Correct 3196 ms 114872 KB Output is correct
56 Correct 3324 ms 119304 KB Output is correct
57 Execution timed out 10064 ms 255588 KB Time limit exceeded
58 Halted 0 ms 0 KB -