Submission #1160109
Source Code Expand
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#include<cmath>
#include<string>
#define ls (t<<1)
#define rs ((t<<1)+1)
#define mid ((l+r)>>1)
#define fi first
#define se second
#define mk make_pair
#define pb push_back
#define N 200005
#define M 200005
#define seed 23333
using namespace std;
typedef long long LL;
const LL INF=1e18;
int K,i,j,m,n,p,k,B[N],C[N],L[N],R[N];
LL A[N],Min[N*4],Add[N*4];
void build_tree(int l,int r,int t)
{
if (l==r) Min[t]=-C[l];
else
{
build_tree(l,mid,ls); build_tree(mid+1,r,rs);
Min[t]=min(Min[ls],Min[rs]);
}
}
void down(int t)
{
if (Add[t]==-1) return;
Add[ls]=Add[rs]=Min[ls]=Min[rs]=INF;
Add[t]=-1;
}
long long FindMin(int ll,int rr,int l,int r,int t)
{
if (ll>rr) return INF;
else if (ll<=l&&r<=rr) return Min[t];
else
{
down(t);
long long S=INF;
if (ll<=mid) S=min(S,FindMin(ll,rr,l,mid,ls));
if (rr>mid) S=min(S,FindMin(ll,rr,mid+1,r,rs));
return S;
}
}
void update(int ll,long long c,int l,int r,int t)
{
if (l==r) Min[t]=min(Min[t],c-C[l]);
else
{
down(t);
if (ll<=mid) update(ll,c,l,mid,ls);
else update(ll,c,mid+1,r,rs);
Min[t]=min(Min[ls],Min[rs]);
}
}
long long DFS(int l,int r,int t)
{
if (l==r) return Min[t]+C[l];
else
return down(t),min(DFS(l,mid,ls),DFS(mid+1,r,rs));
}
void del(int ll,int rr,int l,int r,int t)
{
if (ll>rr) return;
if (ll<=l&&r<=rr) Add[t]=Min[t]=INF;
else
{
down(t);
if (ll<=mid) del(ll,rr,l,mid,ls);
if (rr>mid) del(ll,rr,mid+1,r,rs);
Min[t]=min(Min[ls],Min[rs]);
}
}
int main()
{
scanf("%d%d",&n,&K);
memset(Add,-1,sizeof(Add));
for (i=1;i<=n;++i)
{
scanf("%lld%d",&A[i],&B[i]);
if (B[i]==1&&2*A[i]>K)
{
puts("-1");
return 0;
}
A[i]+=A[i-1];
if (B[i]==2) continue;
L[i]=(-2*A[i-1])%K; if (L[i]<0) L[i]+=K;
R[i]=(-2*A[i])%K; if (R[i]<0) R[i]+=K;
C[++C[0]]=L[i]; C[++C[0]]=R[i];
}
sort(C+1,C+C[0]+1); C[0]=unique(C+1,C+C[0]+1)-(C+1);
build_tree(1,C[0],1);
for (i=1;i<=n;++i)
{
if (B[i]==2) continue;
int l=lower_bound(C+1,C+C[0]+1,L[i])-C,r=lower_bound(C+1,C+C[0]+1,R[i])-C;
if (l>r)
{
update(l,FindMin(r+1,l-1,1,C[0],1)+C[l],1,C[0],1);
del(r+1,l-1,1,C[0],1);
}
else
{
update(l,FindMin(r+1,C[0],1,C[0],1)+C[l]+K,1,C[0],1);
update(l,FindMin(1,l-1,1,C[0],1)+C[l],1,C[0],1);
del(r+1,C[0],1,C[0],1);
del(1,l-1,1,C[0],1);
}
}
printf("%lld\n",2*A[n]+DFS(1,C[0],1));
}
Submission Info
Submission Time
2017-03-13 15:25:49+0900
Task
F - Train Service Planning
User
qiaoranliqu
Language
C++14 (GCC 5.4.1)
Score
1700
Code Size
2716 Byte
Status
AC
Exec Time
157 ms
Memory
15104 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:88: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:92:32: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%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
5 ms
12544 KB
in10.txt
AC
89 ms
14976 KB
in101.txt
AC
65 ms
12928 KB
in102.txt
AC
60 ms
12928 KB
in103.txt
AC
67 ms
12928 KB
in104.txt
AC
55 ms
14976 KB
in105.txt
AC
53 ms
14976 KB
in106.txt
AC
65 ms
12928 KB
in107.txt
AC
59 ms
12928 KB
in108.txt
AC
67 ms
12928 KB
in109.txt
AC
55 ms
14976 KB
in11.txt
AC
90 ms
14976 KB
in110.txt
AC
53 ms
14976 KB
in12.txt
AC
85 ms
14976 KB
in13.txt
AC
83 ms
14976 KB
in14.txt
AC
84 ms
14976 KB
in15.txt
AC
78 ms
14976 KB
in16.txt
AC
81 ms
14976 KB
in17.txt
AC
82 ms
15104 KB
in18.txt
AC
83 ms
14976 KB
in19.txt
AC
81 ms
14976 KB
in2.txt
AC
91 ms
14976 KB
in20.txt
AC
83 ms
14976 KB
in21.txt
AC
53 ms
14976 KB
in22.txt
AC
46 ms
14976 KB
in23.txt
AC
57 ms
14976 KB
in24.txt
AC
60 ms
14976 KB
in25.txt
AC
30 ms
12928 KB
in26.txt
AC
30 ms
12928 KB
in27.txt
AC
29 ms
12928 KB
in28.txt
AC
31 ms
12928 KB
in3.txt
AC
89 ms
14976 KB
in4.txt
AC
91 ms
14976 KB
in5.txt
AC
77 ms
12928 KB
in6.txt
AC
80 ms
14976 KB
in7.txt
AC
86 ms
12928 KB
in8.txt
AC
15 ms
12800 KB
in9.txt
AC
90 ms
14976 KB
sample1.txt
AC
4 ms
12544 KB
sample2.txt
AC
4 ms
10496 KB
sample3.txt
AC
4 ms
12544 KB
sample4.txt
AC
4 ms
12544 KB
sub2in1.txt
AC
4 ms
12544 KB
sub2in10.txt
AC
4 ms
12544 KB
sub2in11.txt
AC
4 ms
12544 KB
sub2in12.txt
AC
4 ms
12544 KB
sub2in13.txt
AC
4 ms
12544 KB
sub2in14.txt
AC
4 ms
12544 KB
sub2in15.txt
AC
4 ms
12544 KB
sub2in16.txt
AC
4 ms
12544 KB
sub2in17.txt
AC
4 ms
12544 KB
sub2in18.txt
AC
4 ms
12544 KB
sub2in19.txt
AC
4 ms
12544 KB
sub2in2.txt
AC
4 ms
12544 KB
sub2in20.txt
AC
4 ms
12544 KB
sub2in21.txt
AC
4 ms
12544 KB
sub2in22.txt
AC
4 ms
12544 KB
sub2in23.txt
AC
4 ms
12544 KB
sub2in24.txt
AC
4 ms
12544 KB
sub2in3.txt
AC
4 ms
12544 KB
sub2in4.txt
AC
4 ms
12544 KB
sub2in5.txt
AC
4 ms
12544 KB
sub2in6.txt
AC
4 ms
12544 KB
sub2in7.txt
AC
4 ms
12544 KB
sub2in8.txt
AC
4 ms
12544 KB
sub2in9.txt
AC
4 ms
12544 KB
subin1.txt
AC
156 ms
14976 KB
subin10.txt
AC
144 ms
14976 KB
subin101.txt
AC
129 ms
14976 KB
subin102.txt
AC
80 ms
14976 KB
subin103.txt
AC
69 ms
14976 KB
subin104.txt
AC
67 ms
14976 KB
subin105.txt
AC
48 ms
14976 KB
subin106.txt
AC
48 ms
14976 KB
subin107.txt
AC
87 ms
14976 KB
subin108.txt
AC
95 ms
14976 KB
subin109.txt
AC
78 ms
14976 KB
subin11.txt
AC
132 ms
14976 KB
subin12.txt
AC
136 ms
14976 KB
subin13.txt
AC
140 ms
14976 KB
subin14.txt
AC
143 ms
14976 KB
subin15.txt
AC
138 ms
14976 KB
subin16.txt
AC
141 ms
14976 KB
subin17.txt
AC
129 ms
14976 KB
subin18.txt
AC
133 ms
14976 KB
subin19.txt
AC
138 ms
14976 KB
subin2.txt
AC
154 ms
14976 KB
subin20.txt
AC
139 ms
14976 KB
subin201.txt
AC
4 ms
12544 KB
subin21.txt
AC
37 ms
12928 KB
subin22.txt
AC
36 ms
12928 KB
subin23.txt
AC
38 ms
12928 KB
subin24.txt
AC
38 ms
12928 KB
subin3.txt
AC
157 ms
14976 KB
subin4.txt
AC
133 ms
14976 KB
subin5.txt
AC
136 ms
14976 KB
subin6.txt
AC
91 ms
14976 KB
subin7.txt
AC
24 ms
12928 KB
subin8.txt
AC
18 ms
12800 KB
subin9.txt
AC
156 ms
14976 KB