oj.uz

답안 #123523

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
123523 2019-07-01T14:23:04 Z sebinkim Two Dishes (JOI19_dishes) C++14
100 / 100
 3516 ms 159732 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct fenwick{
	ll T[1010101];
	ll m;
	
	void init(ll _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], P[1010101];
ll B[1010101], T[1010101], Q[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);
	}
	
	for(; ; ){
		auto it = X.upper_bound(p);
		if(it == X.end()) break;
		
		x = F.getval(*it) - F.getval(*it - 1) - Q[*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, P + i);
		A[i] += A[i - 1];
	}
	
	for(i=1; i<=m; i++){
		scanf("%lld%lld%lld", B + i, T + i, Q + i);
		B[i] += B[i - 1];
	}	
	
	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) Q[i] = 0;
		F.addval(i, Q[i]);
	}
	
	for(i=1; i<=n; i++){
		for(ll &t: V[i]){
			if(Q[t] >= 0){
				Q[t] = 0;
				if(X.find(t) == X.end()) X.insert(t);
			}
		}
		
		if(S[i] > m) F.addval(0, P[i]);
		else if(S[i]){
			if(X.find(S[i]) == X.end()) X.insert(S[i]);
			query(0, S[i] - 1, P[i]);
		}
		
		for(ll &t: V[i]){
			if(Q[t] < 0){
				Q[t] = 0;
				x = F.getval(t) - F.getval(t - 1);
				if(x <= 0){
					if(X.find(t) != X.end()) X.erase(t);
					query(1, t, -x);
				}
			}
		}
	}
	
	printf("%lld\n", F.getval(m) + ans);
	
	return 0;
}

Compilation message

dishes.cpp: In function 'int main()':
dishes.cpp:71:8: warning: unused variable 'k' [-Wunused-variable]
  ll i, k, x;
        ^
dishes.cpp:73: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:76: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, P + i);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
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", B + i, T + i, Q + i);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 341 ms 52600 KB Output is correct
2 Correct 296 ms 44192 KB Output is correct
3 Correct 244 ms 41060 KB Output is correct
4 Correct 348 ms 49152 KB Output is correct
5 Correct 23 ms 24056 KB Output is correct
6 Correct 305 ms 42372 KB Output is correct
7 Correct 133 ms 35684 KB Output is correct
8 Correct 127 ms 32632 KB Output is correct
9 Correct 252 ms 40376 KB Output is correct
10 Correct 259 ms 45516 KB Output is correct
11 Correct 183 ms 41064 KB Output is correct

Subtask #2
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 24056 KB Output is correct
2 Correct 28 ms 24056 KB Output is correct
3 Correct 23 ms 24056 KB Output is correct
4 Correct 23 ms 24184 KB Output is correct
5 Correct 23 ms 24056 KB Output is correct
6 Correct 23 ms 24024 KB Output is correct
7 Correct 23 ms 24056 KB Output is correct
8 Correct 23 ms 24056 KB Output is correct
9 Correct 23 ms 24056 KB Output is correct
10 Correct 23 ms 24056 KB Output is correct
11 Correct 23 ms 24056 KB Output is correct
12 Correct 23 ms 24056 KB Output is correct
13 Correct 23 ms 24060 KB Output is correct
14 Correct 23 ms 24056 KB Output is correct
15 Correct 24 ms 24056 KB Output is correct
16 Correct 23 ms 24028 KB Output is correct

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 24056 KB Output is correct
2 Correct 28 ms 24056 KB Output is correct
3 Correct 23 ms 24056 KB Output is correct
4 Correct 23 ms 24184 KB Output is correct
5 Correct 23 ms 24056 KB Output is correct
6 Correct 23 ms 24024 KB Output is correct
7 Correct 23 ms 24056 KB Output is correct
8 Correct 23 ms 24056 KB Output is correct
9 Correct 23 ms 24056 KB Output is correct
10 Correct 23 ms 24056 KB Output is correct
11 Correct 23 ms 24056 KB Output is correct
12 Correct 23 ms 24056 KB Output is correct
13 Correct 23 ms 24060 KB Output is correct
14 Correct 23 ms 24056 KB Output is correct
15 Correct 24 ms 24056 KB Output is correct
16 Correct 23 ms 24028 KB Output is correct
17 Correct 25 ms 24312 KB Output is correct
18 Correct 25 ms 24444 KB Output is correct
19 Correct 26 ms 24312 KB Output is correct
20 Correct 26 ms 24312 KB Output is correct
21 Correct 27 ms 24312 KB Output is correct
22 Correct 27 ms 24224 KB Output is correct
23 Correct 26 ms 24312 KB Output is correct

Subtask #4
39.0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 24056 KB Output is correct
2 Correct 28 ms 24056 KB Output is correct
3 Correct 23 ms 24056 KB Output is correct
4 Correct 23 ms 24184 KB Output is correct
5 Correct 23 ms 24056 KB Output is correct
6 Correct 23 ms 24024 KB Output is correct
7 Correct 23 ms 24056 KB Output is correct
8 Correct 23 ms 24056 KB Output is correct
9 Correct 23 ms 24056 KB Output is correct
10 Correct 23 ms 24056 KB Output is correct
11 Correct 23 ms 24056 KB Output is correct
12 Correct 23 ms 24056 KB Output is correct
13 Correct 23 ms 24060 KB Output is correct
14 Correct 23 ms 24056 KB Output is correct
15 Correct 24 ms 24056 KB Output is correct
16 Correct 23 ms 24028 KB Output is correct
17 Correct 25 ms 24312 KB Output is correct
18 Correct 25 ms 24444 KB Output is correct
19 Correct 26 ms 24312 KB Output is correct
20 Correct 26 ms 24312 KB Output is correct
21 Correct 27 ms 24312 KB Output is correct
22 Correct 27 ms 24224 KB Output is correct
23 Correct 26 ms 24312 KB Output is correct
24 Correct 244 ms 41268 KB Output is correct
25 Correct 326 ms 50364 KB Output is correct
26 Correct 253 ms 41084 KB Output is correct
27 Correct 350 ms 55084 KB Output is correct
28 Correct 311 ms 42088 KB Output is correct
29 Correct 207 ms 41060 KB Output is correct
30 Correct 518 ms 43768 KB Output is correct
31 Correct 163 ms 38924 KB Output is correct
32 Correct 120 ms 31144 KB Output is correct
33 Correct 378 ms 42604 KB Output is correct
34 Correct 448 ms 46224 KB Output is correct
35 Correct 458 ms 41728 KB Output is correct
36 Correct 446 ms 41716 KB Output is correct

Subtask #5
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 24056 KB Output is correct
2 Correct 28 ms 24056 KB Output is correct
3 Correct 23 ms 24056 KB Output is correct
4 Correct 23 ms 24184 KB Output is correct
5 Correct 23 ms 24056 KB Output is correct
6 Correct 23 ms 24024 KB Output is correct
7 Correct 23 ms 24056 KB Output is correct
8 Correct 23 ms 24056 KB Output is correct
9 Correct 23 ms 24056 KB Output is correct
10 Correct 23 ms 24056 KB Output is correct
11 Correct 23 ms 24056 KB Output is correct
12 Correct 23 ms 24056 KB Output is correct
13 Correct 23 ms 24060 KB Output is correct
14 Correct 23 ms 24056 KB Output is correct
15 Correct 24 ms 24056 KB Output is correct
16 Correct 23 ms 24028 KB Output is correct
17 Correct 25 ms 24312 KB Output is correct
18 Correct 25 ms 24444 KB Output is correct
19 Correct 26 ms 24312 KB Output is correct
20 Correct 26 ms 24312 KB Output is correct
21 Correct 27 ms 24312 KB Output is correct
22 Correct 27 ms 24224 KB Output is correct
23 Correct 26 ms 24312 KB Output is correct
24 Correct 244 ms 41268 KB Output is correct
25 Correct 326 ms 50364 KB Output is correct
26 Correct 253 ms 41084 KB Output is correct
27 Correct 350 ms 55084 KB Output is correct
28 Correct 311 ms 42088 KB Output is correct
29 Correct 207 ms 41060 KB Output is correct
30 Correct 518 ms 43768 KB Output is correct
31 Correct 163 ms 38924 KB Output is correct
32 Correct 120 ms 31144 KB Output is correct
33 Correct 378 ms 42604 KB Output is correct
34 Correct 448 ms 46224 KB Output is correct
35 Correct 458 ms 41728 KB Output is correct
36 Correct 446 ms 41716 KB Output is correct
37 Correct 295 ms 41556 KB Output is correct
38 Correct 388 ms 55960 KB Output is correct
39 Correct 455 ms 54776 KB Output is correct
40 Correct 277 ms 45380 KB Output is correct
41 Correct 23 ms 24056 KB Output is correct
42 Correct 566 ms 44160 KB Output is correct
43 Correct 454 ms 42316 KB Output is correct
44 Correct 521 ms 46592 KB Output is correct
45 Correct 499 ms 43612 KB Output is correct

Subtask #6
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 24056 KB Output is correct
2 Correct 28 ms 24056 KB Output is correct
3 Correct 23 ms 24056 KB Output is correct
4 Correct 23 ms 24184 KB Output is correct
5 Correct 23 ms 24056 KB Output is correct
6 Correct 23 ms 24024 KB Output is correct
7 Correct 23 ms 24056 KB Output is correct
8 Correct 23 ms 24056 KB Output is correct
9 Correct 23 ms 24056 KB Output is correct
10 Correct 23 ms 24056 KB Output is correct
11 Correct 23 ms 24056 KB Output is correct
12 Correct 23 ms 24056 KB Output is correct
13 Correct 23 ms 24060 KB Output is correct
14 Correct 23 ms 24056 KB Output is correct
15 Correct 24 ms 24056 KB Output is correct
16 Correct 23 ms 24028 KB Output is correct
17 Correct 25 ms 24312 KB Output is correct
18 Correct 25 ms 24444 KB Output is correct
19 Correct 26 ms 24312 KB Output is correct
20 Correct 26 ms 24312 KB Output is correct
21 Correct 27 ms 24312 KB Output is correct
22 Correct 27 ms 24224 KB Output is correct
23 Correct 26 ms 24312 KB Output is correct
24 Correct 244 ms 41268 KB Output is correct
25 Correct 326 ms 50364 KB Output is correct
26 Correct 253 ms 41084 KB Output is correct
27 Correct 350 ms 55084 KB Output is correct
28 Correct 311 ms 42088 KB Output is correct
29 Correct 207 ms 41060 KB Output is correct
30 Correct 518 ms 43768 KB Output is correct
31 Correct 163 ms 38924 KB Output is correct
32 Correct 120 ms 31144 KB Output is correct
33 Correct 378 ms 42604 KB Output is correct
34 Correct 448 ms 46224 KB Output is correct
35 Correct 458 ms 41728 KB Output is correct
36 Correct 446 ms 41716 KB Output is correct
37 Correct 295 ms 41556 KB Output is correct
38 Correct 388 ms 55960 KB Output is correct
39 Correct 455 ms 54776 KB Output is correct
40 Correct 277 ms 45380 KB Output is correct
41 Correct 23 ms 24056 KB Output is correct
42 Correct 566 ms 44160 KB Output is correct
43 Correct 454 ms 42316 KB Output is correct
44 Correct 521 ms 46592 KB Output is correct
45 Correct 499 ms 43612 KB Output is correct
46 Correct 1413 ms 89716 KB Output is correct
47 Correct 1981 ms 159732 KB Output is correct
48 Correct 2577 ms 159704 KB Output is correct
49 Correct 1289 ms 112888 KB Output is correct
50 Correct 3369 ms 102944 KB Output is correct
51 Correct 2322 ms 95932 KB Output is correct
52 Correct 2863 ms 112432 KB Output is correct
53 Correct 2983 ms 103892 KB Output is correct

Subtask #7
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 341 ms 52600 KB Output is correct
2 Correct 296 ms 44192 KB Output is correct
3 Correct 244 ms 41060 KB Output is correct
4 Correct 348 ms 49152 KB Output is correct
5 Correct 23 ms 24056 KB Output is correct
6 Correct 305 ms 42372 KB Output is correct
7 Correct 133 ms 35684 KB Output is correct
8 Correct 127 ms 32632 KB Output is correct
9 Correct 252 ms 40376 KB Output is correct
10 Correct 259 ms 45516 KB Output is correct
11 Correct 183 ms 41064 KB Output is correct
12 Correct 23 ms 24056 KB Output is correct
13 Correct 28 ms 24056 KB Output is correct
14 Correct 23 ms 24056 KB Output is correct
15 Correct 23 ms 24184 KB Output is correct
16 Correct 23 ms 24056 KB Output is correct
17 Correct 23 ms 24024 KB Output is correct
18 Correct 23 ms 24056 KB Output is correct
19 Correct 23 ms 24056 KB Output is correct
20 Correct 23 ms 24056 KB Output is correct
21 Correct 23 ms 24056 KB Output is correct
22 Correct 23 ms 24056 KB Output is correct
23 Correct 23 ms 24056 KB Output is correct
24 Correct 23 ms 24060 KB Output is correct
25 Correct 23 ms 24056 KB Output is correct
26 Correct 24 ms 24056 KB Output is correct
27 Correct 23 ms 24028 KB Output is correct
28 Correct 25 ms 24312 KB Output is correct
29 Correct 25 ms 24444 KB Output is correct
30 Correct 26 ms 24312 KB Output is correct
31 Correct 26 ms 24312 KB Output is correct
32 Correct 27 ms 24312 KB Output is correct
33 Correct 27 ms 24224 KB Output is correct
34 Correct 26 ms 24312 KB Output is correct
35 Correct 244 ms 41268 KB Output is correct
36 Correct 326 ms 50364 KB Output is correct
37 Correct 253 ms 41084 KB Output is correct
38 Correct 350 ms 55084 KB Output is correct
39 Correct 311 ms 42088 KB Output is correct
40 Correct 207 ms 41060 KB Output is correct
41 Correct 518 ms 43768 KB Output is correct
42 Correct 163 ms 38924 KB Output is correct
43 Correct 120 ms 31144 KB Output is correct
44 Correct 378 ms 42604 KB Output is correct
45 Correct 448 ms 46224 KB Output is correct
46 Correct 458 ms 41728 KB Output is correct
47 Correct 446 ms 41716 KB Output is correct
48 Correct 295 ms 41556 KB Output is correct
49 Correct 388 ms 55960 KB Output is correct
50 Correct 455 ms 54776 KB Output is correct
51 Correct 277 ms 45380 KB Output is correct
52 Correct 23 ms 24056 KB Output is correct
53 Correct 566 ms 44160 KB Output is correct
54 Correct 454 ms 42316 KB Output is correct
55 Correct 521 ms 46592 KB Output is correct
56 Correct 499 ms 43612 KB Output is correct
57 Correct 418 ms 50608 KB Output is correct
58 Correct 461 ms 54544 KB Output is correct
59 Correct 314 ms 44280 KB Output is correct
60 Correct 463 ms 62712 KB Output is correct
61 Correct 419 ms 50044 KB Output is correct
62 Correct 22 ms 24184 KB Output is correct
63 Correct 603 ms 53448 KB Output is correct
64 Correct 425 ms 51564 KB Output is correct
65 Correct 520 ms 52800 KB Output is correct
66 Correct 528 ms 46996 KB Output is correct

Subtask #8
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 341 ms 52600 KB Output is correct
2 Correct 296 ms 44192 KB Output is correct
3 Correct 244 ms 41060 KB Output is correct
4 Correct 348 ms 49152 KB Output is correct
5 Correct 23 ms 24056 KB Output is correct
6 Correct 305 ms 42372 KB Output is correct
7 Correct 133 ms 35684 KB Output is correct
8 Correct 127 ms 32632 KB Output is correct
9 Correct 252 ms 40376 KB Output is correct
10 Correct 259 ms 45516 KB Output is correct
11 Correct 183 ms 41064 KB Output is correct
12 Correct 23 ms 24056 KB Output is correct
13 Correct 28 ms 24056 KB Output is correct
14 Correct 23 ms 24056 KB Output is correct
15 Correct 23 ms 24184 KB Output is correct
16 Correct 23 ms 24056 KB Output is correct
17 Correct 23 ms 24024 KB Output is correct
18 Correct 23 ms 24056 KB Output is correct
19 Correct 23 ms 24056 KB Output is correct
20 Correct 23 ms 24056 KB Output is correct
21 Correct 23 ms 24056 KB Output is correct
22 Correct 23 ms 24056 KB Output is correct
23 Correct 23 ms 24056 KB Output is correct
24 Correct 23 ms 24060 KB Output is correct
25 Correct 23 ms 24056 KB Output is correct
26 Correct 24 ms 24056 KB Output is correct
27 Correct 23 ms 24028 KB Output is correct
28 Correct 25 ms 24312 KB Output is correct
29 Correct 25 ms 24444 KB Output is correct
30 Correct 26 ms 24312 KB Output is correct
31 Correct 26 ms 24312 KB Output is correct
32 Correct 27 ms 24312 KB Output is correct
33 Correct 27 ms 24224 KB Output is correct
34 Correct 26 ms 24312 KB Output is correct
35 Correct 244 ms 41268 KB Output is correct
36 Correct 326 ms 50364 KB Output is correct
37 Correct 253 ms 41084 KB Output is correct
38 Correct 350 ms 55084 KB Output is correct
39 Correct 311 ms 42088 KB Output is correct
40 Correct 207 ms 41060 KB Output is correct
41 Correct 518 ms 43768 KB Output is correct
42 Correct 163 ms 38924 KB Output is correct
43 Correct 120 ms 31144 KB Output is correct
44 Correct 378 ms 42604 KB Output is correct
45 Correct 448 ms 46224 KB Output is correct
46 Correct 458 ms 41728 KB Output is correct
47 Correct 446 ms 41716 KB Output is correct
48 Correct 295 ms 41556 KB Output is correct
49 Correct 388 ms 55960 KB Output is correct
50 Correct 455 ms 54776 KB Output is correct
51 Correct 277 ms 45380 KB Output is correct
52 Correct 23 ms 24056 KB Output is correct
53 Correct 566 ms 44160 KB Output is correct
54 Correct 454 ms 42316 KB Output is correct
55 Correct 521 ms 46592 KB Output is correct
56 Correct 499 ms 43612 KB Output is correct
57 Correct 1413 ms 89716 KB Output is correct
58 Correct 1981 ms 159732 KB Output is correct
59 Correct 2577 ms 159704 KB Output is correct
60 Correct 1289 ms 112888 KB Output is correct
61 Correct 3369 ms 102944 KB Output is correct
62 Correct 2322 ms 95932 KB Output is correct
63 Correct 2863 ms 112432 KB Output is correct
64 Correct 2983 ms 103892 KB Output is correct
65 Correct 418 ms 50608 KB Output is correct
66 Correct 461 ms 54544 KB Output is correct
67 Correct 314 ms 44280 KB Output is correct
68 Correct 463 ms 62712 KB Output is correct
69 Correct 419 ms 50044 KB Output is correct
70 Correct 22 ms 24184 KB Output is correct
71 Correct 603 ms 53448 KB Output is correct
72 Correct 425 ms 51564 KB Output is correct
73 Correct 520 ms 52800 KB Output is correct
74 Correct 528 ms 46996 KB Output is correct
75 Correct 2395 ms 136096 KB Output is correct
76 Correct 2432 ms 159696 KB Output is correct
77 Correct 1502 ms 112408 KB Output is correct
78 Correct 2673 ms 159340 KB Output is correct
79 Correct 3516 ms 102748 KB Output is correct
80 Correct 2287 ms 95068 KB Output is correct
81 Correct 2794 ms 100616 KB Output is correct
82 Correct 3046 ms 109604 KB Output is correct
83 Correct 3218 ms 102104 KB Output is correct