oj.uz

Submission #18419

# Submission time Handle Problem Language Result Execution time Memory
18419 2016-02-01T06:17:41 Z suhgyuho_william 막대기 (KOI13_game) C++
11 / 100
 121 ms 13320 KB 
#include <stdio.h>
#include <algorithm>

using namespace std;

int N;
long long L;
struct data{
	int num;
	long long x,y;
}a[100002],b[100002];
bool cmpx(data x,data y){
	if(x.x != y.x) return x.x < y.x;
	return x.y < y.y;
}
bool cmpy(data x,data y){
	if(x.y != y.y) return x.y < y.y;
	return x.x < y.x;
}

int where[100002];
long long d[100002][2];
bool check[100002][2];
long long length(int x){
	long long ans;

	ans = a[x].x-a[x].y;
	if(ans < 0) ans = -ans;
	return ans+L;
}
void dfs(int x,int op){
	int left,mid,right;
	int i,v,t;

	if(check[x][op]) return;
	check[x][op] = true;
	v = -1;
	left = 1; right = N;
	if(op == 0){
		while(left <= right){
			mid = (left+right)/2;
			if(a[mid].x == a[x].x){
				if(a[x].y < a[mid].y){
					v = mid;
					right = mid-1;
				}else left = mid+1;
			}else if(a[mid].x > a[x].x) right = mid-1;
			else left = mid+1;
		}
		if(v == -1){ d[x][op] = length(x); return; }
		t = v;
		for(i=t; i<=N; i++){
			if(a[x].x != a[i].x) break;
			dfs(v,1);
			d[x][op] = max(d[v][1]+length(x),d[x][op]);
		}
	}else{
		while(left <= right){
			mid = (left+right)/2;
			if(a[x].y == b[mid].y){
				if(a[x].x < b[mid].x){
					v = mid;
					right = mid-1;
				}else left = mid+1;
			}else if(b[mid].y > a[x].y) right = mid-1;
			else left = mid+1;
		}
		if(v == -1){ d[x][op] = length(x); return; }
		t = v;
		for(i=t; i<=N; i++){
			if(a[x].y != b[i].y) break;
			v = where[b[v].num];
			dfs(v,0);
			d[x][op] = max(d[v][0]+length(x),d[x][op]);
		}
	}
}

int main(){
	int i;
	long long ans = 0;
	//freopen("input.txt","r",stdin);

	scanf("%d %lld",&N,&L);
	for(i=1; i<=N; i++){
		scanf("%lld %lld",&a[i].x,&a[i].y);
		b[i].x = a[i].x;
		b[i].y = a[i].y;
		a[i].num = b[i].num = i;
	}
	sort(a+1,a+N+1,cmpx);
	sort(b+1,b+N+1,cmpy);
	for(i=1; i<=N; i++) where[a[i].num] = i;

	for(i=1; i<=N; i++){
		dfs(i,0);
		dfs(i,1);
		ans = max(ans,d[i][0]);
		ans = max(ans,d[i][1]);
	}
	printf("%lld",ans);

	return 0;
}

Subtask #1
11.0 / 11.0

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

Subtask #2
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 121 ms 13320 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 7924 KB Output is correct
2 Incorrect 0 ms 7924 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 7924 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 38.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 8408 KB Output isn't correct
2 Halted 0 ms 0 KB -