Submission #1776761
Source Code Expand
#include <bits/stdc++.h> #define N 200010 using namespace std; typedef long long ll; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();} return x*f; } int n,K,L[N],R[N],A[N],sl[N],cnt,Rt,B[N]; int tree[N*20],tot,ls[N*20],rs[N*20]; ll Ans,F[N]; //问题转化后,表示在第i转移之后站在第i个区间的最右端,还需走多少步能使选择合法 inline void deal(int &x,int y) { if(!x) x=++tot; tree[x]=y; } inline void pushdown(int x) { if(tree[x]) { deal(ls[x],tree[x]); deal(rs[x],tree[x]); tree[x]=0; } } inline int query(int x,int l,int r,int &rt) { if(!rt) rt=++tot; if(l==r||tree[rt]) return tree[rt]; int mid=(l+r)>>1; pushdown(rt); if(x>mid) return query(x,mid+1,r,rs[rt]); else return query(x,l,mid,ls[rt]); } inline void updata(int L,int R,int x,int l,int r,int &rt) { if(L>R) return ; if(!rt) rt=++tot; if(L<=l&&r<=R) { deal(rt,x); return ; } int mid=(l+r)>>1; pushdown(rt); if(R>mid) updata(L,R,x,mid+1,r,rs[rt]); if(L<=mid) updata(L,R,x,l,mid,ls[rt]); } inline int calc(int l,int r,int x) { if(l<=x&&x<=r) return 0; return (l-x+K)%K; } inline void solve(int l,int r,int rt) { if(tree[rt]) { Ans=min(Ans,F[tree[rt]]+(tree[rt]>cnt?0: calc(l,r,R[tree[rt]]))); return ; } if(!rt||l==r) return ; int mid=(l+r)>>1; solve(l,mid,ls[rt]); solve(mid+1,r,rs[rt]); } int main() { n=read(); K=read(); ll all=0; Ans=100000000000000ll; for(int i=1;i<=n;i++) { int x=read(), y=read(); x<<=1; all+=x; if(y==1) { if(x>K) {puts("-1"); return 0;} ++cnt; L[cnt]=all%K; R[cnt]=((all-x)%K+K)%K; //cout << L[cnt] << " " << R[cnt] << endl; } } deal(Rt,cnt+1); for(int i=cnt;i;i--) { int tx=query(R[i],0,K-1,Rt); F[i]=tx>cnt? 0: F[tx]+(R[i]-R[tx]+K)%K; if(L[i]<R[i]) { if(L[i]) updata(0,L[i]-1,i,0,K-1,Rt); if(R[i]<K-1) updata(R[i]+1,K-1,i,0,K-1,Rt); } else updata(R[i]+1,L[i]-1,i,0,K-1,Rt); } solve(0,K-1,Rt); cout << Ans+all << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | F - Train Service Planning |
User | wcz111 |
Language | C++14 (GCC 5.4.1) |
Score | 500 |
Code Size | 2144 Byte |
Status | WA |
Exec Time | 91 ms |
Memory | 38784 KB |
Judge Result
Set Name | Sample | All | subtask | subtask2 | ||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 700 | 500 / 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 | 6528 KB |
in10.txt | AC | 39 ms | 13568 KB |
in101.txt | AC | 37 ms | 11520 KB |
in102.txt | AC | 36 ms | 15616 KB |
in103.txt | AC | 37 ms | 9472 KB |
in104.txt | AC | 39 ms | 19712 KB |
in105.txt | AC | 33 ms | 19712 KB |
in106.txt | AC | 36 ms | 11520 KB |
in107.txt | AC | 36 ms | 15616 KB |
in108.txt | AC | 36 ms | 9472 KB |
in109.txt | AC | 40 ms | 19712 KB |
in11.txt | AC | 56 ms | 29952 KB |
in110.txt | AC | 33 ms | 21760 KB |
in12.txt | AC | 50 ms | 23808 KB |
in13.txt | AC | 37 ms | 13568 KB |
in14.txt | AC | 54 ms | 29952 KB |
in15.txt | AC | 54 ms | 29952 KB |
in16.txt | AC | 54 ms | 29952 KB |
in17.txt | AC | 55 ms | 29952 KB |
in18.txt | AC | 54 ms | 29952 KB |
in19.txt | AC | 42 ms | 17664 KB |
in2.txt | AC | 50 ms | 23808 KB |
in20.txt | AC | 44 ms | 17664 KB |
in21.txt | AC | 61 ms | 29952 KB |
in22.txt | AC | 57 ms | 27904 KB |
in23.txt | AC | 61 ms | 29952 KB |
in24.txt | AC | 58 ms | 29952 KB |
in25.txt | AC | 14 ms | 7040 KB |
in26.txt | AC | 14 ms | 7040 KB |
in27.txt | AC | 14 ms | 7040 KB |
in28.txt | AC | 15 ms | 7040 KB |
in3.txt | AC | 38 ms | 13568 KB |
in4.txt | AC | 56 ms | 29952 KB |
in5.txt | AC | 47 ms | 27904 KB |
in6.txt | AC | 51 ms | 27904 KB |
in7.txt | AC | 32 ms | 9472 KB |
in8.txt | AC | 8 ms | 2432 KB |
in9.txt | AC | 50 ms | 23808 KB |
sample1.txt | AC | 2 ms | 6400 KB |
sample2.txt | AC | 1 ms | 256 KB |
sample3.txt | AC | 2 ms | 6400 KB |
sample4.txt | AC | 2 ms | 6400 KB |
sub2in1.txt | AC | 2 ms | 6400 KB |
sub2in10.txt | AC | 2 ms | 6400 KB |
sub2in11.txt | AC | 2 ms | 6400 KB |
sub2in12.txt | AC | 2 ms | 6400 KB |
sub2in13.txt | AC | 2 ms | 6400 KB |
sub2in14.txt | AC | 2 ms | 6400 KB |
sub2in15.txt | AC | 2 ms | 6400 KB |
sub2in16.txt | AC | 2 ms | 6400 KB |
sub2in17.txt | AC | 2 ms | 6400 KB |
sub2in18.txt | AC | 2 ms | 6400 KB |
sub2in19.txt | AC | 2 ms | 6400 KB |
sub2in2.txt | AC | 3 ms | 6400 KB |
sub2in20.txt | AC | 2 ms | 6400 KB |
sub2in21.txt | AC | 2 ms | 6400 KB |
sub2in22.txt | AC | 2 ms | 6400 KB |
sub2in23.txt | WA | 3 ms | 6400 KB |
sub2in24.txt | AC | 2 ms | 6400 KB |
sub2in3.txt | AC | 2 ms | 6400 KB |
sub2in4.txt | AC | 2 ms | 6400 KB |
sub2in5.txt | AC | 3 ms | 6400 KB |
sub2in6.txt | AC | 2 ms | 6400 KB |
sub2in7.txt | AC | 2 ms | 2304 KB |
sub2in8.txt | AC | 3 ms | 6400 KB |
sub2in9.txt | AC | 3 ms | 6400 KB |
subin1.txt | AC | 83 ms | 32640 KB |
subin10.txt | AC | 90 ms | 38784 KB |
subin101.txt | AC | 73 ms | 34688 KB |
subin102.txt | AC | 58 ms | 26496 KB |
subin103.txt | AC | 54 ms | 22400 KB |
subin104.txt | AC | 49 ms | 22400 KB |
subin105.txt | AC | 56 ms | 24448 KB |
subin106.txt | AC | 45 ms | 24448 KB |
subin107.txt | AC | 59 ms | 28544 KB |
subin108.txt | AC | 64 ms | 28672 KB |
subin109.txt | AC | 58 ms | 26496 KB |
subin11.txt | AC | 87 ms | 38784 KB |
subin12.txt | AC | 88 ms | 38784 KB |
subin13.txt | AC | 89 ms | 38784 KB |
subin14.txt | AC | 89 ms | 38784 KB |
subin15.txt | AC | 69 ms | 24448 KB |
subin16.txt | AC | 70 ms | 24448 KB |
subin17.txt | AC | 54 ms | 16256 KB |
subin18.txt | AC | 56 ms | 16256 KB |
subin19.txt | AC | 57 ms | 16256 KB |
subin2.txt | AC | 60 ms | 16256 KB |
subin20.txt | AC | 60 ms | 16256 KB |
subin201.txt | AC | 2 ms | 6400 KB |
subin21.txt | AC | 16 ms | 7552 KB |
subin22.txt | AC | 17 ms | 7552 KB |
subin23.txt | AC | 17 ms | 7552 KB |
subin24.txt | AC | 17 ms | 7552 KB |
subin3.txt | AC | 91 ms | 38784 KB |
subin4.txt | AC | 78 ms | 34560 KB |
subin5.txt | AC | 89 ms | 36736 KB |
subin6.txt | AC | 74 ms | 38784 KB |
subin7.txt | AC | 13 ms | 2688 KB |
subin8.txt | AC | 8 ms | 2560 KB |
subin9.txt | AC | 91 ms | 38784 KB |