Submission #1161869
Source Code Expand
#include <algorithm>
#include <iostream>
#include <sstream>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cmath>
#include <list>
#include <cassert>
#include <ctime>
#include <climits>
using namespace std;
#define PB push_back
#define MP make_pair
#define SZ(v) ((int)(v).size())
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define FORE(i,a,b) for(int i=(a);i<=(b);++i)
#define REPE(i,n) FORE(i,0,n)
#define FORSZ(i,a,v) FOR(i,a,SZ(v))
#define REPSZ(i,v) REP(i,SZ(v))
typedef long long ll;
typedef unsigned long long ull;
ll gcd(ll a,ll b) { return b==0?a:gcd(b,a%b); }
const int MAXN=100000;
// Train A departs at station i at sum(j=0..i-1,tj+u{j+1})
// Train B arrives at station i at D-sum(j=0..i-1,tj+v{j+1})
// If track i is one way then D-sum(j=0..i-1,tj+v{j+1})<=sum(j=0..i-1,tj+u{j+1}) || D-sum(j=0..i-1,tj+v{j+1})-ti>=sum(j=0..i-1,tj+u{j+1})+ti
// In other words: -sum(j=0..i-1,2*tj)<=sum(j=0..i-1,u{j+1}+v{j+1})-D<=-sum(j=0..i,2*tj)
int ntrack,T;
int t[MAXN];
bool onedir[MAXN];
ll tsum[MAXN+1];
int L[MAXN],R[MAXN],ncond;
int x[2*MAXN],nx;
ll dpL[MAXN],dpR[MAXN];
int sval[4*MAXN];
void spush(int x) { if(sval[x]!=-1) sval[2*x+1]=sval[2*x+2]=sval[x],sval[x]=-1; }
void sset(int x,int l,int r,int L,int R,int VAL) {
//printf("sset(%d,%d..%d,%d..%d,%d)\n",x,l,r,L,R,VAL);
if(L<=l&&r<=R) { sval[x]=VAL; return; }
spush(x);
int m=l+(r-l)/2;
if(L<=m) sset(2*x+1,l,m,L,R,VAL);
if(m+1<=R) sset(2*x+2,m+1,r,L,R,VAL);
}
int sget(int x,int l,int r,int IDX) {
//printf("sget(%d,%d..%d,%d)\n",x,l,r,IDX);
if(sval[x]!=-1||l==r) return sval[x];
spush(x);
int m=l+(r-l)/2;
return IDX<=m?sget(2*x+1,l,m,IDX):sget(2*x+2,m+1,r,IDX);
}
void run() {
scanf("%d%d",&ntrack,&T);
REP(i,ntrack) { int tmp; scanf("%d%d",&t[i],&tmp); onedir[i]=tmp==1; }
REP(i,ntrack) if(onedir[i]&&2*t[i]>T) { printf("-1\n"); return; }
tsum[0]=0; REP(i,ntrack) tsum[i+1]=tsum[i]+t[i];
ncond=0;
REP(i,ntrack) if(onedir[i]) { L[ncond]=-2*tsum[i]%T; R[ncond]=-2*tsum[i+1]%T; if(L[ncond]<0) L[ncond]+=T; if(R[ncond]<0) R[ncond]+=T; ++ncond; }
nx=0; REP(i,ncond) x[nx++]=L[i],x[nx++]=R[i]; sort(x,x+nx); nx=unique(x,x+nx)-x; REP(i,ncond) L[i]=lower_bound(x,x+nx,L[i])-x,R[i]=lower_bound(x,x+nx,R[i])-x;
memset(sval,-1,sizeof(sval));
for(int i=ncond-1;i>=0;--i) {
int lj=sget(0,0,nx-1,L[i]);
dpL[i]=lj==-1?0:(x[L[lj]]-x[L[i]]+T)%T+dpL[lj];
int rj=sget(0,0,nx-1,R[i]);
dpR[i]=rj==-1?0:(x[L[rj]]-x[R[i]]+T)%T+dpL[rj];
//printf("%d: %d..%d (%d..%d) -> %d,%d -> %lld,%lld\n",i,L[i],R[i],x[L[i]],x[R[i]],lj,rj,dpL[i],dpR[i]);
if(L[i]<=R[i]) {
if(L[i]>=1) sset(0,0,nx-1,0,L[i]-1,i);
if(nx-R[i]>=2) sset(0,0,nx-1,R[i]+1,nx-1,i);
} else {
if(L[i]-R[i]>=2) sset(0,0,nx-1,R[i]+1,L[i]-1,i);
}
}
ll ret=LLONG_MAX;
REP(i,nx) {
int j=sget(0,0,nx-1,i);
ll cur=j==-1?0:(x[L[j]]-x[i]+T)%T+dpL[j];
//printf("%d (%d) -> %d -> %lld\n",i,x[i],j,cur);
if(cur<ret) ret=cur;
}
ret+=2*tsum[ntrack];
printf("%lld\n",ret);
}
int main() {
run();
return 0;
}
Submission Info
Submission Time
2017-03-14 21:54:25+0900
Task
F - Train Service Planning
User
krijgertje
Language
C++14 (GCC 5.4.1)
Score
1700
Code Size
3263 Byte
Status
AC
Exec Time
94 ms
Memory
6144 KB
Compile Error
./Main.cpp: In function ‘void run()’:
./Main.cpp:69:26: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&ntrack,&T);
^
./Main.cpp:70:51: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
REP(i,ntrack) { int tmp; scanf("%d%d",&t[i],&tmp); onedir[i]=tmp==1; }
^
Judge Result
Set Name
Sample
All
subtask
subtask2
Score / Max Score
0 / 0
700 / 700
500 / 500
500 / 500
Status
Set Name
Test Cases
Sample
sample1.txt, sample2.txt, sample3.txt, sample4.txt
All
sample1.txt, sample2.txt, sample3.txt, sample4.txt, in1.txt, in10.txt, in101.txt, in102.txt, in103.txt, in104.txt, in105.txt, in106.txt, in107.txt, in108.txt, in109.txt, in11.txt, in110.txt, in12.txt, in13.txt, in14.txt, in15.txt, in16.txt, in17.txt, in18.txt, in19.txt, in2.txt, in20.txt, in21.txt, in22.txt, in23.txt, in24.txt, in25.txt, in26.txt, in27.txt, in28.txt, in3.txt, in4.txt, in5.txt, in6.txt, in7.txt, in8.txt, in9.txt, sample1.txt, sample2.txt, sample3.txt, sample4.txt, sub2in1.txt, sub2in10.txt, sub2in11.txt, sub2in12.txt, sub2in13.txt, sub2in14.txt, sub2in15.txt, sub2in16.txt, sub2in17.txt, sub2in18.txt, sub2in19.txt, sub2in2.txt, sub2in20.txt, sub2in21.txt, sub2in22.txt, sub2in23.txt, sub2in24.txt, sub2in3.txt, sub2in4.txt, sub2in5.txt, sub2in6.txt, sub2in7.txt, sub2in8.txt, sub2in9.txt, subin1.txt, subin10.txt, subin101.txt, subin102.txt, subin103.txt, subin104.txt, subin105.txt, subin106.txt, subin107.txt, subin108.txt, subin109.txt, subin11.txt, subin12.txt, subin13.txt, subin14.txt, subin15.txt, subin16.txt, subin17.txt, subin18.txt, subin19.txt, subin2.txt, subin20.txt, subin201.txt, subin21.txt, subin22.txt, subin23.txt, subin24.txt, subin3.txt, subin4.txt, subin5.txt, subin6.txt, subin7.txt, subin8.txt, subin9.txt
subtask
sample1.txt, sample2.txt, sample3.txt, subin1.txt, subin10.txt, subin101.txt, subin102.txt, subin103.txt, subin104.txt, subin105.txt, subin106.txt, subin107.txt, subin108.txt, subin109.txt, subin11.txt, subin12.txt, subin13.txt, subin14.txt, subin15.txt, subin16.txt, subin17.txt, subin18.txt, subin19.txt, subin2.txt, subin20.txt, subin201.txt, subin21.txt, subin22.txt, subin23.txt, subin24.txt, subin3.txt, subin4.txt, subin5.txt, subin6.txt, subin7.txt, subin8.txt, subin9.txt
subtask2
sample1.txt, sample2.txt, sample3.txt, sample4.txt, sub2in1.txt, sub2in10.txt, sub2in11.txt, sub2in12.txt, sub2in13.txt, sub2in14.txt, sub2in15.txt, sub2in16.txt, sub2in17.txt, sub2in18.txt, sub2in19.txt, sub2in2.txt, sub2in20.txt, sub2in21.txt, sub2in22.txt, sub2in23.txt, sub2in24.txt, sub2in3.txt, sub2in4.txt, sub2in5.txt, sub2in6.txt, sub2in7.txt, sub2in8.txt, sub2in9.txt
Case Name
Status
Exec Time
Memory
in1.txt
AC
3 ms
3840 KB
in10.txt
AC
55 ms
5760 KB
in101.txt
AC
43 ms
5760 KB
in102.txt
AC
42 ms
5760 KB
in103.txt
AC
43 ms
5760 KB
in104.txt
AC
43 ms
5760 KB
in105.txt
AC
38 ms
5760 KB
in106.txt
AC
43 ms
5760 KB
in107.txt
AC
42 ms
5760 KB
in108.txt
AC
43 ms
5760 KB
in109.txt
AC
43 ms
5760 KB
in11.txt
AC
56 ms
5760 KB
in110.txt
AC
38 ms
5760 KB
in12.txt
AC
55 ms
5760 KB
in13.txt
AC
53 ms
5760 KB
in14.txt
AC
55 ms
5760 KB
in15.txt
AC
54 ms
5760 KB
in16.txt
AC
55 ms
5760 KB
in17.txt
AC
55 ms
5760 KB
in18.txt
AC
55 ms
5760 KB
in19.txt
AC
54 ms
5760 KB
in2.txt
AC
56 ms
5760 KB
in20.txt
AC
54 ms
5760 KB
in21.txt
AC
49 ms
5760 KB
in22.txt
AC
46 ms
5760 KB
in23.txt
AC
51 ms
5760 KB
in24.txt
AC
52 ms
5760 KB
in25.txt
AC
26 ms
5760 KB
in26.txt
AC
26 ms
5760 KB
in27.txt
AC
25 ms
5760 KB
in28.txt
AC
27 ms
5760 KB
in3.txt
AC
55 ms
5760 KB
in4.txt
AC
56 ms
5760 KB
in5.txt
AC
47 ms
5504 KB
in6.txt
AC
55 ms
5760 KB
in7.txt
AC
54 ms
5760 KB
in8.txt
AC
18 ms
768 KB
in9.txt
AC
56 ms
5760 KB
sample1.txt
AC
2 ms
3840 KB
sample2.txt
AC
1 ms
256 KB
sample3.txt
AC
2 ms
3840 KB
sample4.txt
AC
2 ms
3840 KB
sub2in1.txt
AC
2 ms
3840 KB
sub2in10.txt
AC
2 ms
3840 KB
sub2in11.txt
AC
2 ms
3840 KB
sub2in12.txt
AC
2 ms
3840 KB
sub2in13.txt
AC
2 ms
3840 KB
sub2in14.txt
AC
2 ms
3840 KB
sub2in15.txt
AC
2 ms
3840 KB
sub2in16.txt
AC
2 ms
3840 KB
sub2in17.txt
AC
2 ms
3840 KB
sub2in18.txt
AC
2 ms
3840 KB
sub2in19.txt
AC
2 ms
3840 KB
sub2in2.txt
AC
2 ms
3840 KB
sub2in20.txt
AC
2 ms
3840 KB
sub2in21.txt
AC
2 ms
3840 KB
sub2in22.txt
AC
2 ms
3840 KB
sub2in23.txt
AC
2 ms
3840 KB
sub2in24.txt
AC
2 ms
3840 KB
sub2in3.txt
AC
2 ms
3840 KB
sub2in4.txt
AC
2 ms
3840 KB
sub2in5.txt
AC
2 ms
3840 KB
sub2in6.txt
AC
2 ms
3840 KB
sub2in7.txt
AC
1 ms
256 KB
sub2in8.txt
AC
2 ms
3840 KB
sub2in9.txt
AC
2 ms
3840 KB
subin1.txt
AC
93 ms
6144 KB
subin10.txt
AC
92 ms
6144 KB
subin101.txt
AC
77 ms
6144 KB
subin102.txt
AC
60 ms
6144 KB
subin103.txt
AC
56 ms
6144 KB
subin104.txt
AC
56 ms
6144 KB
subin105.txt
AC
37 ms
6144 KB
subin106.txt
AC
45 ms
6144 KB
subin107.txt
AC
59 ms
6144 KB
subin108.txt
AC
68 ms
6144 KB
subin109.txt
AC
58 ms
6144 KB
subin11.txt
AC
89 ms
6144 KB
subin12.txt
AC
91 ms
6144 KB
subin13.txt
AC
91 ms
6144 KB
subin14.txt
AC
92 ms
6144 KB
subin15.txt
AC
91 ms
6144 KB
subin16.txt
AC
91 ms
6144 KB
subin17.txt
AC
86 ms
6144 KB
subin18.txt
AC
89 ms
6144 KB
subin19.txt
AC
89 ms
6144 KB
subin2.txt
AC
91 ms
6144 KB
subin20.txt
AC
90 ms
6144 KB
subin201.txt
AC
2 ms
3840 KB
subin21.txt
AC
31 ms
6144 KB
subin22.txt
AC
31 ms
6144 KB
subin23.txt
AC
32 ms
6144 KB
subin24.txt
AC
32 ms
6144 KB
subin3.txt
AC
94 ms
6144 KB
subin4.txt
AC
79 ms
5888 KB
subin5.txt
AC
91 ms
6144 KB
subin6.txt
AC
69 ms
6144 KB
subin7.txt
AC
17 ms
768 KB
subin8.txt
AC
16 ms
768 KB
subin9.txt
AC
93 ms
6144 KB