Submission #1678023
Source Code Expand
#include<bits/stdc++.h>
#define N 400005
#define LL long long
#define L(__) (__ << 1)
#define R(__) (L(__)|1)
#define INF (1LL<<60)
using namespace std;
LL A[4*N],T[4*N],ans=INF;
int n,k,l[N],r[N],w[N],lw,a[N],b[N];
void B(int t,int l,int r)
{
int mid=(l+r)>>1; T[t]=-INF;
if(l==r){ A[t]=-w[l]; return ;}
B(L(t),l,mid);
B(R(t),mid+1,r);
A[t]=min(A[L(t)],A[R(t)]);
}
void TA(int t,LL x){ T[t]=A[t]=x;}
void push(int t)
{
if(T[t]==-INF) return ;
TA(L(t),T[t]),TA(R(t),T[t]);
T[t]=-INF;
}
void M(int t,int l,int r,int l1,int r1,LL x)
{
int mid=(l+r)>>1;
if(l>r1||r<l1||l>r) return ;
if(l>=l1&&r<=r1) return TA(t,x);
push(t);
M(L(t),l,mid,l1,r1,x);
M(R(t),mid+1,r,l1,r1,x);
A[t]=min(A[L(t)],A[R(t)]);
}
LL Q(int t,int l,int r,int l1,int r1)
{
int mid=(l+r)>>1; LL z=INF;
if(l>r1||r<l1||l>r) return INF;
if(l>=l1&&r<=r1) return A[t];
push(t);
z=min(z,Q(L(t),l,mid,l1,r1));
z=min(z,Q(R(t),mid+1,r,l1,r1));
A[t]=min(A[L(t)],A[R(t)]);
return z;
}
int main()
{
int i,p; LL z,e;
scanf("%d %d",&n,&k),p=0;
for(i=1;i<=n;i++){
scanf("%d %d",&a[i],&b[i]);
if(2*a[i]>k&&b[i]==1){ printf("-1"); exit(0);}
if(b[i]==2) l[i]=k-1,r[i]=0;
else r[i]=p,l[i]=(p-2*a[i]%k+k)%k;
p=(p-2*a[i]%k+k)%k;
}
for(i=1;i<=n;i++) w[++lw]=l[i],w[++lw]=r[i];
sort(w+1,w+lw+1);
lw=unique(w+1,w+lw+1)-w-1;
for(i=1;i<=n;i++){
l[i]=lower_bound(w+1,w+lw+1,l[i])-w;
r[i]=lower_bound(w+1,w+lw+1,r[i])-w;
}
B(1,1,lw);
for(i=1;i<=n;i++){
if(l[i]<r[i]){
z=Q(1,1,lw,l[i]+1,r[i]-1);
M(1,1,lw,l[i]+1,r[i]-1,INF);
e=Q(1,1,lw,r[i],r[i]);
if(z<e) M(1,1,lw,r[i],r[i],z);
}
else{
z=Q(1,1,lw,l[i]+1,lw);
M(1,1,lw,l[i]+1,lw,INF);
z=min(z+k,Q(1,1,lw,1,r[i]-1));
M(1,1,lw,1,r[i]-1,INF);
e=Q(1,1,lw,r[i],r[i]);
if(z<e) M(1,1,lw,r[i],r[i],z);
}
}
for(i=1;i<=lw;i++)
ans=min(ans,Q(1,1,lw,i,i)+w[i]);
for(i=1;i<=n;i++) ans+=a[i]*2;
cout<<ans;
return 0;
}
Submission Info
Submission Time |
|
Task |
F - Train Service Planning |
User |
MemorySlices |
Language |
C++14 (GCC 5.4.1) |
Score |
1700 |
Code Size |
1980 Byte |
Status |
AC |
Exec Time |
207 ms |
Memory |
13312 KB |
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:49:26: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&n,&k),p=0;
^
./Main.cpp:51:29: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&a[i],&b[i]);
^
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 |
6 ms |
8568 KB |
in10.txt |
AC |
131 ms |
13312 KB |
in101.txt |
AC |
94 ms |
13312 KB |
in102.txt |
AC |
97 ms |
13312 KB |
in103.txt |
AC |
87 ms |
13312 KB |
in104.txt |
AC |
104 ms |
13312 KB |
in105.txt |
AC |
97 ms |
13312 KB |
in106.txt |
AC |
94 ms |
13312 KB |
in107.txt |
AC |
97 ms |
13312 KB |
in108.txt |
AC |
87 ms |
13312 KB |
in109.txt |
AC |
103 ms |
13312 KB |
in11.txt |
AC |
133 ms |
13312 KB |
in110.txt |
AC |
97 ms |
13312 KB |
in12.txt |
AC |
124 ms |
13312 KB |
in13.txt |
AC |
120 ms |
13312 KB |
in14.txt |
AC |
124 ms |
13312 KB |
in15.txt |
AC |
117 ms |
13312 KB |
in16.txt |
AC |
120 ms |
13312 KB |
in17.txt |
AC |
121 ms |
13312 KB |
in18.txt |
AC |
122 ms |
13312 KB |
in19.txt |
AC |
120 ms |
13312 KB |
in2.txt |
AC |
133 ms |
13312 KB |
in20.txt |
AC |
122 ms |
13312 KB |
in21.txt |
AC |
99 ms |
13312 KB |
in22.txt |
AC |
96 ms |
13312 KB |
in23.txt |
AC |
102 ms |
13312 KB |
in24.txt |
AC |
103 ms |
13312 KB |
in25.txt |
AC |
37 ms |
9216 KB |
in26.txt |
AC |
37 ms |
9216 KB |
in27.txt |
AC |
35 ms |
9216 KB |
in28.txt |
AC |
39 ms |
9216 KB |
in3.txt |
AC |
130 ms |
13312 KB |
in4.txt |
AC |
133 ms |
13312 KB |
in5.txt |
AC |
111 ms |
13184 KB |
in6.txt |
AC |
119 ms |
13312 KB |
in7.txt |
AC |
116 ms |
13312 KB |
in8.txt |
AC |
12 ms |
4736 KB |
in9.txt |
AC |
132 ms |
13312 KB |
sample1.txt |
AC |
3 ms |
8448 KB |
sample2.txt |
AC |
2 ms |
2304 KB |
sample3.txt |
AC |
3 ms |
8448 KB |
sample4.txt |
AC |
3 ms |
8448 KB |
sub2in1.txt |
AC |
4 ms |
8448 KB |
sub2in10.txt |
AC |
4 ms |
8448 KB |
sub2in11.txt |
AC |
3 ms |
8448 KB |
sub2in12.txt |
AC |
4 ms |
8448 KB |
sub2in13.txt |
AC |
4 ms |
8448 KB |
sub2in14.txt |
AC |
4 ms |
8448 KB |
sub2in15.txt |
AC |
4 ms |
8448 KB |
sub2in16.txt |
AC |
4 ms |
8448 KB |
sub2in17.txt |
AC |
3 ms |
8448 KB |
sub2in18.txt |
AC |
4 ms |
8448 KB |
sub2in19.txt |
AC |
4 ms |
8448 KB |
sub2in2.txt |
AC |
4 ms |
8448 KB |
sub2in20.txt |
AC |
4 ms |
8448 KB |
sub2in21.txt |
AC |
4 ms |
8448 KB |
sub2in22.txt |
AC |
4 ms |
8448 KB |
sub2in23.txt |
AC |
4 ms |
8448 KB |
sub2in24.txt |
AC |
4 ms |
8448 KB |
sub2in3.txt |
AC |
4 ms |
8448 KB |
sub2in4.txt |
AC |
4 ms |
8448 KB |
sub2in5.txt |
AC |
3 ms |
8448 KB |
sub2in6.txt |
AC |
4 ms |
8448 KB |
sub2in7.txt |
AC |
2 ms |
4352 KB |
sub2in8.txt |
AC |
4 ms |
8448 KB |
sub2in9.txt |
AC |
4 ms |
8448 KB |
subin1.txt |
AC |
204 ms |
13312 KB |
subin10.txt |
AC |
187 ms |
13312 KB |
subin101.txt |
AC |
179 ms |
13312 KB |
subin102.txt |
AC |
133 ms |
13312 KB |
subin103.txt |
AC |
116 ms |
13312 KB |
subin104.txt |
AC |
118 ms |
13312 KB |
subin105.txt |
AC |
109 ms |
13312 KB |
subin106.txt |
AC |
108 ms |
13312 KB |
subin107.txt |
AC |
142 ms |
13312 KB |
subin108.txt |
AC |
140 ms |
13312 KB |
subin109.txt |
AC |
131 ms |
13312 KB |
subin11.txt |
AC |
173 ms |
13312 KB |
subin12.txt |
AC |
177 ms |
13312 KB |
subin13.txt |
AC |
180 ms |
13312 KB |
subin14.txt |
AC |
183 ms |
13312 KB |
subin15.txt |
AC |
179 ms |
13312 KB |
subin16.txt |
AC |
182 ms |
13312 KB |
subin17.txt |
AC |
168 ms |
13312 KB |
subin18.txt |
AC |
172 ms |
13312 KB |
subin19.txt |
AC |
175 ms |
13312 KB |
subin2.txt |
AC |
202 ms |
13312 KB |
subin20.txt |
AC |
178 ms |
13312 KB |
subin201.txt |
AC |
3 ms |
8448 KB |
subin21.txt |
AC |
41 ms |
9216 KB |
subin22.txt |
AC |
41 ms |
9216 KB |
subin23.txt |
AC |
44 ms |
9216 KB |
subin24.txt |
AC |
43 ms |
9344 KB |
subin3.txt |
AC |
205 ms |
13312 KB |
subin4.txt |
AC |
173 ms |
13184 KB |
subin5.txt |
AC |
176 ms |
13312 KB |
subin6.txt |
AC |
138 ms |
13312 KB |
subin7.txt |
AC |
19 ms |
5120 KB |
subin8.txt |
AC |
14 ms |
4864 KB |
subin9.txt |
AC |
207 ms |
13312 KB |