Main » 2013 September 23 » [noip模拟赛]TASTYD
4:27 PM [noip模拟赛]TASTYD |
#include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> #define N 200100 #define FOR(i,a,b) for(i=(a);i<=(b);i++) #define ROF(i,a,b) for(i=(a);i>=(b);i--) #define mp(a,b) make_pair((a),(b)) #define INF 2147000000 using namespace std; int l[N],r[N],n,k,tot[N]; long long a[N],s[N]; long long ans=0; pair<int,int> b[N]; long long calc(int l,int r,int x) { if (l>r) return 0; return (long long)(upper_bound(b,b+n+2,mp(x,r))-lower_bound(b,b+n+2,mp(x,l))); } void solve(int x) { ans--;l[x]++;r[x]--; if (l[x]==x) { int t=s[x-1]+a[x]; if (t>=k) t-=k; ans+=calc(x,r[x],t); }else if (r[x]==x) { int t=s[x]-a[x]; if (t<0) t+=k; ans+=calc(l[x]-1,x-1,t); }else if (x-l[x]<=r[x]-x) { int i; FOR(i,l[x],x) { int t=s[i-1]+a[x]; if (t>=k) t-=k; ans+=calc(x,r[x],t); } }else { int i; FOR(i,x,r[x]) { int t=s[i]-a[x]; if (t<0) t+=k; ans+=calc(l[x]-1,x-1,t); } } } int main() { freopen("TASTYD.in","r",stdin); freopen("TASTYD.out","w",stdout); scanf("%d %d",&n,&k); int i,j; FOR(i,1,n) {scanf("%d",&a[i]);r[i]=n+1;} FOR(i,1,n) { for (j=i-1;a[j]>a[i];j=l[j]) r[j]=i; l[i]=j; } s[0]=0;b[0]=mp(-INF,0);b[1]=mp(s[i],1);b[n+1]=mp(INF,n+1); FOR(i,1,n) a[i]%=k; FOR(i,1,n) {s[i]=(s[i-1]+a[i])%k;b[i]=mp(s[i],i);} sort(b,b+n+2); FOR(i,1,n) solve(i); printf("%lld\n",ans); }
|
|
|
| Total comments: 0 | |