Submission #1164742
Source Code Expand
#include <bits/stdc++.h>
#define N 200006
#define mid ((l+r)>>1)
#define ls i<<1
#define rs i<<1|1
#define inf 1e18
#define in l==r
#define in2 x<=l&&r<=y
using namespace std;
map<int,int>g;
int n,k,x,tot,d[N],b[N],ll[N],rr[N],q[N],f[N<<2];long long s[N<<2],a[N];
void down(int i,int l,int r)
{
if(f[i]){
f[i]=0;s[i]=inf;
if(l!=r)f[ls]=f[rs]=1;
}
}
void build(int i,int l,int r)
{
if(in){s[i]=-q[l];return;}
build(ls,l,mid);build(rs,mid+1,r);s[i]=min(s[ls],s[rs]);
}
void del(int i,int l,int r,int x,int y)
{
down(i,l,r);if(in2){f[i]=1;return;}
if(x<=mid)del(ls,l,mid,x,y);if(y>mid)del(rs,mid+1,r,x,y);
down(ls,l,mid);down(rs,mid+1,r);s[i]=min(s[ls],s[rs]);
}
long long query(int i,int l,int r,int x,int y)
{
down(i,l,r);if(in2)return s[i];
long long tmp=inf;if(x<=mid)tmp=query(ls,l,mid,x,y);
if(y>mid)tmp=min(tmp,query(rs,mid+1,r,x,y));return tmp;
}
void change(int i,int l,int r,int x,long long y)
{
down(i,l,r);if(in){s[i]=min(s[i],y-q[l]);return;}
if(x<=mid)change(ls,l,mid,x,y);else change(rs,mid+1,r,x,y);
down(ls,l,mid);down(rs,mid+1,r);s[i]=min(s[ls],s[rs]);
}
long long find(int i,int l,int r)
{
down(i,l,r);if(in)return s[i]+q[l];
return min(find(ls,l,mid),find(rs,mid+1,r));
}
int main()
{
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++){
scanf("%d%d",&x,&b[i]);
if(b[i]==1&&x*2>k)return puts("-1"),0;
a[i]=a[i-1]+1LL*x;if(b[i]==2)continue;
ll[i]=-2LL*a[i-1]%k;ll[i]+=ll[i]<0?k:0;
rr[i]=-2LL*a[i]%k;rr[i]+=rr[i]<0?k:0;
d[i]=ll[i];d[n+i]=rr[i];
}
sort(d+1,d+2*n+1);
for(int i=1;i<=2*n;i++)
if(d[i]!=d[i-1]||i==1)g[d[i]]=++tot,q[tot]=d[i];
build(1,1,tot);
for(int i=1;i<=n;i++){
if(b[i]==2)continue;
int L=g[ll[i]],R=g[rr[i]];
if(L>R){
change(1,1,tot,L,(R+1<L?query(1,1,tot,R+1,L-1):inf)+ll[i]);
if(R+1<L)del(1,1,tot,R+1,L-1);
}else{
change(1,1,tot,L,(1<L?query(1,1,tot,1,L-1):inf)+ll[i]);
change(1,1,tot,L,(R<tot?query(1,1,tot,R+1,tot):inf)+k+ll[i]);
if(1<L)del(1,1,tot,1,L-1);
if(R<tot)del(1,1,tot,R+1,tot);
}
}
printf("%lld",2LL*a[n]+find(1,1,tot));
}
Submission Info
Submission Time
2017-03-17 16:59:15+0900
Task
F - Train Service Planning
User
wtl666wtl
Language
C++14 (GCC 5.4.1)
Score
1700
Code Size
2104 Byte
Status
AC
Exec Time
211 ms
Memory
18944 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:49:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&n,&k);
^
./Main.cpp:51:25: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&x,&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
3 ms
6400 KB
in10.txt
AC
123 ms
15488 KB
in101.txt
AC
78 ms
14208 KB
in102.txt
AC
78 ms
15360 KB
in103.txt
AC
81 ms
11136 KB
in104.txt
AC
78 ms
16384 KB
in105.txt
AC
78 ms
16768 KB
in106.txt
AC
75 ms
14208 KB
in107.txt
AC
78 ms
15360 KB
in108.txt
AC
74 ms
11136 KB
in109.txt
AC
79 ms
16384 KB
in11.txt
AC
126 ms
15744 KB
in110.txt
AC
79 ms
16768 KB
in12.txt
AC
119 ms
15744 KB
in13.txt
AC
114 ms
15488 KB
in14.txt
AC
117 ms
15744 KB
in15.txt
AC
110 ms
15744 KB
in16.txt
AC
113 ms
15744 KB
in17.txt
AC
115 ms
15744 KB
in18.txt
AC
117 ms
15744 KB
in19.txt
AC
113 ms
15744 KB
in2.txt
AC
128 ms
15744 KB
in20.txt
AC
118 ms
15744 KB
in21.txt
AC
77 ms
15744 KB
in22.txt
AC
70 ms
15744 KB
in23.txt
AC
81 ms
15744 KB
in24.txt
AC
83 ms
15744 KB
in25.txt
AC
30 ms
7680 KB
in26.txt
AC
29 ms
7680 KB
in27.txt
AC
28 ms
7680 KB
in28.txt
AC
31 ms
7680 KB
in3.txt
AC
122 ms
15488 KB
in4.txt
AC
127 ms
15744 KB
in5.txt
AC
105 ms
15104 KB
in6.txt
AC
112 ms
15744 KB
in7.txt
AC
105 ms
14080 KB
in8.txt
AC
13 ms
4992 KB
in9.txt
AC
125 ms
15744 KB
sample1.txt
AC
2 ms
6400 KB
sample2.txt
AC
2 ms
2304 KB
sample3.txt
AC
2 ms
4352 KB
sample4.txt
AC
2 ms
6400 KB
sub2in1.txt
AC
3 ms
6400 KB
sub2in10.txt
AC
3 ms
6400 KB
sub2in11.txt
AC
3 ms
6400 KB
sub2in12.txt
AC
3 ms
6400 KB
sub2in13.txt
AC
3 ms
6400 KB
sub2in14.txt
AC
3 ms
6400 KB
sub2in15.txt
AC
2 ms
6400 KB
sub2in16.txt
AC
2 ms
6400 KB
sub2in17.txt
AC
2 ms
6400 KB
sub2in18.txt
AC
2 ms
6400 KB
sub2in19.txt
AC
2 ms
6400 KB
sub2in2.txt
AC
2 ms
6400 KB
sub2in20.txt
AC
2 ms
6400 KB
sub2in21.txt
AC
2 ms
6400 KB
sub2in22.txt
AC
2 ms
6400 KB
sub2in23.txt
AC
2 ms
6400 KB
sub2in24.txt
AC
2 ms
6400 KB
sub2in3.txt
AC
2 ms
6400 KB
sub2in4.txt
AC
3 ms
6400 KB
sub2in5.txt
AC
2 ms
6400 KB
sub2in6.txt
AC
2 ms
6400 KB
sub2in7.txt
AC
2 ms
4352 KB
sub2in8.txt
AC
3 ms
6400 KB
sub2in9.txt
AC
3 ms
6400 KB
subin1.txt
AC
211 ms
16896 KB
subin10.txt
AC
198 ms
16896 KB
subin101.txt
AC
166 ms
16896 KB
subin102.txt
AC
115 ms
16896 KB
subin103.txt
AC
103 ms
16896 KB
subin104.txt
AC
101 ms
16896 KB
subin105.txt
AC
92 ms
16896 KB
subin106.txt
AC
93 ms
16896 KB
subin107.txt
AC
128 ms
16896 KB
subin108.txt
AC
125 ms
16896 KB
subin109.txt
AC
112 ms
16896 KB
subin11.txt
AC
180 ms
18944 KB
subin12.txt
AC
187 ms
16896 KB
subin13.txt
AC
195 ms
16896 KB
subin14.txt
AC
196 ms
16896 KB
subin15.txt
AC
189 ms
16896 KB
subin16.txt
AC
196 ms
16896 KB
subin17.txt
AC
172 ms
16512 KB
subin18.txt
AC
179 ms
16512 KB
subin19.txt
AC
185 ms
16512 KB
subin2.txt
AC
207 ms
16512 KB
subin20.txt
AC
186 ms
16512 KB
subin201.txt
AC
2 ms
4352 KB
subin21.txt
AC
35 ms
7680 KB
subin22.txt
AC
34 ms
7680 KB
subin23.txt
AC
36 ms
7680 KB
subin24.txt
AC
36 ms
7680 KB
subin3.txt
AC
211 ms
16896 KB
subin4.txt
AC
177 ms
16000 KB
subin5.txt
AC
187 ms
16896 KB
subin6.txt
AC
128 ms
16896 KB
subin7.txt
AC
20 ms
5632 KB
subin8.txt
AC
15 ms
5248 KB
subin9.txt
AC
211 ms
16896 KB