oj.uz

Submission #12978

# Submission time Handle Problem Language Result Execution time Memory
12978 2015-01-23T01:19:09 Z ainta 코알라 (JOI13_koala) C++
100 / 100
 200 ms 64700 KB 
#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.0 / 20.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 1208 KB Output is correct
2 Correct 48 ms 1208 KB Output is correct
3 Correct 24 ms 1208 KB Output is correct
4 Correct 40 ms 1208 KB Output is correct
5 Correct 28 ms 1208 KB Output is correct
6 Correct 16 ms 1208 KB Output is correct
7 Correct 36 ms 1208 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 7016 KB Output is correct
2 Correct 156 ms 23252 KB Output is correct
3 Correct 184 ms 43844 KB Output is correct
4 Correct 200 ms 64700 KB Output is correct
5 Correct 92 ms 13880 KB Output is correct
6 Correct 60 ms 7544 KB Output is correct