Submission #8614933


Source Code Expand

Copy
//quming
#include<bits/stdc++.h>
#define R register
#define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i)
#define fd(i,a,b) for(R int i=(a),I=(b)-1;i>I;--i)
#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)
template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}
template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}
using namespace std;
char buf[1<<21],*p1=buf,*p2=buf;
inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
int read(){
    R int res,f=1;R char ch;
    while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);
    for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');
    return res*f;
}
int read(char *s){
    R int len=0;R char ch;while(((ch=getc())>'9'||ch<'0'));
    for(s[++len]=ch;(ch=getc())>='0'&&ch<='9';s[++len]=ch);
    return s[len+1]='\0',len;
}
double readdb()
{
    R double x=0,y=0.1,f=1;R char ch;
    while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);
    for(x=ch-'0';(ch=getc())>='0'&&ch<='9';x=x*10+ch-'0');
    for(ch=='.'&&(ch=getc());ch>='0'&&ch<='9';x+=(ch-'0')*y,y*=0.1,ch=getc());
    return x*f;
}
char sr[1<<21],z[20];int C=-1,Z=0;
inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;}
void print(R int x){
    if(C>1<<20)Ot();if(x<0)sr[++C]='-',x=-x;
    while(z[++Z]=x%10+48,x/=10);
    while(sr[++C]=z[Z],--Z);sr[++C]='\n';
}
int P;
inline void upd(R int &x,R int y){(x+=y)>=P?x-=P:0;}
inline int inc(R int x,R int y){return x+y>=P?x+y-P:x+y;}
inline int dec(R int x,R int y){return x-y<0?x-y+P:x-y;}
inline int mul(R int x,R int y){return 1ll*x*y-1ll*x*y/P*P;}
int ksm(R int x,R int y){
	R int res=1;
	for(;y;y>>=1,x=mul(x,x))(y&1)?res=mul(res,x):0;
	return res;
}
const int N=2e5+5;
typedef long long ll;
map<int,int>mp,mmp;int a[N],n;ll res;
int main(){
	scanf("%d%d",&n,&P);
	if(P==1)return puts("0"),0;
	fp(i,1,n)scanf("%d",&a[i]),a[i]%=P,upd(a[i],a[i-1]);
	fp(i,1,n)a[i]-=i;
	mp[0]=1;
	fp(i,1,n){
		res+=mp[a[i]];
		res+=mp[a[i]+P]-mmp[a[i]+P];
		++mp[a[i]];
		if(i-P+1>=0)++mmp[a[i-P+1]];
	}
	printf("%lld\n",res);
	return 0;
}

Submission Info

Submission Time
Task E - Rem of Sum is Num
User yuanquming
Language C++14 (GCC 5.4.1)
Score 500
Code Size 2116 Byte
Status AC
Exec Time 300 ms
Memory 29184 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:52:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&P);
                     ^
./Main.cpp:54:53: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  fp(i,1,n)scanf("%d",&a[i]),a[i]%=P,upd(a[i],a[i-1]);
                                                     ^

Judge Result

Set Name sample All
Score / Max Score 0 / 0 500 / 500
Status
AC × 3
AC × 29
Set Name Test Cases
sample sample01, sample02, sample03
All few01, few02, few03, hand01, hand02, hand03, hand04, large01, large02, large03, max01, max02, max03, mid01, mid02, mid03, mid04, mid05, min01, min02, min03, sample01, sample02, sample03, small01, small02, small03, small04, small05
Case Name Status Exec Time Memory
few01 AC 20 ms 1024 KB
few02 AC 27 ms 1024 KB
few03 AC 27 ms 1024 KB
hand01 AC 1 ms 256 KB
hand02 AC 1 ms 256 KB
hand03 AC 196 ms 18560 KB
hand04 AC 29 ms 1024 KB
large01 AC 254 ms 26496 KB
large02 AC 294 ms 29056 KB
large03 AC 300 ms 28160 KB
max01 AC 188 ms 29184 KB
max02 AC 186 ms 29184 KB
max03 AC 247 ms 29184 KB
mid01 AC 2 ms 384 KB
mid02 AC 3 ms 512 KB
mid03 AC 3 ms 512 KB
mid04 AC 2 ms 384 KB
mid05 AC 3 ms 512 KB
min01 AC 103 ms 12544 KB
min02 AC 95 ms 12032 KB
min03 AC 106 ms 12928 KB
sample01 AC 1 ms 256 KB
sample02 AC 1 ms 256 KB
sample03 AC 1 ms 256 KB
small01 AC 1 ms 256 KB
small02 AC 1 ms 256 KB
small03 AC 1 ms 256 KB
small04 AC 1 ms 256 KB
small05 AC 1 ms 256 KB