Submission #4926

#	Time	Username	Problem	Language	Result	Execution time	Memory
4926		Qwaz	막대기 (KOI13_game)	C++98	100 / 100	108 ms	13368 KiB

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 / 11
• Subtask 2: 13 / 13
• Subtask 3: 16 / 16
• Subtask 4: 22 / 22
• Subtask 5: 38 / 38