Submission #24903

#	Time	Username	Problem	Language	Result	Execution time	Memory
24903		khsoo01	코알라 (JOI13_koala)	C++11	100 / 100	126 ms	9676 KiB

koala

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf = 1e18;

ll s, e, d, c, n;

vector<ll> mod;
vector<pair<ll,ll> > a;

struct segtree {
	ll val[444444], lim;
	void init () {
		for(lim=1;lim<=mod.size();lim<<=1);
		for(ll i=2*lim;--i;) val[i] = -inf;
	}
	void update (ll P, ll V) {
		P += lim;
		while(P) {
			val[P] = max(val[P], V);
			P >>= 1;
		}
	}
	ll query (ll S, ll E) {
		ll ret = -inf;
		S += lim; E += lim;
		while(S<=E) {
			if(S%2 == 1) {ret = max(ret, val[S]); S++;}
			if(E%2 == 0) {ret = max(ret, val[E]); E--;}
			S >>= 1; E >>= 1;
		}
		return ret;
	}
} seg;

ll compr (ll X) {
	return lower_bound(mod.begin(), mod.end(), X) - mod.begin();
}

ll getval (ll X) {
	ll M = compr(X%d);
	return max(seg.query(0, M-1)-c, seg.query(M, mod.size()-1)) - X/d*c;
}

void update (ll P, ll V) {
	ll M = compr(P%d);
	seg.update(M, V + P/d*c);
}

int main()
{
	scanf("%lld%lld%lld%lld%lld",&s,&e,&d,&c,&n);
	for(ll i=0;i<n;i++) {
		ll A, B;
		scanf("%lld%lld",&A,&B);
		a.push_back({A, B});
		mod.push_back(A%d);
	}
	mod.push_back(s%d);
	mod.push_back(e%d);
	sort(mod.begin(), mod.end());
	mod.erase(unique(mod.begin(), mod.end()), mod.end());
	seg.init();
	update(s, 0);
	for(auto &T : a) {
		ll A, B; tie(A, B) = T;
		update(A, getval(A) + B);
	}
	printf("%lld\n",getval(e));
}

Compilation message (stderr)

koala.cpp: In member function 'void segtree::init()':
koala.cpp:14:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(lim=1;lim<=mod.size();lim<<=1);
                ^
koala.cpp: In function 'int main()':
koala.cpp:52:46: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld%lld%lld%lld",&s,&e,&d,&c,&n);
                                              ^
koala.cpp:55:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld",&A,&B);
                          ^

• Subtask 1: 20 / 20
• Subtask 2: 30 / 30
• Subtask 3: 50 / 50