Submission #1866817
Source Code Expand
///////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////
// _oo0oo_ //
// o8888888o //
// 88" . "88 ------ hzt1 //
// (| -_- |) //
// 0\ = /0 //
// ___/`---'\___ //
// .' \| |// '. //
// / \||| : |||// \ //
// / _||||| -:- |||||- \ //
// | | \ - /// | | //
// | \_| ''\---/'' |_/ | //
// \ .-\__ '-' ___/-. / //
// ___'. .' /--.--\ `. .'___ //
// ."" '< `.___\_<|>_/___.' >' "". //
// | | : `- \`.;`\ _ /`;.`/ - ` : | | //
// \ \ `_. \_ __\ /__ _/ .-` / / //
// =====`-.____`.___ \_____/___.-`___.-'===== //
// `=---=' //
// //
// //
// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ //
// //
// God-He Bless All. //
// This Code Will Never Explode. //
// //
// //
///////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////
#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#include<vector>
#define pb push_back
#define mp make_pair
#define xx first
#define yy second
#define rep(i,a,b) for(int i=(a),i##_end_=(b);i<=i##_end_;i++)
#define dwn(i,a,b) for(int i=(a),i##_end_=(b);i>=i##_end_;i--)
using namespace std;
const int Size=1<<16;
char buffer[Size],*head,*tail;
inline char Getchar() {
if(head==tail) {
int l=fread(buffer,1,Size,stdin);
tail=(head=buffer)+l;
}
if(head==tail) return -1;
return *head++;
}
inline int read() {
int x=0,f=1;char c=Getchar();
for(;!isdigit(c);c=Getchar()) if(c=='-') f=-1;
for(;isdigit(c);c=Getchar()) x=x*10+c-'0';
return x*f;
}
typedef long long ll;
typedef pair<int,int> pii;
const int maxn=100010;
int n,k,sum[maxn],A[maxn],B[maxn];
void GG() {puts("-1");exit(0);}
pii p[maxn];
ll ans,f[maxn],g[maxn];
int add(int x,int y) {return ((x+y)%k+k)%k;}
int in(int x,int l,int r) {
if(l<=r) return (x>=l)&&(x<=r);
return (x>=l)||(x<=r);
}
const int maxnode=3000010;
ll setv[maxnode];
int ls[maxnode],rs[maxnode],ToT;
void pushdown(int o) {
if(!ls[o]) setv[ls[o]=++ToT]=0;
if(!rs[o]) setv[rs[o]=++ToT]=0;
setv[ls[o]]=setv[rs[o]]=setv[o];
setv[o]=0;
}
void update(int& x,int l,int r,int ql,int qr,int v) {
if(!x) setv[x=++ToT]=0;
if(ql<=l&&r<=qr) setv[x]=v;
else {
int mid=l+r>>1;
if(setv[x]) pushdown(x);
if(ql<=mid) update(ls[x],l,mid,ql,qr,v);
if(qr>mid) update(rs[x],mid+1,r,ql,qr,v);
}
}
ll query(int& x,int l,int r,int p) {
if(!x) return 0;
if(setv[x]) return setv[x];
int mid=l+r>>1;
if(p<=mid) return query(ls[x],l,mid,p);
return query(rs[x],mid+1,r,p);
}
int root;
int Query(int p) {return query(root,0,k-1,p);}
int main() {
n=read();k=read();
rep(i,1,n) {
ans+=A[i]=read();B[i]=read();
sum[i]=(sum[i-1]+A[i])%k;
if(B[i]==1&&A[i]*2>k) GG();
p[i]=mp((k-2*sum[i]%k)%k,(k-2*sum[i-1]%k)%k);
}
dwn(i,n,1) {
int j=Query(p[i].xx);
if(j) f[i]=min(f[j]+add(p[j].xx,-p[i].xx),g[j]+add(p[j].yy,-p[i].xx));
j=Query(p[i].yy);
if(j) g[i]=min(f[j]+add(p[j].xx,-p[i].yy),g[j]+add(p[j].yy,-p[i].yy));
if(B[i]==1) {
int l=add(p[i].xx,1),r=add(p[i].yy,-1);
if(l<=r) update(root,0,k-1,l,r,i);
else update(root,0,k-1,l,k-1,i),update(root,0,k-1,0,r,i);
}
}
ll res=1ll<<60;
root=ToT=0;
rep(i,1,n) {
if(!Query(p[i].xx)) res=min(res,f[i]);
if(!Query(p[i].yy)) res=min(res,g[i]);
if(B[i]==1) {
int l=add(p[i].xx,1),r=add(p[i].yy,-1);
if(l<=r) update(root,0,k-1,l,r,i);
else update(root,0,k-1,l,k-1,i),update(root,0,k-1,0,r,i);
}
}
printf("%lld\n",ans*2+res);
return 0;
}
Submission Info
Submission Time |
|
Task |
F - Train Service Planning |
User |
wzj52501 |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
4542 Byte |
Status |
WA |
Exec Time |
184 ms |
Memory |
50560 KB |
Judge Result
Set Name |
Sample |
All |
subtask |
subtask2 |
Score / Max Score |
0 / 0 |
0 / 700 |
0 / 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 |
3 ms |
8448 KB |
in10.txt |
AC |
71 ms |
17792 KB |
in101.txt |
WA |
72 ms |
17664 KB |
in102.txt |
WA |
72 ms |
23936 KB |
in103.txt |
WA |
73 ms |
14592 KB |
in104.txt |
WA |
73 ms |
25984 KB |
in105.txt |
WA |
69 ms |
25984 KB |
in106.txt |
WA |
72 ms |
17664 KB |
in107.txt |
WA |
72 ms |
23936 KB |
in108.txt |
WA |
73 ms |
14592 KB |
in109.txt |
WA |
74 ms |
28032 KB |
in11.txt |
AC |
111 ms |
40320 KB |
in110.txt |
WA |
70 ms |
28032 KB |
in12.txt |
WA |
97 ms |
34176 KB |
in13.txt |
WA |
71 ms |
17792 KB |
in14.txt |
WA |
108 ms |
40320 KB |
in15.txt |
WA |
114 ms |
40320 KB |
in16.txt |
WA |
111 ms |
42368 KB |
in17.txt |
WA |
113 ms |
40320 KB |
in18.txt |
WA |
110 ms |
40320 KB |
in19.txt |
WA |
85 ms |
25984 KB |
in2.txt |
WA |
97 ms |
34176 KB |
in20.txt |
AC |
84 ms |
25984 KB |
in21.txt |
AC |
102 ms |
36224 KB |
in22.txt |
AC |
90 ms |
32128 KB |
in23.txt |
AC |
104 ms |
40320 KB |
in24.txt |
AC |
105 ms |
40320 KB |
in25.txt |
WA |
22 ms |
9600 KB |
in26.txt |
WA |
21 ms |
9600 KB |
in27.txt |
AC |
20 ms |
9600 KB |
in28.txt |
WA |
23 ms |
9600 KB |
in3.txt |
AC |
71 ms |
17792 KB |
in4.txt |
WA |
111 ms |
42368 KB |
in5.txt |
WA |
99 ms |
40192 KB |
in6.txt |
WA |
108 ms |
40320 KB |
in7.txt |
WA |
59 ms |
14336 KB |
in8.txt |
AC |
3 ms |
2944 KB |
in9.txt |
AC |
98 ms |
34176 KB |
sample1.txt |
AC |
2 ms |
8320 KB |
sample2.txt |
AC |
1 ms |
2176 KB |
sample3.txt |
AC |
2 ms |
6272 KB |
sample4.txt |
AC |
2 ms |
8320 KB |
sub2in1.txt |
WA |
2 ms |
8448 KB |
sub2in10.txt |
WA |
2 ms |
8448 KB |
sub2in11.txt |
AC |
2 ms |
8320 KB |
sub2in12.txt |
WA |
2 ms |
8320 KB |
sub2in13.txt |
AC |
2 ms |
8448 KB |
sub2in14.txt |
WA |
2 ms |
8320 KB |
sub2in15.txt |
WA |
2 ms |
8320 KB |
sub2in16.txt |
WA |
2 ms |
8320 KB |
sub2in17.txt |
WA |
2 ms |
8320 KB |
sub2in18.txt |
AC |
2 ms |
8320 KB |
sub2in19.txt |
WA |
2 ms |
8320 KB |
sub2in2.txt |
WA |
2 ms |
8448 KB |
sub2in20.txt |
AC |
2 ms |
8320 KB |
sub2in21.txt |
AC |
2 ms |
8320 KB |
sub2in22.txt |
WA |
2 ms |
8320 KB |
sub2in23.txt |
AC |
2 ms |
8320 KB |
sub2in24.txt |
AC |
2 ms |
8320 KB |
sub2in3.txt |
AC |
2 ms |
8320 KB |
sub2in4.txt |
WA |
2 ms |
8320 KB |
sub2in5.txt |
WA |
2 ms |
8320 KB |
sub2in6.txt |
AC |
2 ms |
8320 KB |
sub2in7.txt |
AC |
1 ms |
2176 KB |
sub2in8.txt |
WA |
2 ms |
8448 KB |
sub2in9.txt |
AC |
2 ms |
8448 KB |
subin1.txt |
WA |
164 ms |
42368 KB |
subin10.txt |
WA |
179 ms |
50560 KB |
subin101.txt |
WA |
136 ms |
44416 KB |
subin102.txt |
WA |
105 ms |
36224 KB |
subin103.txt |
WA |
90 ms |
32128 KB |
subin104.txt |
WA |
92 ms |
32128 KB |
subin105.txt |
WA |
92 ms |
32128 KB |
subin106.txt |
WA |
87 ms |
32128 KB |
subin107.txt |
WA |
112 ms |
40320 KB |
subin108.txt |
WA |
113 ms |
40320 KB |
subin109.txt |
WA |
103 ms |
36224 KB |
subin11.txt |
WA |
176 ms |
50560 KB |
subin12.txt |
WA |
179 ms |
50560 KB |
subin13.txt |
WA |
180 ms |
50560 KB |
subin14.txt |
WA |
184 ms |
50560 KB |
subin15.txt |
WA |
136 ms |
32128 KB |
subin16.txt |
WA |
136 ms |
32128 KB |
subin17.txt |
WA |
111 ms |
23936 KB |
subin18.txt |
WA |
109 ms |
23936 KB |
subin19.txt |
WA |
111 ms |
23936 KB |
subin2.txt |
AC |
118 ms |
23936 KB |
subin20.txt |
WA |
112 ms |
23936 KB |
subin201.txt |
AC |
2 ms |
6272 KB |
subin21.txt |
WA |
25 ms |
9600 KB |
subin22.txt |
AC |
26 ms |
9600 KB |
subin23.txt |
WA |
27 ms |
9600 KB |
subin24.txt |
AC |
26 ms |
9600 KB |
subin3.txt |
WA |
184 ms |
50560 KB |
subin4.txt |
WA |
162 ms |
48384 KB |
subin5.txt |
WA |
170 ms |
48512 KB |
subin6.txt |
WA |
138 ms |
50560 KB |
subin7.txt |
AC |
4 ms |
3456 KB |
subin8.txt |
AC |
3 ms |
3072 KB |
subin9.txt |
AC |
183 ms |
50560 KB |