Submission #1866819
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) {
int ok1=1,ok2=1;
rep(j,1,i-1) {
if(B[j]==1&&in(p[i].xx,add(p[j].xx,1),add(p[j].yy,-1))) ok1=0;
if(B[j]==1&&in(p[i].yy,add(p[j].xx,1),add(p[j].yy,-1))) ok2=0;
if((!ok1)&&(!ok2)) break;
}
if(ok1) res=min(res,f[i]);
if(ok2) res=min(res,g[i]);
/*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 |
500 |
Code Size |
4813 Byte |
Status |
TLE |
Exec Time |
2104 ms |
Memory |
50560 KB |
Judge Result
Set Name |
Sample |
All |
subtask |
subtask2 |
Score / Max Score |
0 / 0 |
0 / 700 |
0 / 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 |
8448 KB |
in10.txt |
AC |
51 ms |
17792 KB |
in101.txt |
TLE |
2103 ms |
17536 KB |
in102.txt |
TLE |
2103 ms |
23936 KB |
in103.txt |
TLE |
2103 ms |
14464 KB |
in104.txt |
TLE |
2103 ms |
25984 KB |
in105.txt |
TLE |
2103 ms |
25984 KB |
in106.txt |
TLE |
2103 ms |
17536 KB |
in107.txt |
TLE |
2103 ms |
23936 KB |
in108.txt |
TLE |
2103 ms |
14464 KB |
in109.txt |
TLE |
2103 ms |
28032 KB |
in11.txt |
AC |
81 ms |
40320 KB |
in110.txt |
TLE |
2103 ms |
28032 KB |
in12.txt |
AC |
90 ms |
34176 KB |
in13.txt |
AC |
74 ms |
17792 KB |
in14.txt |
AC |
102 ms |
40320 KB |
in15.txt |
AC |
313 ms |
40320 KB |
in16.txt |
AC |
204 ms |
42368 KB |
in17.txt |
AC |
128 ms |
40320 KB |
in18.txt |
AC |
121 ms |
40320 KB |
in19.txt |
AC |
128 ms |
25984 KB |
in2.txt |
AC |
76 ms |
34176 KB |
in20.txt |
AC |
92 ms |
25984 KB |
in21.txt |
TLE |
2103 ms |
36224 KB |
in22.txt |
TLE |
2103 ms |
32128 KB |
in23.txt |
TLE |
2103 ms |
40320 KB |
in24.txt |
TLE |
2103 ms |
40320 KB |
in25.txt |
AC |
30 ms |
9600 KB |
in26.txt |
AC |
36 ms |
9600 KB |
in27.txt |
AC |
38 ms |
9600 KB |
in28.txt |
AC |
36 ms |
9600 KB |
in3.txt |
AC |
53 ms |
17792 KB |
in4.txt |
AC |
83 ms |
42368 KB |
in5.txt |
AC |
75 ms |
40064 KB |
in6.txt |
AC |
198 ms |
40320 KB |
in7.txt |
AC |
48 ms |
14336 KB |
in8.txt |
AC |
7 ms |
2944 KB |
in9.txt |
AC |
74 ms |
34176 KB |
sample1.txt |
AC |
3 ms |
8320 KB |
sample2.txt |
AC |
1 ms |
2176 KB |
sample3.txt |
AC |
2 ms |
6272 KB |
sample4.txt |
AC |
3 ms |
8320 KB |
sub2in1.txt |
AC |
3 ms |
8448 KB |
sub2in10.txt |
AC |
3 ms |
8320 KB |
sub2in11.txt |
AC |
3 ms |
8320 KB |
sub2in12.txt |
AC |
3 ms |
8320 KB |
sub2in13.txt |
AC |
3 ms |
8320 KB |
sub2in14.txt |
AC |
3 ms |
8320 KB |
sub2in15.txt |
AC |
3 ms |
8320 KB |
sub2in16.txt |
AC |
3 ms |
8320 KB |
sub2in17.txt |
AC |
3 ms |
8320 KB |
sub2in18.txt |
AC |
3 ms |
8320 KB |
sub2in19.txt |
AC |
3 ms |
8320 KB |
sub2in2.txt |
AC |
3 ms |
8448 KB |
sub2in20.txt |
AC |
3 ms |
8320 KB |
sub2in21.txt |
AC |
3 ms |
8320 KB |
sub2in22.txt |
AC |
3 ms |
8320 KB |
sub2in23.txt |
AC |
3 ms |
8320 KB |
sub2in24.txt |
AC |
3 ms |
8320 KB |
sub2in3.txt |
AC |
3 ms |
8320 KB |
sub2in4.txt |
AC |
3 ms |
8320 KB |
sub2in5.txt |
AC |
3 ms |
8320 KB |
sub2in6.txt |
AC |
3 ms |
8320 KB |
sub2in7.txt |
AC |
1 ms |
2176 KB |
sub2in8.txt |
AC |
3 ms |
8448 KB |
sub2in9.txt |
AC |
3 ms |
8448 KB |
subin1.txt |
AC |
113 ms |
42368 KB |
subin10.txt |
AC |
129 ms |
50560 KB |
subin101.txt |
AC |
460 ms |
44416 KB |
subin102.txt |
TLE |
2104 ms |
36224 KB |
subin103.txt |
TLE |
2104 ms |
32128 KB |
subin104.txt |
TLE |
2103 ms |
32128 KB |
subin105.txt |
TLE |
2103 ms |
32128 KB |
subin106.txt |
AC |
1313 ms |
32128 KB |
subin107.txt |
AC |
1374 ms |
40320 KB |
subin108.txt |
TLE |
2104 ms |
40320 KB |
subin109.txt |
TLE |
2103 ms |
36224 KB |
subin11.txt |
AC |
240 ms |
50560 KB |
subin12.txt |
AC |
175 ms |
50560 KB |
subin13.txt |
AC |
144 ms |
50560 KB |
subin14.txt |
AC |
144 ms |
50560 KB |
subin15.txt |
AC |
121 ms |
32128 KB |
subin16.txt |
AC |
111 ms |
32128 KB |
subin17.txt |
AC |
177 ms |
23936 KB |
subin18.txt |
AC |
131 ms |
23936 KB |
subin19.txt |
AC |
99 ms |
23936 KB |
subin2.txt |
AC |
81 ms |
23936 KB |
subin20.txt |
AC |
91 ms |
23936 KB |
subin201.txt |
AC |
2 ms |
6272 KB |
subin21.txt |
AC |
29 ms |
9600 KB |
subin22.txt |
AC |
36 ms |
9600 KB |
subin23.txt |
AC |
30 ms |
9600 KB |
subin24.txt |
AC |
26 ms |
9600 KB |
subin3.txt |
AC |
121 ms |
50560 KB |
subin4.txt |
AC |
104 ms |
48256 KB |
subin5.txt |
AC |
162 ms |
48512 KB |
subin6.txt |
TLE |
2104 ms |
50560 KB |
subin7.txt |
AC |
11 ms |
3456 KB |
subin8.txt |
AC |
7 ms |
3072 KB |
subin9.txt |
AC |
118 ms |
50560 KB |