Submission #1866852
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;}
ll setv[maxn<<4];
void pushdown(int o) {
int lc=o<<1,rc=lc|1;
setv[lc]=setv[rc]=setv[o];
setv[o]=0;
}
void update(int x,int l,int r,int ql,int qr,int v) {
if(ql<=l&&r<=qr) setv[x]=v;
else {
int mid=l+r>>1,lc=x<<1,rc=lc|1;
if(setv[x]) pushdown(x);
if(ql<=mid) update(lc,l,mid,ql,qr,v);
if(qr>mid) update(rc,mid+1,r,ql,qr,v);
}
}
ll query(int x,int l,int r,int p) {
if(setv[x]) return setv[x];
if(l==r) return 0;
int mid=l+r>>1,lc=x<<1,rc=lc|1;
if(p<=mid) return query(lc,l,mid,p);
return query(rc,mid+1,r,p);
}
int cnt,ql[maxn],qr[maxn],L[maxn],R[maxn];
int Query(int p) {return query(1,1,cnt,p);}
ll tmp[maxn*4];
void prework() {
rep(i,1,n) tmp[++cnt]=p[i].xx,tmp[++cnt]=p[i].yy,tmp[++cnt]=add(p[i].xx,1),tmp[++cnt]=add(p[i].yy,-1);
sort(tmp+1,tmp+cnt+1);
rep(i,1,n) {
ql[i]=lower_bound(tmp+1,tmp+cnt+1,add(p[i].xx,1))-tmp;
qr[i]=lower_bound(tmp+1,tmp+cnt+1,add(p[i].yy,-1))-tmp;
L[i]=lower_bound(tmp+1,tmp+cnt+1,p[i].xx)-tmp;
R[i]=lower_bound(tmp+1,tmp+cnt+1,p[i].yy)-tmp;
}
}
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);
}
prework();
dwn(i,n,1) {
int j=Query(L[i]);
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(R[i]);
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=ql[i],r=qr[i];
if(l<=r) update(1,1,cnt,l,r,i);
else update(1,1,cnt,l,cnt,i),update(1,1,cnt,1,r,i);
}
}
ll res=1ll<<60;
memset(setv,0,sizeof(setv));
rep(i,1,n) {
if(!Query(L[i])) res=min(res,f[i]);
if(!Query(R[i])) res=min(res,g[i]);
if(B[i]==1) {
int l=ql[i],r=qr[i];
if(l<=r) update(1,1,cnt,l,r,i);
else update(1,1,cnt,l,cnt,i),update(1,1,cnt,1,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 |
1700 |
Code Size |
4728 Byte |
Status |
AC |
Exec Time |
164 ms |
Memory |
20864 KB |
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 |
6 ms |
18688 KB |
in10.txt |
AC |
130 ms |
20864 KB |
in101.txt |
AC |
102 ms |
20864 KB |
in102.txt |
AC |
90 ms |
20864 KB |
in103.txt |
AC |
113 ms |
20864 KB |
in104.txt |
AC |
80 ms |
20864 KB |
in105.txt |
AC |
75 ms |
20864 KB |
in106.txt |
AC |
102 ms |
20864 KB |
in107.txt |
AC |
90 ms |
20864 KB |
in108.txt |
AC |
113 ms |
20864 KB |
in109.txt |
AC |
79 ms |
20864 KB |
in11.txt |
AC |
129 ms |
20864 KB |
in110.txt |
AC |
75 ms |
20864 KB |
in12.txt |
AC |
130 ms |
20864 KB |
in13.txt |
AC |
129 ms |
20864 KB |
in14.txt |
AC |
130 ms |
20864 KB |
in15.txt |
AC |
128 ms |
20864 KB |
in16.txt |
AC |
130 ms |
20864 KB |
in17.txt |
AC |
130 ms |
20864 KB |
in18.txt |
AC |
130 ms |
20864 KB |
in19.txt |
AC |
131 ms |
20864 KB |
in2.txt |
AC |
129 ms |
20864 KB |
in20.txt |
AC |
130 ms |
20864 KB |
in21.txt |
AC |
121 ms |
20864 KB |
in22.txt |
AC |
119 ms |
20864 KB |
in23.txt |
AC |
122 ms |
20864 KB |
in24.txt |
AC |
123 ms |
20864 KB |
in25.txt |
AC |
62 ms |
20864 KB |
in26.txt |
AC |
62 ms |
20864 KB |
in27.txt |
AC |
57 ms |
20864 KB |
in28.txt |
AC |
66 ms |
20864 KB |
in3.txt |
AC |
129 ms |
20864 KB |
in4.txt |
AC |
133 ms |
20864 KB |
in5.txt |
AC |
110 ms |
20864 KB |
in6.txt |
AC |
130 ms |
20864 KB |
in7.txt |
AC |
128 ms |
20864 KB |
in8.txt |
AC |
3 ms |
2304 KB |
in9.txt |
AC |
129 ms |
20864 KB |
sample1.txt |
AC |
5 ms |
18560 KB |
sample2.txt |
AC |
1 ms |
2176 KB |
sample3.txt |
AC |
4 ms |
18560 KB |
sample4.txt |
AC |
5 ms |
18560 KB |
sub2in1.txt |
AC |
5 ms |
18560 KB |
sub2in10.txt |
AC |
5 ms |
18560 KB |
sub2in11.txt |
AC |
5 ms |
18560 KB |
sub2in12.txt |
AC |
5 ms |
18560 KB |
sub2in13.txt |
AC |
5 ms |
18560 KB |
sub2in14.txt |
AC |
5 ms |
18560 KB |
sub2in15.txt |
AC |
5 ms |
18560 KB |
sub2in16.txt |
AC |
5 ms |
18560 KB |
sub2in17.txt |
AC |
5 ms |
18560 KB |
sub2in18.txt |
AC |
5 ms |
18560 KB |
sub2in19.txt |
AC |
5 ms |
18560 KB |
sub2in2.txt |
AC |
5 ms |
18560 KB |
sub2in20.txt |
AC |
5 ms |
18560 KB |
sub2in21.txt |
AC |
5 ms |
18560 KB |
sub2in22.txt |
AC |
5 ms |
18560 KB |
sub2in23.txt |
AC |
5 ms |
18560 KB |
sub2in24.txt |
AC |
5 ms |
18560 KB |
sub2in3.txt |
AC |
5 ms |
18560 KB |
sub2in4.txt |
AC |
5 ms |
18560 KB |
sub2in5.txt |
AC |
5 ms |
18560 KB |
sub2in6.txt |
AC |
5 ms |
18560 KB |
sub2in7.txt |
AC |
1 ms |
2176 KB |
sub2in8.txt |
AC |
5 ms |
18560 KB |
sub2in9.txt |
AC |
5 ms |
18560 KB |
subin1.txt |
AC |
162 ms |
20864 KB |
subin10.txt |
AC |
160 ms |
20864 KB |
subin101.txt |
AC |
128 ms |
20864 KB |
subin102.txt |
AC |
98 ms |
20864 KB |
subin103.txt |
AC |
94 ms |
20864 KB |
subin104.txt |
AC |
93 ms |
20864 KB |
subin105.txt |
AC |
89 ms |
20864 KB |
subin106.txt |
AC |
82 ms |
20864 KB |
subin107.txt |
AC |
102 ms |
20864 KB |
subin108.txt |
AC |
100 ms |
20864 KB |
subin109.txt |
AC |
97 ms |
20864 KB |
subin11.txt |
AC |
153 ms |
20864 KB |
subin12.txt |
AC |
157 ms |
20864 KB |
subin13.txt |
AC |
159 ms |
20864 KB |
subin14.txt |
AC |
161 ms |
20864 KB |
subin15.txt |
AC |
160 ms |
20864 KB |
subin16.txt |
AC |
164 ms |
20864 KB |
subin17.txt |
AC |
152 ms |
20864 KB |
subin18.txt |
AC |
156 ms |
20864 KB |
subin19.txt |
AC |
158 ms |
20864 KB |
subin2.txt |
AC |
162 ms |
20864 KB |
subin20.txt |
AC |
159 ms |
20864 KB |
subin201.txt |
AC |
5 ms |
18560 KB |
subin21.txt |
AC |
79 ms |
20864 KB |
subin22.txt |
AC |
79 ms |
20864 KB |
subin23.txt |
AC |
85 ms |
20864 KB |
subin24.txt |
AC |
82 ms |
20864 KB |
subin3.txt |
AC |
163 ms |
20864 KB |
subin4.txt |
AC |
139 ms |
20864 KB |
subin5.txt |
AC |
156 ms |
20864 KB |
subin6.txt |
AC |
109 ms |
20864 KB |
subin7.txt |
AC |
4 ms |
2560 KB |
subin8.txt |
AC |
3 ms |
2432 KB |
subin9.txt |
AC |
163 ms |
20864 KB |