Submission #12978

#	Time	Username	Problem	Language	Result	Execution time	Memory
12978		ainta	코알라 (JOI13_koala)	C++98	100 / 100	200 ms	64700 KiB

koala

#include<stdio.h>
#include<algorithm>
using namespace std;
#define INF 1999999999999999999LL
int D, A, n;
struct SegTree{
	long long M;
	SegTree *c1, *c2;
	SegTree(){
		M = -INF;
		c1 = NULL; c2 = NULL;
	}
	void spread(){
		c1->M = max(c1->M, M);
		c2->M = max(c2->M, M);
	}
	void Ins(int b, int e, int s, int l, long long x){
		if (b == s && e == l){
			M = max(M, x);
			return;
		}
		if (!c1){
			c1 = new SegTree();
			c2 = new SegTree();
		}
		spread();
		int m = (b + e) >> 1;
		if (s <= m)c1->Ins(b, m, s, min(m, l), x);
		if (l > m)c2->Ins(m + 1, e, max(s, m + 1), l, x);
	}
	long long Calc(int b, int e, int x){
		if (b == e)return M;
		if (!c1){
			c1 = new SegTree();
			c2 = new SegTree();
		}
		spread();
		int m = (b + e) >> 1;
		if (x <= m)return c1->Calc(b, m, x);
		else return c2->Calc(m + 1, e, x);
	}
};
SegTree *root;
long long Gap(int a){
	return (long long)(a / D)*A;
}
void Ins2(int a, long long x){
	root->Ins(0, D - 1, 0, a%D, x);
	if (a%D + 1 != D)root->Ins(0, D - 1, a%D + 1, D - 1, x - A);
}
int main()
{
	root = new SegTree();
	int ss, ee, i, x, b;
	scanf("%d%d%d%d%d", &ss, &ee, &D, &A, &n);
	Ins2(ss, Gap(ss));
	for (i = 1; i <= n; i++){
		scanf("%d%d", &x,&b);
		Ins2(x, root->Calc(0, D - 1, x%D) + b);
	}
	printf("%lld\n", root->Calc(0, D - 1, ee%D) - Gap(ee));
}

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