Submission #1692016

---

Source Code Expand

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

template<typename T>inline void check_min(T a,T &b){if(a<b)b=a;}

namespace diaoye_chicken_dinner
{
	typedef long long ll;
	const int N=101000,M=N*30,INF=2147483647;

	int n,m,K;
	
	struct segment_treeeeee
	{
#define lt (st[p][0])
#define rt (st[p][1])
#define mid ((L+R)>>1)
#define lts lt,L,mid
#define rts rt,mid+1,R
#define dog T.root
		int st[M][2];
		int w[M];
		int e,root;
		void init(){w[root=e=1]=INF;}
		void init_s(){w[root=e=1]=0;st[1][0]=st[1][1]=0;}
		int check(int &p){if(p)return p;p=++e;w[p]=INF;return p;}
		int check_s(int &p){if(p)return p;p=++e;w[p]=0;lt=rt=0;return p;}
		void modify(int s,int t,int x,int &p,int L=0,int R=K-1)
		{
			p=check(p);
			if(s<=L && t>=R){check_min(x,w[p]);return;}
			if(s<=mid)modify(s,t,x,lts);
			if(t>mid)modify(s,t,x,rts);
		}
		int query(int x,int &p,int L=0,int R=K-1)
		{
			p=check(p);
			if(L==R)return w[p];
			int ret=w[p];
			if(x<=mid)check_min(query(x,lts),ret);
			else check_min(query(x,rts),ret);
			return ret;
		}
		void inc(int s,int t,int &p,int L=0,int R=K-1)
		{
			p=check_s(p);
			if(s<=L && t>=R){w[p]++;return;}
			if(s<=mid)inc(s,t,lts);
			if(t>mid)inc(s,t,rts);
		}
		int query_s(int x,int &p,int L=0,int R=K-1)
		{
			p=check_s(p);
			if(L==R)return w[p];
			int ret=w[p];
			if(x<=mid)ret+=query_s(x,lts);
			else ret+=query_s(x,rts);
			return ret;
		}
	}T;

	ll tx[N],ty[N],ans;
	int A[N],B[N],L[N],R[N];

	bool initialize()
	{
		scanf("%d%d",&n,&K),ans=m=0;
		for(int i=1;i<=n;i++)
		{
			scanf("%d%d",A+i,B+i),ans+=A[i];
			if(B[i]==1 && A[i]*2>K)return 0;
		}
		for(int i=1;i<=n;i++)tx[i+1]=tx[i]+A[i];
		for(int i=n-1;i;i--)ty[i]=ty[i+1]+A[i+1];

		for(int i=n;i;i--)
		{
			if(B[i]==2)continue;
			m++;
			ll tmp=ty[i],s,t;
			s=(tx[i]+A[i])%K;
			t=((tx[i]-A[i])%K+K)%K;
			L[m]=((s-tmp)%K+K)%K;
			R[m]=((t-tmp)%K+K)%K;
		}
		return 1;
	}
	ll fl[N],fr[N];
	bool check_in(int x,int l,int r)
	{
		if(l<=r)return x>=l && x<=r;
		return x<=r || x>=l;
	}
	void work()
	{
		T.init();
		for(int i=m,j;i;i--)
		{
			j=T.query(L[i],dog);
			fl[i]=(j==INF)?0:(fl[j]+(L[j]-L[i]+K)%K);
			j=T.query(R[i],dog);
			fr[i]=(j==INF)?0:(fl[j]+(L[j]-R[i]+K)%K);

			if(L[i]<=R[i])
			{
				if(L[i])T.modify(0,L[i]-1,i,dog);
				if(R[i]<K-1)T.modify(R[i]+1,K-1,i,dog);
			}
			else if(R[i]+1<=L[i]-1)T.modify(R[i]+1,L[i]-1,i,dog);
		}
	}
	void solve()
	{
		if(!initialize()){printf("-1\n");return;}

//		for(int i=1;i<=m;i++)printf("%d---%d\n",L[i],R[i]);

		work();

//		for(int i=1;i<=m;i++)printf("%lld , %lld\n",fl[i],fr[i]);

		ll ret=INF*100000000ll;

		T.init_s();
		for(int i=1;i<=m;i++)
		{
//			printf(":%d %d\n",T.query_s(L[i],dog),T.query_s(R[i],dog));
			if(T.query_s(L[i],dog)==i-1)check_min(fl[i],ret);
			if(T.query_s(R[i],dog)==i-1)check_min(fr[i],ret);

			if(L[i]<=R[i])T.inc(L[i],R[i],dog);
			else T.inc(0,R[i],dog),T.inc(L[i],K-1,dog);
		}
		printf("%lld\n",ans*2+ret);
	}
}

int main()
{
//	freopen("F.in","r",stdin);
//	freopen("F.out","w",stdout);
	diaoye_chicken_dinner::solve();
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘bool diaoye_chicken_dinner::initialize()’:
./Main.cpp:69:30: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&n,&K),ans=m=0;
                              ^
./Main.cpp:72:35: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d%d",A+i,B+i),ans+=A[i];
                                   ^

Judge Result