Submission #4926

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
4926	2014-01-14T09:18:39 Z	Qwaz	막대기 (KOI13_game)	C++	100 / 100	108 ms	13368 KB

game

#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;
typedef long long ll;
typedef pair < int, int > pii;
const int MAX=100020;

int n, gap, xu[MAX], xuFull, xd[MAX], xdFull;
pii data[MAX];

void input(){
	scanf("%d%d", &n, &gap);

	int i;
	for(i=0; i<n; i++){
		scanf("%d%d", &data[i].first, &data[i].second);

		xu[xuFull++] = data[i].first;
		xd[xdFull++] = data[i].second;
	}
}

vector < int > tu[MAX], td[MAX];

int index(int target[], int size, int value){
	return lower_bound(target, target+size, value)-target;
}

void init(){
	sort(xu, xu+xuFull);
	sort(xd, xd+xdFull);

	xuFull = unique(xu, xu+xuFull)-xu;
	xdFull = unique(xd, xd+xdFull)-xd;

	int i;
	for(i=0; i<n; i++){
		int f=index(xu, xuFull, data[i].first), s=index(xd, xdFull, data[i].second);
		tu[f].push_back(s);
		td[s].push_back(f);
	}
}

ll su[MAX], lu[MAX], ld[MAX], res;

void update(ll &target, ll value){
	if(target < value){
		target = value;
		if(res < value)
			res = value;
	}
}

void solve(){
	int i=0, j=0, k;
	while(i < xuFull || j < xdFull){
		if(j == xdFull || (i < xuFull && xu[i] <= xd[j])){
			su[i] = lu[i];
			sort(tu[i].begin(), tu[i].end());
			for(k=0; k<tu[i].size(); k++){
				ll before = ld[tu[i][k]];
				if(xd[tu[i][k]] > xu[i]){
					update(ld[tu[i][k]], lu[i]+xd[tu[i][k]]-xu[i]+gap);
					update(lu[i], before+abs(xd[tu[i][k]]-xu[i])+gap);
				} else if(xd[tu[i][k]] == xu[i])
					update(lu[i], ld[tu[i][k]]+abs(xd[tu[i][k]]-xu[i])+gap);
			}
			i++;
		} else {
			sort(td[j].begin(), td[j].end());
			for(k=0; k<td[j].size(); k++){
				ll before = lu[td[j][k]];
				if(xu[td[j][k]] > xd[j]){
					update(lu[td[j][k]], ld[j]+xu[td[j][k]]-xd[j]+gap);
					update(ld[j], before+abs(xu[td[j][k]]-xd[j])+gap);
				} else if(xu[td[j][k]] == xd[j])
					update(ld[j], su[td[j][k]]+abs(xu[td[j][k]]-xd[j])+gap);
			}
			j++;
		}
	}

	printf("%lld\n", res);
}

int main(){
	input();

	init();
	solve();

	return 0;
}

Subtask #1

11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	9804 KB	Output is correct
2	Correct	4 ms	9804 KB	Output is correct
3	Correct	0 ms	9804 KB	Output is correct
4	Correct	4 ms	9804 KB	Output is correct
5	Correct	4 ms	9804 KB	Output is correct

Subtask #2

13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	32 ms	10464 KB	Output is correct
2	Correct	28 ms	10464 KB	Output is correct
3	Correct	60 ms	10992 KB	Output is correct
4	Correct	60 ms	10992 KB	Output is correct
5	Correct	64 ms	10992 KB	Output is correct

Subtask #3

16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	9804 KB	Output is correct
2	Correct	0 ms	9804 KB	Output is correct
3	Correct	0 ms	9804 KB	Output is correct
4	Correct	0 ms	9804 KB	Output is correct
5	Correct	0 ms	9804 KB	Output is correct

Subtask #4

22.0 / 22.0

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

Subtask #5

38.0 / 38.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	9936 KB	Output is correct
2	Correct	4 ms	10068 KB	Output is correct
3	Correct	40 ms	10892 KB	Output is correct
4	Correct	100 ms	12576 KB	Output is correct
5	Correct	100 ms	12708 KB	Output is correct
6	Correct	88 ms	13208 KB	Output is correct
7	Correct	108 ms	13368 KB	Output is correct
8	Correct	88 ms	13356 KB	Output is correct
9	Correct	12 ms	10068 KB	Output is correct
10	Correct	8 ms	9936 KB	Output is correct
11	Correct	100 ms	12048 KB	Output is correct
12	Correct	100 ms	12048 KB	Output is correct