oj.uz

Submission #123314

# Submission time Handle Problem Language Result Execution time Memory
123314 2019-07-01T07:05:42 Z 김세빈(#3018) Two Dishes (JOI19_dishes) C++14
74 / 100
 2932 ms 165124 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct fenwick{
	ll T[1010101];
	ll m;
	
	void init(int _m) { m = _m; }
	
	void addval(ll p, ll v)
	{
		if(!p) T[0] += v;
		else{
			for(; p<=m; p+=p&-p){
				T[p] += v;
			}
		}
	}
	
	ll getval(ll p)
	{
		ll ret = T[0];
		
		for(; p; p-=p&-p){
			ret += T[p];
		}
		
		return ret;
	}
};

ll A[1010101], S[1010101], P1[1010101], P2[1010101];
ll B[1010101], T[1010101], Q1[1010101], Q2[1010101];
vector <ll> V[1010101];
set <ll> X;
fenwick F;
ll n, m, ans;

void query(ll f, ll p, ll k)
{
	ll x;
	
	if(f == 0) F.addval(0, k);
	else if(f == 1){
		if(X.find(p) == X.end()) X.insert(p);
		F.addval(p, k);
		return;
	}
	else if(f == 2){
		if(X.find(p) == X.end()) X.insert(p);
		F.addval(p, k);
	}
	
	for(; ; ){
		auto it = X.upper_bound(p);
		if(it == X.end()) break;
		
		x = F.getval(*it) - F.getval(*it - 1) - Q1[*it];
		
		if(x <= k){
			F.addval(*it, -x); k -= x;
			X.erase(it);
		}
		else{
			F.addval(*it, -k);
			break;
		}
	}
}

int main()
{
	ll i, k, x;
	
	scanf("%lld%lld", &n, &m);
	
	for(i=1; i<=n; i++){
		scanf("%lld%lld%lld", A + i, S + i, P1 + i);
		A[i] += A[i - 1];
		if(P1[i] < 0){
			ans += P1[i];
			P2[i] = -P1[i], P1[i] = 0;
		}
	}
	
	for(i=1; i<=m; i++){
		scanf("%lld%lld%lld", B + i, T + i, Q1 + i);
		B[i] += B[i - 1];
		if(Q1[i] < 0){
			ans += Q1[i];
			Q2[i] = -Q1[i], Q1[i] = 0;
		}
	}	
	
	for(i=1; i<=n; i++){
		S[i] = upper_bound(B, B + m + 1, S[i] - A[i]) - B;
	}
	
	for(i=1; i<=m; i++){
		T[i] = upper_bound(A, A + n + 1, T[i] - B[i]) - A;
		V[T[i]].push_back(i);
	}
	
	F.init(m);
	
	for(i=1; i<=m; i++){
		if(T[i] == 0) swap(Q1[i], Q2[i]);
		F.addval(i, Q1[i]);
	}
	
	for(i=1; i<=n; i++){
		sort(V[i].begin(), V[i].end());
		for(ll &t: V[i]){
			swap(Q1[t], Q2[t]);
			
			if(Q1[t] == 0){
				if(X.find(t) == X.end()) X.insert(t);
			}
			else{
				if(X.find(t) == X.end()){
					query(2, t, Q1[t]);
				}
				else{
					x = F.getval(t) - F.getval(t - 1);
					if(x <= Q1[t]){
						X.erase(t);
						query(2, t, Q1[t] - x);
					}
				}
			}
		}
		
		if(P2[i] == 0){
			if(S[i]) query(0, S[i] - 1, P1[i]);
		}
		else{
			if(S[i]) query(1, S[i], P2[i]);
			else F.addval(0, P2[i]);
		}
	}
	
	printf("%lld\n", F.getval(m) + ans);
	
	return 0;
}

Compilation message

dishes.cpp: In function 'int main()':
dishes.cpp:76:8: warning: unused variable 'k' [-Wunused-variable]
  ll i, k, x;
        ^
dishes.cpp:78:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~~~~~
dishes.cpp:81:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld%lld", A + i, S + i, P1 + i);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dishes.cpp:90:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld%lld", B + i, T + i, Q1 + i);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 333 ms 49004 KB Output is correct
2 Correct 291 ms 40392 KB Output is correct
3 Correct 244 ms 36732 KB Output is correct
4 Correct 333 ms 46528 KB Output is correct
5 Correct 23 ms 24156 KB Output is correct
6 Correct 306 ms 39324 KB Output is correct
7 Correct 132 ms 32356 KB Output is correct
8 Correct 129 ms 28796 KB Output is correct
9 Correct 252 ms 36840 KB Output is correct
10 Correct 257 ms 42872 KB Output is correct
11 Correct 182 ms 36808 KB Output is correct

Subtask #2
3.0 / 3.0

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

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 24056 KB Output is correct
2 Correct 23 ms 24184 KB Output is correct
3 Correct 23 ms 24056 KB Output is correct
4 Correct 23 ms 24184 KB Output is correct
5 Correct 25 ms 24184 KB Output is correct
6 Correct 23 ms 24184 KB Output is correct
7 Correct 23 ms 24184 KB Output is correct
8 Correct 23 ms 24184 KB Output is correct
9 Correct 23 ms 24184 KB Output is correct
10 Correct 23 ms 24184 KB Output is correct
11 Correct 23 ms 24184 KB Output is correct
12 Correct 24 ms 24184 KB Output is correct
13 Correct 23 ms 24060 KB Output is correct
14 Correct 24 ms 24184 KB Output is correct
15 Correct 24 ms 24184 KB Output is correct
16 Correct 23 ms 24184 KB Output is correct
17 Correct 25 ms 24184 KB Output is correct
18 Correct 29 ms 24440 KB Output is correct
19 Correct 26 ms 24312 KB Output is correct
20 Correct 30 ms 24312 KB Output is correct
21 Correct 27 ms 24312 KB Output is correct
22 Correct 26 ms 24312 KB Output is correct
23 Correct 31 ms 24312 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 24056 KB Output is correct
2 Correct 23 ms 24184 KB Output is correct
3 Correct 23 ms 24056 KB Output is correct
4 Correct 23 ms 24184 KB Output is correct
5 Correct 25 ms 24184 KB Output is correct
6 Correct 23 ms 24184 KB Output is correct
7 Correct 23 ms 24184 KB Output is correct
8 Correct 23 ms 24184 KB Output is correct
9 Correct 23 ms 24184 KB Output is correct
10 Correct 23 ms 24184 KB Output is correct
11 Correct 23 ms 24184 KB Output is correct
12 Correct 24 ms 24184 KB Output is correct
13 Correct 23 ms 24060 KB Output is correct
14 Correct 24 ms 24184 KB Output is correct
15 Correct 24 ms 24184 KB Output is correct
16 Correct 23 ms 24184 KB Output is correct
17 Correct 25 ms 24184 KB Output is correct
18 Correct 29 ms 24440 KB Output is correct
19 Correct 26 ms 24312 KB Output is correct
20 Correct 30 ms 24312 KB Output is correct
21 Correct 27 ms 24312 KB Output is correct
22 Correct 26 ms 24312 KB Output is correct
23 Correct 31 ms 24312 KB Output is correct
24 Correct 225 ms 38464 KB Output is correct
25 Correct 347 ms 47772 KB Output is correct
26 Correct 236 ms 38344 KB Output is correct
27 Correct 371 ms 52444 KB Output is correct
28 Correct 299 ms 39280 KB Output is correct
29 Correct 208 ms 36836 KB Output is correct
30 Correct 468 ms 40980 KB Output is correct
31 Correct 168 ms 38284 KB Output is correct
32 Correct 115 ms 28792 KB Output is correct
33 Correct 341 ms 39884 KB Output is correct
34 Correct 419 ms 43380 KB Output is correct
35 Correct 399 ms 41064 KB Output is correct
36 Correct 401 ms 40940 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 24056 KB Output is correct
2 Correct 23 ms 24184 KB Output is correct
3 Correct 23 ms 24056 KB Output is correct
4 Correct 23 ms 24184 KB Output is correct
5 Correct 25 ms 24184 KB Output is correct
6 Correct 23 ms 24184 KB Output is correct
7 Correct 23 ms 24184 KB Output is correct
8 Correct 23 ms 24184 KB Output is correct
9 Correct 23 ms 24184 KB Output is correct
10 Correct 23 ms 24184 KB Output is correct
11 Correct 23 ms 24184 KB Output is correct
12 Correct 24 ms 24184 KB Output is correct
13 Correct 23 ms 24060 KB Output is correct
14 Correct 24 ms 24184 KB Output is correct
15 Correct 24 ms 24184 KB Output is correct
16 Correct 23 ms 24184 KB Output is correct
17 Correct 25 ms 24184 KB Output is correct
18 Correct 29 ms 24440 KB Output is correct
19 Correct 26 ms 24312 KB Output is correct
20 Correct 30 ms 24312 KB Output is correct
21 Correct 27 ms 24312 KB Output is correct
22 Correct 26 ms 24312 KB Output is correct
23 Correct 31 ms 24312 KB Output is correct
24 Correct 225 ms 38464 KB Output is correct
25 Correct 347 ms 47772 KB Output is correct
26 Correct 236 ms 38344 KB Output is correct
27 Correct 371 ms 52444 KB Output is correct
28 Correct 299 ms 39280 KB Output is correct
29 Correct 208 ms 36836 KB Output is correct
30 Correct 468 ms 40980 KB Output is correct
31 Correct 168 ms 38284 KB Output is correct
32 Correct 115 ms 28792 KB Output is correct
33 Correct 341 ms 39884 KB Output is correct
34 Correct 419 ms 43380 KB Output is correct
35 Correct 399 ms 41064 KB Output is correct
36 Correct 401 ms 40940 KB Output is correct
37 Correct 281 ms 38344 KB Output is correct
38 Correct 393 ms 52376 KB Output is correct
39 Correct 423 ms 52392 KB Output is correct
40 Correct 276 ms 42880 KB Output is correct
41 Correct 24 ms 24056 KB Output is correct
42 Correct 520 ms 41260 KB Output is correct
43 Correct 386 ms 39916 KB Output is correct
44 Correct 449 ms 43404 KB Output is correct
45 Correct 416 ms 40952 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 24056 KB Output is correct
2 Correct 23 ms 24184 KB Output is correct
3 Correct 23 ms 24056 KB Output is correct
4 Correct 23 ms 24184 KB Output is correct
5 Correct 25 ms 24184 KB Output is correct
6 Correct 23 ms 24184 KB Output is correct
7 Correct 23 ms 24184 KB Output is correct
8 Correct 23 ms 24184 KB Output is correct
9 Correct 23 ms 24184 KB Output is correct
10 Correct 23 ms 24184 KB Output is correct
11 Correct 23 ms 24184 KB Output is correct
12 Correct 24 ms 24184 KB Output is correct
13 Correct 23 ms 24060 KB Output is correct
14 Correct 24 ms 24184 KB Output is correct
15 Correct 24 ms 24184 KB Output is correct
16 Correct 23 ms 24184 KB Output is correct
17 Correct 25 ms 24184 KB Output is correct
18 Correct 29 ms 24440 KB Output is correct
19 Correct 26 ms 24312 KB Output is correct
20 Correct 30 ms 24312 KB Output is correct
21 Correct 27 ms 24312 KB Output is correct
22 Correct 26 ms 24312 KB Output is correct
23 Correct 31 ms 24312 KB Output is correct
24 Correct 225 ms 38464 KB Output is correct
25 Correct 347 ms 47772 KB Output is correct
26 Correct 236 ms 38344 KB Output is correct
27 Correct 371 ms 52444 KB Output is correct
28 Correct 299 ms 39280 KB Output is correct
29 Correct 208 ms 36836 KB Output is correct
30 Correct 468 ms 40980 KB Output is correct
31 Correct 168 ms 38284 KB Output is correct
32 Correct 115 ms 28792 KB Output is correct
33 Correct 341 ms 39884 KB Output is correct
34 Correct 419 ms 43380 KB Output is correct
35 Correct 399 ms 41064 KB Output is correct
36 Correct 401 ms 40940 KB Output is correct
37 Correct 281 ms 38344 KB Output is correct
38 Correct 393 ms 52376 KB Output is correct
39 Correct 423 ms 52392 KB Output is correct
40 Correct 276 ms 42880 KB Output is correct
41 Correct 24 ms 24056 KB Output is correct
42 Correct 520 ms 41260 KB Output is correct
43 Correct 386 ms 39916 KB Output is correct
44 Correct 449 ms 43404 KB Output is correct
45 Correct 416 ms 40952 KB Output is correct
46 Correct 1326 ms 94768 KB Output is correct
47 Correct 2133 ms 165124 KB Output is correct
48 Correct 2340 ms 165048 KB Output is correct
49 Correct 1312 ms 118032 KB Output is correct
50 Correct 2932 ms 108196 KB Output is correct
51 Correct 2023 ms 101536 KB Output is correct
52 Correct 2533 ms 116964 KB Output is correct
53 Correct 2644 ms 107800 KB Output is correct

Subtask #7
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 333 ms 49004 KB Output is correct
2 Correct 291 ms 40392 KB Output is correct
3 Correct 244 ms 36732 KB Output is correct
4 Correct 333 ms 46528 KB Output is correct
5 Correct 23 ms 24156 KB Output is correct
6 Correct 306 ms 39324 KB Output is correct
7 Correct 132 ms 32356 KB Output is correct
8 Correct 129 ms 28796 KB Output is correct
9 Correct 252 ms 36840 KB Output is correct
10 Correct 257 ms 42872 KB Output is correct
11 Correct 182 ms 36808 KB Output is correct
12 Correct 23 ms 24056 KB Output is correct
13 Correct 23 ms 24184 KB Output is correct
14 Correct 23 ms 24056 KB Output is correct
15 Correct 23 ms 24184 KB Output is correct
16 Correct 25 ms 24184 KB Output is correct
17 Correct 23 ms 24184 KB Output is correct
18 Correct 23 ms 24184 KB Output is correct
19 Correct 23 ms 24184 KB Output is correct
20 Correct 23 ms 24184 KB Output is correct
21 Correct 23 ms 24184 KB Output is correct
22 Correct 23 ms 24184 KB Output is correct
23 Correct 24 ms 24184 KB Output is correct
24 Correct 23 ms 24060 KB Output is correct
25 Correct 24 ms 24184 KB Output is correct
26 Correct 24 ms 24184 KB Output is correct
27 Correct 23 ms 24184 KB Output is correct
28 Correct 25 ms 24184 KB Output is correct
29 Correct 29 ms 24440 KB Output is correct
30 Correct 26 ms 24312 KB Output is correct
31 Correct 30 ms 24312 KB Output is correct
32 Correct 27 ms 24312 KB Output is correct
33 Correct 26 ms 24312 KB Output is correct
34 Correct 31 ms 24312 KB Output is correct
35 Correct 225 ms 38464 KB Output is correct
36 Correct 347 ms 47772 KB Output is correct
37 Correct 236 ms 38344 KB Output is correct
38 Correct 371 ms 52444 KB Output is correct
39 Correct 299 ms 39280 KB Output is correct
40 Correct 208 ms 36836 KB Output is correct
41 Correct 468 ms 40980 KB Output is correct
42 Correct 168 ms 38284 KB Output is correct
43 Correct 115 ms 28792 KB Output is correct
44 Correct 341 ms 39884 KB Output is correct
45 Correct 419 ms 43380 KB Output is correct
46 Correct 399 ms 41064 KB Output is correct
47 Correct 401 ms 40940 KB Output is correct
48 Correct 281 ms 38344 KB Output is correct
49 Correct 393 ms 52376 KB Output is correct
50 Correct 423 ms 52392 KB Output is correct
51 Correct 276 ms 42880 KB Output is correct
52 Correct 24 ms 24056 KB Output is correct
53 Correct 520 ms 41260 KB Output is correct
54 Correct 386 ms 39916 KB Output is correct
55 Correct 449 ms 43404 KB Output is correct
56 Correct 416 ms 40952 KB Output is correct
57 Correct 373 ms 49252 KB Output is correct
58 Correct 431 ms 53984 KB Output is correct
59 Incorrect 294 ms 43132 KB Output isn't correct
60 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 333 ms 49004 KB Output is correct
2 Correct 291 ms 40392 KB Output is correct
3 Correct 244 ms 36732 KB Output is correct
4 Correct 333 ms 46528 KB Output is correct
5 Correct 23 ms 24156 KB Output is correct
6 Correct 306 ms 39324 KB Output is correct
7 Correct 132 ms 32356 KB Output is correct
8 Correct 129 ms 28796 KB Output is correct
9 Correct 252 ms 36840 KB Output is correct
10 Correct 257 ms 42872 KB Output is correct
11 Correct 182 ms 36808 KB Output is correct
12 Correct 23 ms 24056 KB Output is correct
13 Correct 23 ms 24184 KB Output is correct
14 Correct 23 ms 24056 KB Output is correct
15 Correct 23 ms 24184 KB Output is correct
16 Correct 25 ms 24184 KB Output is correct
17 Correct 23 ms 24184 KB Output is correct
18 Correct 23 ms 24184 KB Output is correct
19 Correct 23 ms 24184 KB Output is correct
20 Correct 23 ms 24184 KB Output is correct
21 Correct 23 ms 24184 KB Output is correct
22 Correct 23 ms 24184 KB Output is correct
23 Correct 24 ms 24184 KB Output is correct
24 Correct 23 ms 24060 KB Output is correct
25 Correct 24 ms 24184 KB Output is correct
26 Correct 24 ms 24184 KB Output is correct
27 Correct 23 ms 24184 KB Output is correct
28 Correct 25 ms 24184 KB Output is correct
29 Correct 29 ms 24440 KB Output is correct
30 Correct 26 ms 24312 KB Output is correct
31 Correct 30 ms 24312 KB Output is correct
32 Correct 27 ms 24312 KB Output is correct
33 Correct 26 ms 24312 KB Output is correct
34 Correct 31 ms 24312 KB Output is correct
35 Correct 225 ms 38464 KB Output is correct
36 Correct 347 ms 47772 KB Output is correct
37 Correct 236 ms 38344 KB Output is correct
38 Correct 371 ms 52444 KB Output is correct
39 Correct 299 ms 39280 KB Output is correct
40 Correct 208 ms 36836 KB Output is correct
41 Correct 468 ms 40980 KB Output is correct
42 Correct 168 ms 38284 KB Output is correct
43 Correct 115 ms 28792 KB Output is correct
44 Correct 341 ms 39884 KB Output is correct
45 Correct 419 ms 43380 KB Output is correct
46 Correct 399 ms 41064 KB Output is correct
47 Correct 401 ms 40940 KB Output is correct
48 Correct 281 ms 38344 KB Output is correct
49 Correct 393 ms 52376 KB Output is correct
50 Correct 423 ms 52392 KB Output is correct
51 Correct 276 ms 42880 KB Output is correct
52 Correct 24 ms 24056 KB Output is correct
53 Correct 520 ms 41260 KB Output is correct
54 Correct 386 ms 39916 KB Output is correct
55 Correct 449 ms 43404 KB Output is correct
56 Correct 416 ms 40952 KB Output is correct
57 Correct 1326 ms 94768 KB Output is correct
58 Correct 2133 ms 165124 KB Output is correct
59 Correct 2340 ms 165048 KB Output is correct
60 Correct 1312 ms 118032 KB Output is correct
61 Correct 2932 ms 108196 KB Output is correct
62 Correct 2023 ms 101536 KB Output is correct
63 Correct 2533 ms 116964 KB Output is correct
64 Correct 2644 ms 107800 KB Output is correct
65 Correct 373 ms 49252 KB Output is correct
66 Correct 431 ms 53984 KB Output is correct
67 Incorrect 294 ms 43132 KB Output isn't correct
68 Halted 0 ms 0 KB -