Submission #123399

#	Time	Username	Problem	Language	Result	Execution time	Memory
123399		sebinkim	Two Dishes (JOI19_dishes)	C++14	74 / 100	3702 ms	166724 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], 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++){
		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(S[i] == 0) F.addval(0, P2[i]);
		else if(S[i] > m) F.addval(0, P1[i]);
		else{
			query(0, S[i] - 1, P1[i]);
			query(1, S[i], P2[i]);
		}
		
		if(!X.empty() && *X.begin() == 0 && *prev(X.end()) > m) for(; ; );
	}
	
	printf("%lld\n", F.getval(m) + ans);
	
	return 0;
}

Compilation message (stderr)

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