Submission #3679762


Source Code Expand

Copy
#include<bits/stdc++.h>
using namespace std;
const int MX=1048576,MB=20;
typedef long long LL;
int n,q,a[MX];
int readch(){
	char c=getchar();
	while(c==' '||c=='\n') c=getchar();
	if(c=='D') return 1;
	if(c=='M') return 2;
	if(c=='C') return 3;
}
struct data{
	int c0,c1;
	LL pr;
	void init(){
		c0=c1=0;
		pr=0ll;
	}
};
data merge(data A,data B){
	data R;
	R.c0=A.c0+B.c0;
	R.c1=A.c1+B.c1;
	R.pr=A.pr+B.pr+(LL)A.c0*(LL)B.c1;
	return R;
}
vector < data > t[5000005];
int lp[5000005],rp[5000005],AD;
void init(int p,int l=0,int r=MX-1){
	if(!l && !r) AD=p;
	lp[p]=l;
	rp[p]=r;
	t[p].resize(r-l+1);
	if(l==r){
		t[p][0].c0=(a[l]==2);
		t[p][0].c1=(a[l]==3);
		t[p][0].pr=0ll;
	}
	else{
		int M=(l+r)>>1,i;
		init((p<<1),l,M);
		init((p<<1|1),M+1,r);
		for(i=l;i<r;++i){
			t[p][i-l].c0=(a[i]==2);
			t[p][i-l].c1=(a[i]==3);
			t[p][i-l].pr=0ll;
		}
		for(i=M-1;i>=l;--i){
			t[p][i-l]=merge(t[p][i-l],t[p][i-l+1]);
		}
		for(i=M+2;i<=r;++i){
			t[p][i-l]=merge(t[p][i-l-1],t[p][i-l]);
		}
	}
}
LL qry(int l,int r){
//	r=min(r,n-1);
	LL ret=0ll;
	int ln=__builtin_clz(l+AD^r+AD)-11;
	int p=(1<<ln)-1&(l+AD>>MB-ln+1);
//	printf("p=%d AD=%d %d %d %d\n",p,AD,l,r,ln);
	return merge(t[p][l-lp[p]],t[p][r-lp[p]]).pr;
}
LL solve(int L){
	int i,j,k;
	LL ret=0ll;
	for(i=0;i<n;++i){
		if(a[i]==1){
			ret+=qry(i+1,i+L-1);
		}
	}
	return ret;
}
int main(){
	int i,j,k;
	scanf("%d",&n);
	for(i=0;i<n;++i){
		a[i]=readch();
	}
	init(1);
	scanf("%d",&q);
	while(q--){
		scanf("%d",&k);
		printf("%lld\n",solve(k));
	}
	return 0;
}

Submission Info

Submission Time
Task C - k-DMC
User shadowsocks
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1603 Byte
Status

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:77:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^
./Main.cpp:82:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&q);
                ^
./Main.cpp:84:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&k);
                 ^

Test Cases

Set Name Score / Max Score Test Cases
All 0 / 600 dmc-dmc-00, dmc-dmc-01, dmc-dmc-02, dmc-dmc-03, dmc-dmc-04, dmc-large-00, dmc-large-01, dmc-large-02, dmc-large-03, dmc-large-04, dmc-random-00, dmc-random-01, dmc-random-02, dmc-random-03, dmc-random-04, dmc-special-00, dmc-special-01, dmc-special-02, dmc-special-03, sample_01, sample_02, sample_03, sample_04
Case Name Status Exec Time Memory
dmc-dmc-00
dmc-dmc-01
dmc-dmc-02
dmc-dmc-03
dmc-dmc-04
dmc-large-00
dmc-large-01
dmc-large-02
dmc-large-03
dmc-large-04
dmc-random-00
dmc-random-01
dmc-random-02
dmc-random-03
dmc-random-04 611 ms 519424 KB
dmc-special-00 629 ms 519808 KB
dmc-special-01
dmc-special-02
dmc-special-03 612 ms 519808 KB
sample_01 553 ms 517376 KB
sample_02 553 ms 517376 KB
sample_03 555 ms 517376 KB
sample_04 555 ms 517376 KB