Submission #1650145
Source Code Expand
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<bitset>
using namespace std;
typedef long long LL;
const int N=2e5+100;
//这题太神!
int gi() {
int w=0;bool q=1;char c=getchar();
while ((c<'0'||c>'9') && c!='-') c=getchar();
if (c=='-') q=0,c=getchar();
while (c>='0'&&c <= '9') w=w*10+c-'0',c=getchar();
return q? w:-w;
}
int L[N],R[N],x[N];
int e[N<<2];
LL f[N],g[N];
#define lc (i<<1)
#define rc (lc|1)
inline void build(int i,int l,int r,int t) {
e[i]=t;
if (l!=r) {
int mid=(l+r)>>1;
build(lc,l,mid,t);
build(rc,mid+1,r,t);
}
}
inline void modify(int i,int l,int r,int L,int R,int k) {
if (L<=l&&r<=R) e[i]=k;
else {
int mid=(l+r)>>1;
if (L<=mid) modify(lc,l,mid,L,R,k);
if (mid<R) modify(rc,mid+1,r,L,R,k);
}
}
inline int query(int i,int l,int r,int k) {
if (l==r) return e[i];
int mid=(l+r)>>1;
return min(e[i],k<=mid?query(lc,l,mid,k):query(rc,mid+1,r,k));
}
inline void add(int i,int l,int r,int L,int R) {
if (L<=l&&r<=R) e[i]++;
else {
int mid=(l+r)>>1;
if (L<=mid) add(lc,l,mid,L,R);
if (mid<R) add(rc,mid+1,r,L,R);
}
}
inline int Sum(int i,int l,int r,int k) {
if (l==r) return e[i];
int mid=(l+r)>>1;
return e[i]+(k<=mid?Sum(lc,l,mid,k):Sum(rc,mid+1,r,k));
}
int main()
{
int n=gi(),m=gi(),i,a,k,tp,sum=0,len=0;
LL ans=1LL<<60,S=0;
for (i=1;i<=n;i++) {
a=gi(),tp=gi();S+=a<<1;
if (tp==1&&a*2>m) return puts("-1"),0;
if (tp==2) L[i]=0,R[i]=m-1;
else L[i]=sum,R[i]=(sum-a*2%m+m)%m;
sum=(sum-a*2%m+m)%m;
x[++len]=L[i];
x[++len]=R[i];
}
sort(x+1,x+1+len);
len=unique(x+1,x+1+len)-x-1;
build(1,1,len,n+1);
for (i=n;i;i--) {
L[i]=lower_bound(x+1,x+1+len,L[i])-x;
R[i]=lower_bound(x+1,x+1+len,R[i])-x;
k=query(1,1,len,L[i]);
if (k!=n+1) f[i]=f[k]+(x[L[k]]-x[L[i]]+m)%m;
k=query(1,1,len,R[i]);
if (k!=n+1) g[i]=f[k]+(x[L[k]]-x[R[i]]+m)%m;
if (L[i]<=R[i]) {
if (R[i]<len) modify(1,1,len,R[i]+1,len,i);
if (L[i]>1) modify(1,1,len,1,L[i]-1,i);
} else if (R[i]+1<L[i]) modify(1,1,len,R[i]+1,L[i]-1,i);
}
build(1,1,len,0);
for (i=1;i<=n;i++) {
//if (Sum(1,1,len,L[i])==i-1)
// ans=min(ans,f[i]);
if (Sum(1,1,len,R[i])==i-1)
ans=min(ans,g[i]);
if (L[i]<=R[i]) add(1,1,len,L[i],R[i]);
else add(1,1,len,L[i],len),add(1,1,len,1,R[i]);
}
cout<<ans+S<<endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
F - Train Service Planning |
User |
laofu |
Language |
C++14 (GCC 5.4.1) |
Score |
1700 |
Code Size |
2538 Byte |
Status |
AC |
Exec Time |
130 ms |
Memory |
7680 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 |
3 ms |
4352 KB |
in10.txt |
AC |
78 ms |
7680 KB |
in101.txt |
AC |
57 ms |
5632 KB |
in102.txt |
AC |
54 ms |
5632 KB |
in103.txt |
AC |
54 ms |
5632 KB |
in104.txt |
AC |
54 ms |
7680 KB |
in105.txt |
AC |
50 ms |
7296 KB |
in106.txt |
AC |
55 ms |
5632 KB |
in107.txt |
AC |
55 ms |
5760 KB |
in108.txt |
AC |
54 ms |
5632 KB |
in109.txt |
AC |
52 ms |
7680 KB |
in11.txt |
AC |
80 ms |
7680 KB |
in110.txt |
AC |
51 ms |
7296 KB |
in12.txt |
AC |
78 ms |
7680 KB |
in13.txt |
AC |
81 ms |
7680 KB |
in14.txt |
AC |
78 ms |
7680 KB |
in15.txt |
AC |
78 ms |
7680 KB |
in16.txt |
AC |
76 ms |
7680 KB |
in17.txt |
AC |
83 ms |
7680 KB |
in18.txt |
AC |
77 ms |
7680 KB |
in19.txt |
AC |
81 ms |
7680 KB |
in2.txt |
AC |
79 ms |
7680 KB |
in20.txt |
AC |
84 ms |
7680 KB |
in21.txt |
AC |
63 ms |
7680 KB |
in22.txt |
AC |
61 ms |
7552 KB |
in23.txt |
AC |
65 ms |
7680 KB |
in24.txt |
AC |
70 ms |
7680 KB |
in25.txt |
AC |
22 ms |
5632 KB |
in26.txt |
AC |
22 ms |
5632 KB |
in27.txt |
AC |
21 ms |
5632 KB |
in28.txt |
AC |
23 ms |
5632 KB |
in3.txt |
AC |
78 ms |
7680 KB |
in4.txt |
AC |
86 ms |
7680 KB |
in5.txt |
AC |
67 ms |
5504 KB |
in6.txt |
AC |
77 ms |
7680 KB |
in7.txt |
AC |
76 ms |
5632 KB |
in8.txt |
AC |
8 ms |
2304 KB |
in9.txt |
AC |
86 ms |
7680 KB |
sample1.txt |
AC |
2 ms |
4352 KB |
sample2.txt |
AC |
2 ms |
256 KB |
sample3.txt |
AC |
2 ms |
4352 KB |
sample4.txt |
AC |
2 ms |
4352 KB |
sub2in1.txt |
AC |
2 ms |
4352 KB |
sub2in10.txt |
AC |
2 ms |
4352 KB |
sub2in11.txt |
AC |
2 ms |
4352 KB |
sub2in12.txt |
AC |
3 ms |
4352 KB |
sub2in13.txt |
AC |
3 ms |
4352 KB |
sub2in14.txt |
AC |
3 ms |
4352 KB |
sub2in15.txt |
AC |
3 ms |
4352 KB |
sub2in16.txt |
AC |
2 ms |
4352 KB |
sub2in17.txt |
AC |
2 ms |
4352 KB |
sub2in18.txt |
AC |
2 ms |
4352 KB |
sub2in19.txt |
AC |
2 ms |
4352 KB |
sub2in2.txt |
AC |
2 ms |
4352 KB |
sub2in20.txt |
AC |
2 ms |
4352 KB |
sub2in21.txt |
AC |
2 ms |
4352 KB |
sub2in22.txt |
AC |
2 ms |
4352 KB |
sub2in23.txt |
AC |
2 ms |
4352 KB |
sub2in24.txt |
AC |
2 ms |
4352 KB |
sub2in3.txt |
AC |
2 ms |
4352 KB |
sub2in4.txt |
AC |
2 ms |
4352 KB |
sub2in5.txt |
AC |
2 ms |
4352 KB |
sub2in6.txt |
AC |
2 ms |
4352 KB |
sub2in7.txt |
AC |
2 ms |
2304 KB |
sub2in8.txt |
AC |
3 ms |
4352 KB |
sub2in9.txt |
AC |
3 ms |
4352 KB |
subin1.txt |
AC |
126 ms |
7680 KB |
subin10.txt |
AC |
130 ms |
7680 KB |
subin101.txt |
AC |
80 ms |
7680 KB |
subin102.txt |
AC |
67 ms |
7424 KB |
subin103.txt |
AC |
66 ms |
7424 KB |
subin104.txt |
AC |
64 ms |
7040 KB |
subin105.txt |
AC |
55 ms |
7680 KB |
subin106.txt |
AC |
54 ms |
6400 KB |
subin107.txt |
AC |
66 ms |
7168 KB |
subin108.txt |
AC |
74 ms |
7680 KB |
subin109.txt |
AC |
66 ms |
7552 KB |
subin11.txt |
AC |
116 ms |
7680 KB |
subin12.txt |
AC |
118 ms |
7680 KB |
subin13.txt |
AC |
126 ms |
7680 KB |
subin14.txt |
AC |
123 ms |
7680 KB |
subin15.txt |
AC |
124 ms |
7680 KB |
subin16.txt |
AC |
121 ms |
7680 KB |
subin17.txt |
AC |
112 ms |
7680 KB |
subin18.txt |
AC |
115 ms |
7680 KB |
subin19.txt |
AC |
123 ms |
7680 KB |
subin2.txt |
AC |
123 ms |
7680 KB |
subin20.txt |
AC |
127 ms |
7680 KB |
subin201.txt |
AC |
2 ms |
4352 KB |
subin21.txt |
AC |
21 ms |
5632 KB |
subin22.txt |
AC |
21 ms |
5632 KB |
subin23.txt |
AC |
22 ms |
5632 KB |
subin24.txt |
AC |
22 ms |
5632 KB |
subin3.txt |
AC |
127 ms |
7680 KB |
subin4.txt |
AC |
112 ms |
7552 KB |
subin5.txt |
AC |
118 ms |
7680 KB |
subin6.txt |
AC |
83 ms |
7552 KB |
subin7.txt |
AC |
11 ms |
2304 KB |
subin8.txt |
AC |
8 ms |
2304 KB |
subin9.txt |
AC |
126 ms |
7680 KB |