実は参加してました。
D:
数え上げだし解法自明だったので解こうとしたが、変なケースがありはまった。WA*3がつらい。
#include<stdio.h> #include<algorithm> using namespace std; int b[110000]; long long fact[310000]; long long factinv[310000]; long long inv[310000]; pair<int,int> ev[310000]; int main(){ int a; int mod=1000000007; fact[0]=1; for(int i=1;i<310000;i++)fact[i]=fact[i-1]*i%mod; inv[1]=1; for(int i=2;i<310000;i++)inv[i]=(mod-(mod/i)*inv[mod%i]%mod); factinv[0]=1; for(int i=1;i<310000;i++)factinv[i]=factinv[i-1]*inv[i]%mod; scanf("%d",&a); for(int i=0;i<a;i++){ scanf("%d",b+i); } int best=9999999; int at=-1; for(int i=0;i<a;i++){ if(b[i]&&best>b[i]){ at=i; best=b[i]; } } bool ok=true; int now=best; for(int i=at;i>=0;i--){ if(b[i]){ if(now>b[i]){ ok=false; } now=b[i]; } } now=best; for(int i=at;i<a;i++){ if(b[i]){ if(now>b[i]){ ok=false; } now=b[i]; } } if(!ok){ printf("0\n"); return 0; } int ind=0; for(int i=0;i<a;i++){ if(b[i])ev[ind++]=make_pair(b[i],i); } std::sort(ev,ev+ind); //for(int i=0;i<ind;i++)printf("%d %d\n",ev[i].first,ev[i].second); int L=0; int R=a-1; long long ret=1; int last=a+1; if(ind==1){ ret=0; int l=ev[0].second+1; int s=last-ev[0].first; int r=s-l; if(l>=1&&r>=0){ ret=(ret+fact[s-1]%mod*factinv[r]%mod*factinv[s-1-r]%mod)%mod; } if(best!=1){ r=R-ev[0].second+1; s=last-ev[0].first; l=s-r; if(r>=1&&l>=0){ ret=(ret+fact[s-1]%mod*factinv[l]%mod*factinv[s-1-l]%mod)%mod; } } printf("%d\n",(int)ret); return 0; } for(int i=ind-1;i>=0;i--){ if(ev[i].second<at){ int l=ev[i].second-L+1; int s=last-ev[i].first; int r=s-l; if(l<1||r<0){ret=0;break;} ret=ret*fact[s-1]%mod*factinv[r]%mod*factinv[s-1-r]%mod; L=ev[i].second+1; last=ev[i].first; R-=r; }else if(ev[i].second>at){ int r=R-ev[i].second+1; int s=last-ev[i].first; int l=s-r; if(r<1||l<0){ret=0;break;} ret=ret*fact[s-1]%mod*factinv[l]%mod*factinv[s-1-l]%mod; R=ev[i].second-1; last=ev[i].first; L+=l; }else{ long long Ret=0; int l=ev[0].second-L+1; int s=last-ev[0].first; int r=s-l; long long val=1; for(int j=0;j<R-L-s;j++)val=val*2%mod; if(l>=1&&r>=0){ Ret=(Ret+fact[s-1]%mod*factinv[r]%mod*factinv[s-1-r]%mod*val%mod)%mod; } if(best!=1){ r=R-ev[0].second+1; s=last-ev[0].first; l=s-r; if(r>=1&&l>=0){ Ret=(Ret+fact[s-1]%mod*factinv[l]%mod*factinv[s-1-l]%mod*val%mod)%mod; } } ret=ret*Ret%mod; R=-1111; } // printf("%d %d %d %d\n",i,L,R,(int)ret); } if(L<=R){ for(int i=0;i<R-L;i++)ret=ret*2%mod; } printf("%d\n",(int)ret); }
C:
よくみるとRMQだけでいけそうな気がしてくる。
#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; int segtree[3000000]; int sum[3000000]; char str[3000000]; int query(int a,int b,int c,int d,int e){ if(d<a||b<c)return 999999999; if(c<=a&&b<=d)return segtree[e]; return min(query(a,(a+b)/2,c,d,e*2),query((a+b)/2+1,b,c,d,e*2+1)); } int main(){ int a; scanf("%s%d",str,&a); for(int i=0;i<3000000;i++)segtree[i]=999999999; int n=strlen(str); for(int i=0;i<n;i++){ sum[i+1]=sum[i]; if(str[i]=='(')sum[i+1]++; else sum[i+1]--; segtree[1048576+i]=sum[i+1]; } for(int i=1048575;i>=1;i--){ segtree[i]=min(segtree[i*2],segtree[i*2+1]); } for(int i=0;i<a;i++){ int b,c; scanf("%d%d",&b,&c);b--;c--; int m=query(0,1048575,b,c,1); m-=sum[b]; int M=sum[c+1]-sum[b]; int ret=c-b+1; if(m<0){ret+=m;M-=m;} if(M>0)ret-=M; printf("%d\n",ret); } }
A:
典型的な感じがする。あんまり好きじゃない。
#include<stdio.h> #include<algorithm> using namespace std; int p[110000]; int q[110000]; int x[110000]; int y[110000]; long long t[1100000]; int main(){ int a; scanf("%d",&a); int S=0; long long now=0; for(int i=0;i<a;i++){ scanf("%d",q+i); if(q[i]==1)scanf("%d",x+i); else scanf("%d%d",x+i,y+i); } int b; scanf("%d",&b); for(int i=0;i<b;i++){scanf("%lld",t+i);t[i]--;} int at=0; for(int i=0;i<a;i++){ long long to=now; if(q[i]==1)to++; else to+=x[i]*y[i]; while(at<b&&t[at]<to){ if(q[i]==1)printf("%d ",x[i]); else printf("%d ",p[(t[at]-now)%x[i]]); at++; } if(q[i]==1){ if(S<100000){ p[S++]=x[i]; } now++; }else{ for(int k=0;k<y[i];k++){ if(S>=100000)break; for(int j=0;j<x[i];j++){ if(S>=100000)break; p[S++]=p[j]; } } now+=x[i]*y[i]; } } }
残り：読む暇なし
全部通る。
Rating: ?
