记录编号	559288	评测结果	AAAAAAAAAAAAAAAATTTT
题目名称	[NOIP 2020]微信步数	最终得分	80
用户昵称	op_组撒头屯	是否通过	未通过
代码语言	C++	运行时间	5.834 s
提交时间	2021-02-27 14:15:25	内存使用	11.64 MiB

#include <bits/stdc++.h>
using namespace std;
const int N=5*100000+5;
const int K=10+5;
const int mod=1000000007;
int n,k;
long long ans=0;
int w[K],l[N],r[N],p[N]={0},v[N]={0};;
int c[N],d[N],num[N]={0};
int main(){
	freopen ("2020walk.in","r",stdin);
	freopen ("2020walk.out","w",stdout);
	cin>>n>>k;
	for (int i=1;i<=k;i++){
		cin>>w[i];
	}
	for (int i=1;i<=n;i++){
		scanf("%d%d",&c[i],&d[i]);
		v[c[i]]+=d[i];
	}
	bool out=0;
	for (int i=1;i<=n;i++){
		p[c[i]]+=d[i];
		if (p[c[i]]<l[c[i]]||p[c[i]]>r[c[i]]){
			l[c[i]]=min(l[c[i]],p[c[i]]);
			r[c[i]]=max(r[c[i]],p[c[i]]);
			long long t=i;
			for (int j=1;j<=k;j++){
				if (j==c[i])continue;
				t=(t*(w[j]+l[j]-r[j])%mod)%mod;
			}
			//cout<<t<<endl;
			ans=(ans+t)%mod;
		}
		if (w[c[i]]+l[c[i]]-r[c[i]]<=0){
			cout<<ans<<endl;
			return 0;
		}
	}
	bool ok=0;
	for (int i=1;i<=k;i++){
		if (p[i]!=0){
			ok=1;break;
		}
	}
	if (ok==0){
		cout<<-1<<endl;
		return 0;
	}
//	for (int i=1;i<=k;i++){
//		cout<<l[i]<<" "<<r[i]<<endl;
//	}
//	return 0;
	for (int i=1;i<=n;i++){
		out=0;
		p[c[i]]+=d[i];
		if (p[c[i]]<l[c[i]]||p[c[i]]>r[c[i]]){
			for (int j=1;j<=k;j++)num[j]=w[j]+l[j]-r[j];
			for (int x=1;;x++){
				long long t=i+x*n;
				for (int j=1;j<=k;j++){
					if (j==c[i])continue;
					t=(t*num[j])%mod;
				}
				//cout<<i<<" "<<x<<" "<<t<<endl;
				ans=(ans+t)%mod;
				for (int j=1;j<=k;j++){
					num[j]-=abs(v[j]);
					if (num[j]<=0){
						out=1;break;
					}
				}
				if (out==1)break;
			}
			l[c[i]]=min(l[c[i]],p[c[i]]);
			r[c[i]]=max(r[c[i]],p[c[i]]);
		}
		if (w[c[i]]+l[c[i]]-r[c[i]]<=0)break;
	}
	cout<<ans%mod<<endl;
	return 0;
}