MINROAD spoj VOI2014 – Con duong Tung Truc

#include<stdio.h> #include<vector> #include<algorithm> using namespace std; typedef pair<int,int> ii; int main() { //freopen("test.inp.c","r",stdin); int n,i,j,k,a,b,s[2]={0}; vector<ii> v; scanf("%d%d%d",&n,&a,&b); for(i=0;i<n;++i) { scanf("%d%d",&j,&k); v.push_back(ii(j,k)); } sort(v.begin(),v.end()); j=-1;k=1e9; for(i=0;i<n;++i) { if(i) --s[(v[i-1].second)&1]; while((s[1]<a || s[0]<b) && j<n) ++s[(v[++j].second)&1]; if(j==n) break; k=min(k,v[j].first-v[i].first); } if(k==1e9) printf("-1"); else printf("%d",k); }

const fi='; nmax=300100; type data=longint; var f:text; D:array[0..nmax] of data; id:array[0..nmax] of byte; n,a,b:data; suma,sumb,vt:array[0..nmax+1] of data; procedure docfile; var i,j:data; begin assign(f,fi); reset(f); readln(f,n,a,b); for i:=1 to n do readln(f,d[i],id[i]); close(f); end; procedure sort(l,r: longint); var i,j,x,y: longint; z:byte; begin i:=l; j:=r; x:=d[(l+r) shr 1]; repeat while d[i]<x do inc(i); while x<d[j] do dec(j); if not(i>j) then begin y:=d[i]; d[i]:=d[j]; d[j]:=y; z:=id[i]; id[i]:=id[j]; id[j]:=z; inc(i); j:=j-1; end; until i>j; if l<j then sort(l,j); if i<r then sort(i,r); end; function min(a,b:data):data; begin if a<b then exit(a); exit(b); end; procedure xuli; var i,j,res:data; begin suma[0]:=0; sumb[0]:=0; d[0]:=0; for i:=1 to n do begin if id[i]=1 then begin suma[i]:=1; sumb[i]:=0; end else begin suma[i]:=0; sumb[i]:=1; end; end; for i:=1 to n do begin suma[i]:=suma[i-1]+suma[i]; sumb[i]:=sumb[i-1]+sumb[i]; end; vt[0]:=1; res:=high(data); for i:=1 to n do begin vt[i]:=vt[i-1]; for j:=vt[i-1] to i-1 do if (suma[i]-suma[j-1]>=a) and (sumb[i]-sumb[j-1]>=b) then begin vt[i]:=j; res:=min(res,d[i]-d[j]); end else break; end; if res=high(data) then writeln(-1) else writeln(res); end; begin docfile; sort(1,n); xuli; end.