oj.uz

Submission #477561

# Submission time Handle Problem Language Result Execution time Memory
477561 2021-10-02T15:48:28 Z cheissmart Two Dishes (JOI19_dishes) C++14
100 / 100
 2925 ms 232568 KB 
#include <bits/stdc++.h>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define MP make_pair
#define EB emplace_back
#define ALL(v) (v).begin(), (v).end()

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

string _reset = "\u001b[0m", _yellow = "\u001b[33m", _bold = "\u001b[1m";
void DBG() { cerr << "]" << _reset << endl; }
template<class H, class...T> void DBG(H h, T ...t) {
	cerr << to_string(h);
	if(sizeof ...(t)) cerr << ", ";
	DBG(t...);
}
#ifdef CHEISSMART
#define debug(...) cerr << _yellow << _bold << "Line(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#else
#define debug(...)
#endif

const int INF = 1e9 + 7, N = 1e6 + 7;

int p[N], q[N];
ll a[N], b[N], s[N], t[N];
V<pi> G[N];

signed main()
{
	IO_OP;
	
	int n, m;
	cin >> n >> m;
	for(int i = 1; i <= n; i++) {
		cin >> a[i] >> s[i] >> p[i];
		a[i] += a[i - 1];
	}
	for(int i = 1; i <= m; i++) {
		cin >> b[i] >> t[i] >> q[i];
		b[i] += b[i - 1];
	}
	ll ans = 0;
	for(int i = 1; i <= n; i++) {
		/*
		a[i] + b[j] <= s[i]
		b[j] <= s[i] - a[i]
		*/
		int j = int(upper_bound(b, b + m + 1, s[i] - a[i]) - b);
		if(!j) continue;
		// if(i-th a before j-th b) ans += p[i]
		G[i].EB(j, p[i]);
	}
	for(int j = 1; j <= m; j++) {
		/*
		a[i] + b[j] <= t[j]
		a[i] <= t[j] - b[j]
		*/
		int i = int(upper_bound(a, a + n + 1, t[j] - b[j]) - a);
		if(!i) continue;
		// original: if(j-th b before i-th a) ans += q[j]
		ans += q[j];
		// now: if(i-th a before j-th b) ans += -q[j]
		G[i].EB(j, -q[j]);
	}
	map<int, ll> mp;
	for(int i = 1; i <= n; i++) {
		sort(ALL(G[i]), [&](pi x, pi y) {
			return x.S < y.S;
		});
		for(auto [j, v] : G[i]) {
			// 0 ~ j - 1 add v
			ans += v;
			if(j > m) continue;
			mp[j] -= v;
			if(mp[j] < 0) {
				auto it = mp.find(j);
				while(it -> S < 0) {
					it++;
					if(it != mp.end()) {
						mp[it -> F] += mp[prev(it) -> F];
						mp.erase(prev(it));
					} else {
						mp.erase(prev(it));
						break;
					}
				}
			}

		}
	}
	for(auto [x, y]:mp)
		ans += y;
	cout << ans << '\n';

}

Compilation message

dishes.cpp: In function 'int main()':
dishes.cpp:78:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   78 |   for(auto [j, v] : G[i]) {
      |            ^
dishes.cpp:99:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   99 |  for(auto [x, y]:mp)
      |           ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 268 ms 49988 KB Output is correct
2 Correct 229 ms 39488 KB Output is correct
3 Correct 194 ms 40136 KB Output is correct
4 Correct 287 ms 43188 KB Output is correct
5 Correct 13 ms 23756 KB Output is correct
6 Correct 238 ms 39204 KB Output is correct
7 Correct 97 ms 29968 KB Output is correct
8 Correct 108 ms 33956 KB Output is correct
9 Correct 196 ms 40040 KB Output is correct
10 Correct 196 ms 37848 KB Output is correct
11 Correct 167 ms 40124 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23740 KB Output is correct
2 Correct 13 ms 23756 KB Output is correct
3 Correct 14 ms 23756 KB Output is correct
4 Correct 14 ms 23840 KB Output is correct
5 Correct 15 ms 23756 KB Output is correct
6 Correct 12 ms 23756 KB Output is correct
7 Correct 14 ms 23756 KB Output is correct
8 Correct 14 ms 23844 KB Output is correct
9 Correct 13 ms 23836 KB Output is correct
10 Correct 14 ms 23772 KB Output is correct
11 Correct 12 ms 23836 KB Output is correct
12 Correct 13 ms 23820 KB Output is correct
13 Correct 13 ms 23756 KB Output is correct
14 Correct 14 ms 23884 KB Output is correct
15 Correct 14 ms 23756 KB Output is correct
16 Correct 13 ms 23720 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23740 KB Output is correct
2 Correct 13 ms 23756 KB Output is correct
3 Correct 14 ms 23756 KB Output is correct
4 Correct 14 ms 23840 KB Output is correct
5 Correct 15 ms 23756 KB Output is correct
6 Correct 12 ms 23756 KB Output is correct
7 Correct 14 ms 23756 KB Output is correct
8 Correct 14 ms 23844 KB Output is correct
9 Correct 13 ms 23836 KB Output is correct
10 Correct 14 ms 23772 KB Output is correct
11 Correct 12 ms 23836 KB Output is correct
12 Correct 13 ms 23820 KB Output is correct
13 Correct 13 ms 23756 KB Output is correct
14 Correct 14 ms 23884 KB Output is correct
15 Correct 14 ms 23756 KB Output is correct
16 Correct 13 ms 23720 KB Output is correct
17 Correct 14 ms 23960 KB Output is correct
18 Correct 15 ms 24096 KB Output is correct
19 Correct 16 ms 24012 KB Output is correct
20 Correct 17 ms 23900 KB Output is correct
21 Correct 16 ms 23956 KB Output is correct
22 Correct 17 ms 23972 KB Output is correct
23 Correct 17 ms 24012 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23740 KB Output is correct
2 Correct 13 ms 23756 KB Output is correct
3 Correct 14 ms 23756 KB Output is correct
4 Correct 14 ms 23840 KB Output is correct
5 Correct 15 ms 23756 KB Output is correct
6 Correct 12 ms 23756 KB Output is correct
7 Correct 14 ms 23756 KB Output is correct
8 Correct 14 ms 23844 KB Output is correct
9 Correct 13 ms 23836 KB Output is correct
10 Correct 14 ms 23772 KB Output is correct
11 Correct 12 ms 23836 KB Output is correct
12 Correct 13 ms 23820 KB Output is correct
13 Correct 13 ms 23756 KB Output is correct
14 Correct 14 ms 23884 KB Output is correct
15 Correct 14 ms 23756 KB Output is correct
16 Correct 13 ms 23720 KB Output is correct
17 Correct 14 ms 23960 KB Output is correct
18 Correct 15 ms 24096 KB Output is correct
19 Correct 16 ms 24012 KB Output is correct
20 Correct 17 ms 23900 KB Output is correct
21 Correct 16 ms 23956 KB Output is correct
22 Correct 17 ms 23972 KB Output is correct
23 Correct 17 ms 24012 KB Output is correct
24 Correct 173 ms 38984 KB Output is correct
25 Correct 241 ms 48868 KB Output is correct
26 Correct 187 ms 39056 KB Output is correct
27 Correct 275 ms 50432 KB Output is correct
28 Correct 250 ms 38508 KB Output is correct
29 Correct 182 ms 40080 KB Output is correct
30 Correct 448 ms 39876 KB Output is correct
31 Correct 111 ms 35544 KB Output is correct
32 Correct 95 ms 33996 KB Output is correct
33 Correct 304 ms 36100 KB Output is correct
34 Correct 369 ms 44980 KB Output is correct
35 Correct 399 ms 40032 KB Output is correct
36 Correct 397 ms 39876 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23740 KB Output is correct
2 Correct 13 ms 23756 KB Output is correct
3 Correct 14 ms 23756 KB Output is correct
4 Correct 14 ms 23840 KB Output is correct
5 Correct 15 ms 23756 KB Output is correct
6 Correct 12 ms 23756 KB Output is correct
7 Correct 14 ms 23756 KB Output is correct
8 Correct 14 ms 23844 KB Output is correct
9 Correct 13 ms 23836 KB Output is correct
10 Correct 14 ms 23772 KB Output is correct
11 Correct 12 ms 23836 KB Output is correct
12 Correct 13 ms 23820 KB Output is correct
13 Correct 13 ms 23756 KB Output is correct
14 Correct 14 ms 23884 KB Output is correct
15 Correct 14 ms 23756 KB Output is correct
16 Correct 13 ms 23720 KB Output is correct
17 Correct 14 ms 23960 KB Output is correct
18 Correct 15 ms 24096 KB Output is correct
19 Correct 16 ms 24012 KB Output is correct
20 Correct 17 ms 23900 KB Output is correct
21 Correct 16 ms 23956 KB Output is correct
22 Correct 17 ms 23972 KB Output is correct
23 Correct 17 ms 24012 KB Output is correct
24 Correct 173 ms 38984 KB Output is correct
25 Correct 241 ms 48868 KB Output is correct
26 Correct 187 ms 39056 KB Output is correct
27 Correct 275 ms 50432 KB Output is correct
28 Correct 250 ms 38508 KB Output is correct
29 Correct 182 ms 40080 KB Output is correct
30 Correct 448 ms 39876 KB Output is correct
31 Correct 111 ms 35544 KB Output is correct
32 Correct 95 ms 33996 KB Output is correct
33 Correct 304 ms 36100 KB Output is correct
34 Correct 369 ms 44980 KB Output is correct
35 Correct 399 ms 40032 KB Output is correct
36 Correct 397 ms 39876 KB Output is correct
37 Correct 196 ms 38996 KB Output is correct
38 Correct 304 ms 50544 KB Output is correct
39 Correct 380 ms 50332 KB Output is correct
40 Correct 215 ms 37908 KB Output is correct
41 Correct 12 ms 23776 KB Output is correct
42 Correct 483 ms 39924 KB Output is correct
43 Correct 325 ms 36164 KB Output is correct
44 Correct 371 ms 44924 KB Output is correct
45 Correct 430 ms 40008 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23740 KB Output is correct
2 Correct 13 ms 23756 KB Output is correct
3 Correct 14 ms 23756 KB Output is correct
4 Correct 14 ms 23840 KB Output is correct
5 Correct 15 ms 23756 KB Output is correct
6 Correct 12 ms 23756 KB Output is correct
7 Correct 14 ms 23756 KB Output is correct
8 Correct 14 ms 23844 KB Output is correct
9 Correct 13 ms 23836 KB Output is correct
10 Correct 14 ms 23772 KB Output is correct
11 Correct 12 ms 23836 KB Output is correct
12 Correct 13 ms 23820 KB Output is correct
13 Correct 13 ms 23756 KB Output is correct
14 Correct 14 ms 23884 KB Output is correct
15 Correct 14 ms 23756 KB Output is correct
16 Correct 13 ms 23720 KB Output is correct
17 Correct 14 ms 23960 KB Output is correct
18 Correct 15 ms 24096 KB Output is correct
19 Correct 16 ms 24012 KB Output is correct
20 Correct 17 ms 23900 KB Output is correct
21 Correct 16 ms 23956 KB Output is correct
22 Correct 17 ms 23972 KB Output is correct
23 Correct 17 ms 24012 KB Output is correct
24 Correct 173 ms 38984 KB Output is correct
25 Correct 241 ms 48868 KB Output is correct
26 Correct 187 ms 39056 KB Output is correct
27 Correct 275 ms 50432 KB Output is correct
28 Correct 250 ms 38508 KB Output is correct
29 Correct 182 ms 40080 KB Output is correct
30 Correct 448 ms 39876 KB Output is correct
31 Correct 111 ms 35544 KB Output is correct
32 Correct 95 ms 33996 KB Output is correct
33 Correct 304 ms 36100 KB Output is correct
34 Correct 369 ms 44980 KB Output is correct
35 Correct 399 ms 40032 KB Output is correct
36 Correct 397 ms 39876 KB Output is correct
37 Correct 196 ms 38996 KB Output is correct
38 Correct 304 ms 50544 KB Output is correct
39 Correct 380 ms 50332 KB Output is correct
40 Correct 215 ms 37908 KB Output is correct
41 Correct 12 ms 23776 KB Output is correct
42 Correct 483 ms 39924 KB Output is correct
43 Correct 325 ms 36164 KB Output is correct
44 Correct 371 ms 44924 KB Output is correct
45 Correct 430 ms 40008 KB Output is correct
46 Correct 993 ms 98600 KB Output is correct
47 Correct 1656 ms 156800 KB Output is correct
48 Correct 2230 ms 156856 KB Output is correct
49 Correct 949 ms 94236 KB Output is correct
50 Correct 2802 ms 104504 KB Output is correct
51 Correct 1718 ms 83336 KB Output is correct
52 Correct 2207 ms 127236 KB Output is correct
53 Correct 2523 ms 103776 KB Output is correct

Subtask #7
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 268 ms 49988 KB Output is correct
2 Correct 229 ms 39488 KB Output is correct
3 Correct 194 ms 40136 KB Output is correct
4 Correct 287 ms 43188 KB Output is correct
5 Correct 13 ms 23756 KB Output is correct
6 Correct 238 ms 39204 KB Output is correct
7 Correct 97 ms 29968 KB Output is correct
8 Correct 108 ms 33956 KB Output is correct
9 Correct 196 ms 40040 KB Output is correct
10 Correct 196 ms 37848 KB Output is correct
11 Correct 167 ms 40124 KB Output is correct
12 Correct 14 ms 23740 KB Output is correct
13 Correct 13 ms 23756 KB Output is correct
14 Correct 14 ms 23756 KB Output is correct
15 Correct 14 ms 23840 KB Output is correct
16 Correct 15 ms 23756 KB Output is correct
17 Correct 12 ms 23756 KB Output is correct
18 Correct 14 ms 23756 KB Output is correct
19 Correct 14 ms 23844 KB Output is correct
20 Correct 13 ms 23836 KB Output is correct
21 Correct 14 ms 23772 KB Output is correct
22 Correct 12 ms 23836 KB Output is correct
23 Correct 13 ms 23820 KB Output is correct
24 Correct 13 ms 23756 KB Output is correct
25 Correct 14 ms 23884 KB Output is correct
26 Correct 14 ms 23756 KB Output is correct
27 Correct 13 ms 23720 KB Output is correct
28 Correct 14 ms 23960 KB Output is correct
29 Correct 15 ms 24096 KB Output is correct
30 Correct 16 ms 24012 KB Output is correct
31 Correct 17 ms 23900 KB Output is correct
32 Correct 16 ms 23956 KB Output is correct
33 Correct 17 ms 23972 KB Output is correct
34 Correct 17 ms 24012 KB Output is correct
35 Correct 173 ms 38984 KB Output is correct
36 Correct 241 ms 48868 KB Output is correct
37 Correct 187 ms 39056 KB Output is correct
38 Correct 275 ms 50432 KB Output is correct
39 Correct 250 ms 38508 KB Output is correct
40 Correct 182 ms 40080 KB Output is correct
41 Correct 448 ms 39876 KB Output is correct
42 Correct 111 ms 35544 KB Output is correct
43 Correct 95 ms 33996 KB Output is correct
44 Correct 304 ms 36100 KB Output is correct
45 Correct 369 ms 44980 KB Output is correct
46 Correct 399 ms 40032 KB Output is correct
47 Correct 397 ms 39876 KB Output is correct
48 Correct 196 ms 38996 KB Output is correct
49 Correct 304 ms 50544 KB Output is correct
50 Correct 380 ms 50332 KB Output is correct
51 Correct 215 ms 37908 KB Output is correct
52 Correct 12 ms 23776 KB Output is correct
53 Correct 483 ms 39924 KB Output is correct
54 Correct 325 ms 36164 KB Output is correct
55 Correct 371 ms 44924 KB Output is correct
56 Correct 430 ms 40008 KB Output is correct
57 Correct 278 ms 51204 KB Output is correct
58 Correct 215 ms 37916 KB Output is correct
59 Correct 223 ms 37856 KB Output is correct
60 Correct 339 ms 50440 KB Output is correct
61 Correct 561 ms 52520 KB Output is correct
62 Correct 14 ms 23756 KB Output is correct
63 Correct 487 ms 39988 KB Output is correct
64 Correct 309 ms 36084 KB Output is correct
65 Correct 416 ms 40448 KB Output is correct
66 Correct 443 ms 47428 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 268 ms 49988 KB Output is correct
2 Correct 229 ms 39488 KB Output is correct
3 Correct 194 ms 40136 KB Output is correct
4 Correct 287 ms 43188 KB Output is correct
5 Correct 13 ms 23756 KB Output is correct
6 Correct 238 ms 39204 KB Output is correct
7 Correct 97 ms 29968 KB Output is correct
8 Correct 108 ms 33956 KB Output is correct
9 Correct 196 ms 40040 KB Output is correct
10 Correct 196 ms 37848 KB Output is correct
11 Correct 167 ms 40124 KB Output is correct
12 Correct 14 ms 23740 KB Output is correct
13 Correct 13 ms 23756 KB Output is correct
14 Correct 14 ms 23756 KB Output is correct
15 Correct 14 ms 23840 KB Output is correct
16 Correct 15 ms 23756 KB Output is correct
17 Correct 12 ms 23756 KB Output is correct
18 Correct 14 ms 23756 KB Output is correct
19 Correct 14 ms 23844 KB Output is correct
20 Correct 13 ms 23836 KB Output is correct
21 Correct 14 ms 23772 KB Output is correct
22 Correct 12 ms 23836 KB Output is correct
23 Correct 13 ms 23820 KB Output is correct
24 Correct 13 ms 23756 KB Output is correct
25 Correct 14 ms 23884 KB Output is correct
26 Correct 14 ms 23756 KB Output is correct
27 Correct 13 ms 23720 KB Output is correct
28 Correct 14 ms 23960 KB Output is correct
29 Correct 15 ms 24096 KB Output is correct
30 Correct 16 ms 24012 KB Output is correct
31 Correct 17 ms 23900 KB Output is correct
32 Correct 16 ms 23956 KB Output is correct
33 Correct 17 ms 23972 KB Output is correct
34 Correct 17 ms 24012 KB Output is correct
35 Correct 173 ms 38984 KB Output is correct
36 Correct 241 ms 48868 KB Output is correct
37 Correct 187 ms 39056 KB Output is correct
38 Correct 275 ms 50432 KB Output is correct
39 Correct 250 ms 38508 KB Output is correct
40 Correct 182 ms 40080 KB Output is correct
41 Correct 448 ms 39876 KB Output is correct
42 Correct 111 ms 35544 KB Output is correct
43 Correct 95 ms 33996 KB Output is correct
44 Correct 304 ms 36100 KB Output is correct
45 Correct 369 ms 44980 KB Output is correct
46 Correct 399 ms 40032 KB Output is correct
47 Correct 397 ms 39876 KB Output is correct
48 Correct 196 ms 38996 KB Output is correct
49 Correct 304 ms 50544 KB Output is correct
50 Correct 380 ms 50332 KB Output is correct
51 Correct 215 ms 37908 KB Output is correct
52 Correct 12 ms 23776 KB Output is correct
53 Correct 483 ms 39924 KB Output is correct
54 Correct 325 ms 36164 KB Output is correct
55 Correct 371 ms 44924 KB Output is correct
56 Correct 430 ms 40008 KB Output is correct
57 Correct 993 ms 98600 KB Output is correct
58 Correct 1656 ms 156800 KB Output is correct
59 Correct 2230 ms 156856 KB Output is correct
60 Correct 949 ms 94236 KB Output is correct
61 Correct 2802 ms 104504 KB Output is correct
62 Correct 1718 ms 83336 KB Output is correct
63 Correct 2207 ms 127236 KB Output is correct
64 Correct 2523 ms 103776 KB Output is correct
65 Correct 278 ms 51204 KB Output is correct
66 Correct 215 ms 37916 KB Output is correct
67 Correct 223 ms 37856 KB Output is correct
68 Correct 339 ms 50440 KB Output is correct
69 Correct 561 ms 52520 KB Output is correct
70 Correct 14 ms 23756 KB Output is correct
71 Correct 487 ms 39988 KB Output is correct
72 Correct 309 ms 36084 KB Output is correct
73 Correct 416 ms 40448 KB Output is correct
74 Correct 443 ms 47428 KB Output is correct
75 Correct 1772 ms 232568 KB Output is correct
76 Correct 1141 ms 166052 KB Output is correct
77 Correct 1175 ms 153112 KB Output is correct
78 Correct 2245 ms 215696 KB Output is correct
79 Correct 2925 ms 174936 KB Output is correct
80 Correct 1783 ms 151756 KB Output is correct
81 Correct 2070 ms 172532 KB Output is correct
82 Correct 2593 ms 142692 KB Output is correct
83 Correct 2624 ms 161516 KB Output is correct