Submission #1678050
Source Code Expand
#include <bits/stdc++.h>
#define ls (n<<1)
#define rs (ls|1)
using namespace std;
typedef long long LL;
const int N=100010;
const LL oo=1LL<<60;
int n,k,m,c[2*N],l[N],r[N],s;
LL t[4*N],sum;
void build(int n,int l,int r)
{
if (l==r) t[n]=-c[l];
else
{
int mid=(l+r)>>1;
build(ls,l,mid),build(rs,mid+1,r);
t[n]=min(t[ls],t[rs]);
}
}
LL askmin(int n,int l,int r,int L,int R)
{
if (t[n]==oo) return oo;
LL ret;
if ((L<=l)&&(r<=R)) ret=t[n],t[n]=oo;
else
{
int mid=(l+r)>>1;
if (mid>=R) ret=askmin(ls,l,mid,L,R);
else if (L>mid) ret=askmin(rs,mid+1,r,L,R);
else ret=min(askmin(ls,l,mid,L,R),askmin(rs,mid+1,r,L,R));
t[n]=min(t[ls],t[rs]);
}
return ret;
}
void modify(int n,int l,int r,int x,LL k)
{
if (l==r) t[n]=min(t[n],k-c[l]);
else
{
int mid=(l+r)>>1;
if (t[n]==oo) t[ls]=t[rs]=oo;
x<=mid?modify(ls,l,mid,x,k):modify(rs,mid+1,r,x,k);
t[n]=min(t[ls],t[rs]);
}
}
LL getans(int n,int l,int r)
{
if (t[n]==oo) return oo;
if (l==r) return t[n]+c[l];
else
{
int mid=(l+r)>>1;
return min(getans(ls,l,mid),getans(rs,mid+1,r));
}
}
void work()
{
scanf("%d %d",&n,&k);
for (int i=1,a,b; i<=n; i++)
{
scanf("%d %d",&a,&b),sum+=2*a;
if ((b==1)&&(2*a>k)) puts("-1"),exit(0);
if (b==1) l[i]=(s+2LL*(k-a%k))%k,r[i]=s;
s=(s+2LL*(k-a%k))%k;
}
for (int i=1; i<=n; i++) c[i]=l[i],c[i+n]=r[i];
sort(c+1,c+2*n+1),m=unique(c+1,c+2*n+1)-c-1;
for (int i=1; i<=n; i++)
{
l[i]=lower_bound(c+1,c+m+1,l[i])-c;
r[i]=lower_bound(c+1,c+m+1,r[i])-c;
}
build(1,1,m);
for (int i=1; i<=n; i++)
if (l[i]<=r[i])
{
if (r[i]-l[i]>1)
modify(1,1,m,r[i],askmin(1,1,m,l[i]+1,r[i]-1)+c[r[i]]);
}else
{
if (l[i]<m) modify(1,1,m,r[i],askmin(1,1,m,l[i]+1,m)+k+c[r[i]]);
if (r[i]>1) modify(1,1,m,r[i],askmin(1,1,m,1,r[i]-1)+c[r[i]]);
}
printf("%lld",sum+getans(1,1,m));
}
int main()
{
work();
return 0;
}
Submission Info
Submission Time |
|
Task |
F - Train Service Planning |
User |
YMDragon |
Language |
C++14 (GCC 5.4.1) |
Score |
500 |
Code Size |
2017 Byte |
Status |
WA |
Exec Time |
91 ms |
Memory |
4992 KB |
Compile Error
./Main.cpp: In function ‘void work()’:
./Main.cpp:64:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&n,&k);
^
./Main.cpp:67:33: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&a,&b),sum+=2*a;
^
Judge Result
Set Name |
Sample |
All |
subtask |
subtask2 |
Score / Max Score |
0 / 0 |
0 / 700 |
500 / 500 |
0 / 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 |
2 ms |
2304 KB |
in10.txt |
AC |
56 ms |
4992 KB |
in101.txt |
AC |
45 ms |
3968 KB |
in102.txt |
AC |
44 ms |
3968 KB |
in103.txt |
AC |
46 ms |
3456 KB |
in104.txt |
AC |
46 ms |
4992 KB |
in105.txt |
AC |
41 ms |
4992 KB |
in106.txt |
AC |
47 ms |
3968 KB |
in107.txt |
AC |
44 ms |
3968 KB |
in108.txt |
AC |
45 ms |
3456 KB |
in109.txt |
AC |
45 ms |
4992 KB |
in11.txt |
AC |
58 ms |
4992 KB |
in110.txt |
AC |
41 ms |
4992 KB |
in12.txt |
AC |
52 ms |
4992 KB |
in13.txt |
AC |
49 ms |
4992 KB |
in14.txt |
AC |
51 ms |
4992 KB |
in15.txt |
AC |
52 ms |
4992 KB |
in16.txt |
AC |
52 ms |
4992 KB |
in17.txt |
AC |
51 ms |
4992 KB |
in18.txt |
AC |
53 ms |
4992 KB |
in19.txt |
AC |
51 ms |
4992 KB |
in2.txt |
AC |
58 ms |
4992 KB |
in20.txt |
AC |
52 ms |
4992 KB |
in21.txt |
AC |
47 ms |
4992 KB |
in22.txt |
AC |
41 ms |
4992 KB |
in23.txt |
AC |
50 ms |
4992 KB |
in24.txt |
AC |
52 ms |
4992 KB |
in25.txt |
AC |
29 ms |
2944 KB |
in26.txt |
AC |
29 ms |
2944 KB |
in27.txt |
AC |
28 ms |
2944 KB |
in28.txt |
AC |
29 ms |
2944 KB |
in3.txt |
AC |
56 ms |
4992 KB |
in4.txt |
AC |
57 ms |
4992 KB |
in5.txt |
AC |
48 ms |
3840 KB |
in6.txt |
AC |
50 ms |
4992 KB |
in7.txt |
AC |
53 ms |
3968 KB |
in8.txt |
AC |
13 ms |
2304 KB |
in9.txt |
AC |
58 ms |
4992 KB |
sample1.txt |
AC |
2 ms |
2304 KB |
sample2.txt |
AC |
1 ms |
256 KB |
sample3.txt |
AC |
2 ms |
2304 KB |
sample4.txt |
AC |
2 ms |
2304 KB |
sub2in1.txt |
AC |
2 ms |
2304 KB |
sub2in10.txt |
AC |
2 ms |
2304 KB |
sub2in11.txt |
AC |
2 ms |
2304 KB |
sub2in12.txt |
AC |
2 ms |
2304 KB |
sub2in13.txt |
AC |
2 ms |
2304 KB |
sub2in14.txt |
AC |
2 ms |
2304 KB |
sub2in15.txt |
AC |
2 ms |
2304 KB |
sub2in16.txt |
AC |
2 ms |
2304 KB |
sub2in17.txt |
AC |
2 ms |
2304 KB |
sub2in18.txt |
AC |
2 ms |
2304 KB |
sub2in19.txt |
AC |
2 ms |
2304 KB |
sub2in2.txt |
AC |
2 ms |
2304 KB |
sub2in20.txt |
AC |
2 ms |
2304 KB |
sub2in21.txt |
AC |
2 ms |
2304 KB |
sub2in22.txt |
AC |
2 ms |
2304 KB |
sub2in23.txt |
WA |
2 ms |
2304 KB |
sub2in24.txt |
AC |
2 ms |
2304 KB |
sub2in3.txt |
AC |
2 ms |
2304 KB |
sub2in4.txt |
AC |
2 ms |
2304 KB |
sub2in5.txt |
AC |
2 ms |
2304 KB |
sub2in6.txt |
AC |
2 ms |
2304 KB |
sub2in7.txt |
AC |
2 ms |
2304 KB |
sub2in8.txt |
AC |
2 ms |
2304 KB |
sub2in9.txt |
AC |
2 ms |
2304 KB |
subin1.txt |
AC |
84 ms |
4992 KB |
subin10.txt |
AC |
73 ms |
4992 KB |
subin101.txt |
AC |
91 ms |
4992 KB |
subin102.txt |
AC |
55 ms |
4992 KB |
subin103.txt |
AC |
47 ms |
4992 KB |
subin104.txt |
AC |
45 ms |
4992 KB |
subin105.txt |
AC |
41 ms |
4992 KB |
subin106.txt |
AC |
43 ms |
4992 KB |
subin107.txt |
AC |
66 ms |
4992 KB |
subin108.txt |
AC |
62 ms |
4992 KB |
subin109.txt |
AC |
53 ms |
4992 KB |
subin11.txt |
AC |
71 ms |
4992 KB |
subin12.txt |
AC |
73 ms |
4992 KB |
subin13.txt |
AC |
72 ms |
4992 KB |
subin14.txt |
AC |
71 ms |
4992 KB |
subin15.txt |
AC |
70 ms |
4992 KB |
subin16.txt |
AC |
71 ms |
4992 KB |
subin17.txt |
AC |
69 ms |
4992 KB |
subin18.txt |
AC |
70 ms |
4992 KB |
subin19.txt |
AC |
68 ms |
4992 KB |
subin2.txt |
AC |
83 ms |
4992 KB |
subin20.txt |
AC |
69 ms |
4992 KB |
subin201.txt |
AC |
2 ms |
2304 KB |
subin21.txt |
AC |
29 ms |
2944 KB |
subin22.txt |
AC |
29 ms |
2944 KB |
subin23.txt |
AC |
30 ms |
2944 KB |
subin24.txt |
AC |
31 ms |
2944 KB |
subin3.txt |
AC |
85 ms |
4992 KB |
subin4.txt |
AC |
71 ms |
4864 KB |
subin5.txt |
AC |
71 ms |
4992 KB |
subin6.txt |
AC |
64 ms |
4992 KB |
subin7.txt |
AC |
19 ms |
2304 KB |
subin8.txt |
AC |
14 ms |
2304 KB |
subin9.txt |
AC |
85 ms |
4992 KB |