oj.uz

Submission #123510

# Submission time Handle Problem Language Result Execution time Memory
123510 2019-07-01T14:12:25 Z sebinkim Two Dishes (JOI19_dishes) C++14
0 / 100
 370 ms 52144 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);
		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) - 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);
			}
			else{
				Q[t] = 0;
				x = F.getval(t) - F.getval(t - 1);
				if(x <= 0){
					if(X.find(t) != X.end()) X.erase(t);
					query(2, t, - x);
				}
			}
		}
		
		if(S[i] == 0) continue;
		else if(S[i] > m) F.addval(0, P[i]);
		else{
			if(X.find(S[i]) == X.end()) X.insert(S[i]);
			query(0, S[i] - 1, P[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, P + i);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dishes.cpp:86: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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 370 ms 52144 KB Output is correct
2 Incorrect 292 ms 46892 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 24056 KB Output is correct
2 Correct 23 ms 24056 KB Output is correct
3 Correct 23 ms 24060 KB Output is correct
4 Correct 23 ms 24056 KB Output is correct
5 Correct 23 ms 24056 KB Output is correct
6 Correct 24 ms 24056 KB Output is correct
7 Incorrect 23 ms 24056 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 24056 KB Output is correct
2 Correct 23 ms 24056 KB Output is correct
3 Correct 23 ms 24060 KB Output is correct
4 Correct 23 ms 24056 KB Output is correct
5 Correct 23 ms 24056 KB Output is correct
6 Correct 24 ms 24056 KB Output is correct
7 Incorrect 23 ms 24056 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 24056 KB Output is correct
2 Correct 23 ms 24056 KB Output is correct
3 Correct 23 ms 24060 KB Output is correct
4 Correct 23 ms 24056 KB Output is correct
5 Correct 23 ms 24056 KB Output is correct
6 Correct 24 ms 24056 KB Output is correct
7 Incorrect 23 ms 24056 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 24056 KB Output is correct
2 Correct 23 ms 24056 KB Output is correct
3 Correct 23 ms 24060 KB Output is correct
4 Correct 23 ms 24056 KB Output is correct
5 Correct 23 ms 24056 KB Output is correct
6 Correct 24 ms 24056 KB Output is correct
7 Incorrect 23 ms 24056 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 24056 KB Output is correct
2 Correct 23 ms 24056 KB Output is correct
3 Correct 23 ms 24060 KB Output is correct
4 Correct 23 ms 24056 KB Output is correct
5 Correct 23 ms 24056 KB Output is correct
6 Correct 24 ms 24056 KB Output is correct
7 Incorrect 23 ms 24056 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #7
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 370 ms 52144 KB Output is correct
2 Incorrect 292 ms 46892 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 370 ms 52144 KB Output is correct
2 Incorrect 292 ms 46892 KB Output isn't correct
3 Halted 0 ms 0 KB -