oj.uz

Submission #24903

# Submission time Handle Problem Language Result Execution time Memory
24903 2017-06-17T05:32:45 Z khsoo01 코알라 (JOI13_koala) C++11
100 / 100
 126 ms 9676 KB 
#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

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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 5496 KB Output is correct
2 Correct 0 ms 5496 KB Output is correct
3 Correct 0 ms 5496 KB Output is correct
4 Correct 0 ms 5496 KB Output is correct
5 Correct 0 ms 5496 KB Output is correct
6 Correct 0 ms 5496 KB Output is correct
7 Correct 0 ms 5496 KB Output is correct
8 Correct 0 ms 5496 KB Output is correct
9 Correct 0 ms 5496 KB Output is correct
10 Correct 0 ms 5496 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 9676 KB Output is correct
2 Correct 49 ms 9676 KB Output is correct
3 Correct 33 ms 7628 KB Output is correct
4 Correct 56 ms 9676 KB Output is correct
5 Correct 49 ms 7628 KB Output is correct
6 Correct 23 ms 7628 KB Output is correct
7 Correct 36 ms 9676 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 9676 KB Output is correct
2 Correct 113 ms 9676 KB Output is correct
3 Correct 96 ms 9676 KB Output is correct
4 Correct 106 ms 9676 KB Output is correct
5 Correct 69 ms 7628 KB Output is correct
6 Correct 46 ms 7628 KB Output is correct