AOJ 2317 Class Representative Witch
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2317
二分探索。場合分けを冷静にしてオーバーフローに気をつける
import std.stdio; import std.string; import std.conv; import std.algorithm; import std.range; import std.typecons; int abs(int a){ if(a<0) return -a; return a; } //valを超えない最大のvec[i]を求めiを返す int search(int[] vec, int val){ int l = 0, h = to!int(vec.length); while(true){ if(l+1 == h) break; int m = (l+h)/2; if(vec[m]<=val){ l = m; }else{ h = m; } } return l; } void main(){ int[] input = array(map!(to!int)(split(readln()))); int N=input[0],M=input[1]; int[] p = new int[M+2]; Tuple!(int,int)[] xs; foreach(i; 0..N){ input = array(map!(to!int)(split(readln()))); xs ~= tuple(input[0],input[1]); } p[0] = 0; p[M+1] = 1234567890; foreach(i; 1..M+1){ p[i] = to!int(chomp(readln())); } sort(p); int[] q = new int[M+2]; int[] r = new int[M+2]; q[0] = 0; r[0] = p[0]; for(int i = 1; i < M+2; i++){ if(i%2==0){ q[i] = q[i-1] + p[i]-p[i-1]; r[i] = r[i-1]; }else{ r[i] = r[i-1] + p[i]-p[i-1]; q[i] = q[i-1]; } } //writeln(p); //writeln(q); //writeln(r); ulong ans = 0; foreach(i; 0..N){ int s = xs[i][0]; int t = xs[i][1]; int si = search(p,s); int ti = search(p,t); int w = abs(s-t); if(s < t){ if(si%2 == 0){ if(ti%2 == 0){ w -= q[ti] - q[si]; }else{ w -= q[ti] - q[si] + t - p[ti]; } }else{ if(ti%2 == 1){ w -= r[ti] - r[si]; }else{ w -= r[ti] - r[si] + t - p[ti]; } } }else{ if(si%2 == 0){ if(ti%2 == 0){ w -= q[si] - q[ti]; }else{ w -= q[si] - q[ti] - t + p[ti]; } }else{ if(ti%2 == 1){ w -= r[si] - r[ti]; }else{ w -= r[si] - r[ti] - t + p[ti]; } } } //writeln("s=",s," t=",t," si=",si," ti=",ti," w=",w); ans += w; } writeln(ans); }