learning

제목 설명
FJ 는 기 존의 소 떼 데이터 로 자동 분류 기 를 만 들 기로 했다.그것 은 소의 몸 에 반점 이 있 는 지 없 는 지 추측 할 수 있다.불 행 히 도 FJ 는 좋 은 데이터 가 없다.그의 N 마리 소 에 대해 그 가 아 는 것 은 소의 무게 와 이 소 에 반점 이 있 는 지 여부 뿐이다.모든 소 는 무게 가 다르다.새로운 소 C 에 반점 이 있 는 지 추측 하기 위해 FJ 는 먼저 기 존 소 떼 와 새 소의 무게 가 가장 가 까 운 소 C 를 찾 았 다.이 소 에 게 반점 이 있다 면 FJ 는 새 소 에 게 도 반점 이 있 을 것 이 라 고 추측 했다.반면 새 소 는 반점 이 없다.소 두 마리 와 새 소의 무게 차이 가 같다 면 그 중 하나 인 소 에 게 반점 이 있다 면 FJ 는 새 소 에 게 도 반점 이 있 을 것 이 라 고 추측 했다.FJ 는 새로 들 어 온 소 들 에 게 이런 테스트 기 를 사용 했다.이 소 들 의 무게 (연속 정수) 는 모두 A 와 B 사이 (A; B 포함) 에 있다.그 중 몇 마리 의 소 가 반점 으로 분 류 될 지 결정 해 주세요.새로운 기 계 는 FJ 기 존의 소 떼 에서 만 데 이 터 를 비교 할 수 있 으 며, 그의 어떤 새로운 소 와 도 비교 하지 않 을 것 이다.그리고 A 와 B 가 모두 클 수 있 기 때문에 당신 의 프로그램 이 A B 에서 하나씩 순환 하면 빨리 달리 지 못 할 수도 있 습 니 다.
입력
첫 줄 세 개 N;A;B. 다음 줄 N 줄 을 이어서 줄 마다 'S W' 이거 나 반점 이 있 는 소 한 마리 의 무 게 는 W 또는 'NS W' 라 는 뜻 입 니 다. 반점 이 없 는 소 한 마리 의 무 게 는 W 데이터 로 임의의 두 마리 의 소의 무게 가 같 지 않다 는 것 을 보증 합 니 다.
출력
얼마나 많은 소 를 수출 하 라 고 하면 반점 이 있 는 것 으로 볼 수 있 습 니까?
샘플 입력
3 1 10 S 10 NS 4 S 1
샘플 출력
6
Explanation
1, 2, 7, 8, 9, 10 에 반점 이 있어 요.
데이터 범위 제한
• 40% 의 데이터 에 대해 1 < = A < = B < = 10 ^ 7.100% 의 데이터 에 대해 N < = 5 * 10 ^ 4, 1 < = A < = B < = 10 ^ 9, 1 < = W < = 10 ^ 9.
생각:
스냅 샷 + 양쪽 MID 판단
...................................................................
코드:

var
        s,o,p,op,l,u,r,d,q:array[0..50000,1..2] of int64;
        f:array[1..50000] of char;
        w1:array[1..50000] of int64;
        c,oc:char;
        n,a,b,w,ow,i,j,k,x,y,z,ls:longint;
        ans:qword;
procedure qs(l,r:longint);
var
        i,j,mid:int64;
        ls1:char;
        ls2:int64;
begin
        i:=l;
        j:=r;
        mid:=w1[(l+r) div 2];
        while i<=j do
        begin
                while w1[j]>mid do
                begin
                        j:=j-1;
                end;
                while w1[i]do
                begin
                        i:=i+1;
                end;
                if i<=j then
                begin
                        ls1:=f[i];
                        ls2:=w1[i];
                        f[i]:=f[j];
                        w1[i]:=w1[j];
                        f[j]:=ls1;
                        w1[j]:=ls2;
                        i:=i+1;
                        j:=j-1;
                end;
        end;
        if ithen qs(i,r);
        if j>l then qs(l,j);
end;
procedure jia(l,r:longint);
begin
        if (l<=a)and(b<=r) then
        begin
                ans:=ans+b-a+1;
        end
        else
        begin
                if (l>=a)and(r<=b) then
                begin
                        ans:=ans+r-l+1;
                end
                else
                begin
                        if (ror(l>b) then
exit;
if (l<=a)and(r<=b) then
begin
ans:=ans+r-a+1;
end
else
begin
ans:=ans+b-l+1;
end;
end;
end;
end;
begin
assign(input,'learning.in');
reset(input);
assign(output,'learning.out');
rewrite(output);
readln(n,a,b);
for i:=1 to n do
begin
read(c);
if c='N' then
begin
readln(c,w);
c:='N';
f[i]:=c;
w1[i]:=w;
end
else
begin
readln(w);
f[i]:=c;
w1[i]:=w;
end;
end;
qs(1,n);
oc:=f[1];
ow:=w1[1];
if (f[1]='S')and(a<=w1[1]) then
begin
jia(a,w1[1]);
end;
for i:=2 to n do
begin
c:=f[i];
if c='N' then
begin
w:=w1[i];
if oc='S' then
begin
s[0,1]:=s[0,1]+1;
s[s[0,1],1]:=ow+1;
s[s[0,1],2]:=ow+(abs(w-ow)+1) div 2 + (abs(w-ow)+1) mod 2 -1;
jia(s[s[0,1],1],s[s[0,1],2]);
end;
end
else
begin
w:=w1[i];
if oc='N' then
begin
s[0,1]:=s[0,1]+1;
s[s[0,1],1]:=ow+(abs(w-ow)+1) div 2;
s[s[0,1],2]:=w;
jia(s[s[0,1],1],s[s[0,1],2]);
end
else
begin
s[0,1]:=s[0,1]+1;
s[s[0,1],1]:=ow+1;
s[s[0,1],2]:=w;
jia(s[s[0,1],1],s[s[0,1],2]);
end;
end;
oc:=c;
ow:=w;
end;
if (f[n]='S')and(b>w1[n]) then
begin
jia(n+1,b);
end;
writeln(ans);
end.