Submission #123523

#	Time	Username	Problem	Language	Result	Execution time	Memory
123523		sebinkim	Two Dishes (JOI19_dishes)	C++14	100 / 100	3516 ms	159732 KiB

dishes

#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 (stderr)

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 / 5
• Subtask 2: 3 / 3
• Subtask 3: 7 / 7
• Subtask 4: 39 / 39
• Subtask 5: 11 / 11
• Subtask 6: 9 / 9
• Subtask 7: 17 / 17
• Subtask 8: 9 / 9