結果
| 問題 | No.619 CardShuffle |
| ユーザー |
 ryoissy
|
| 提出日時 | 2018-01-25 03:24:33 |
| 言語 | C++11 (gcc 11.4.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 3,940 bytes |
| コンパイル時間 | 1,399 ms |
| コンパイル使用メモリ | 164,120 KB |
| 実行使用メモリ | 12,288 KB |
| 最終ジャッジ日時 | 2024-06-08 01:07:31 |
| 合計ジャッジ時間 | 5,183 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge2 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | WA | - |
| testcase_01 | WA | - |
| testcase_02 | WA | - |
| testcase_03 | WA | - |
| testcase_04 | WA | - |
| testcase_05 | WA | - |
| testcase_06 | WA | - |
| testcase_07 | WA | - |
| testcase_08 | WA | - |
| testcase_09 | WA | - |
| testcase_10 | WA | - |
| testcase_11 | WA | - |
| testcase_12 | WA | - |
| testcase_13 | WA | - |
| testcase_14 | WA | - |
| testcase_15 | WA | - |
| testcase_16 | WA | - |
| testcase_17 | WA | - |
| testcase_18 | WA | - |
| testcase_19 | WA | - |
| testcase_20 | WA | - |
| testcase_21 | WA | - |
| testcase_22 | WA | - |
| testcase_23 | WA | - |
| testcase_24 | WA | - |
| testcase_25 | WA | - |
| testcase_26 | WA | - |
| testcase_27 | WA | - |
| testcase_28 | WA | - |
| testcase_29 | WA | - |
| testcase_30 | WA | - |
| testcase_31 | WA | - |
| testcase_32 | WA | - |
| testcase_33 | WA | - |
| testcase_34 | WA | - |
| testcase_35 | WA | - |
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:194:36: warning: format ‘%lld’ expects argument of type ‘long long int’, but argument 2 has type ‘valu’ [-Wformat=]
194 | printf("%lld\n",seg.query(l,r));
| ~~~^ ~~~~~~~~~~~~~~
| | |
| long long int valu
main.cpp:148:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
148 | scanf("%d%*c",&n);
| ~~~~~^~~~~~~~~~~~
main.cpp:152:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
152 | scanf("%c%*c",&c);
| ~~~~~^~~~~~~~~~~~
main.cpp:169:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
169 | scanf("%d%*c",&q);
| ~~~~~^~~~~~~~~~~~
main.cpp:173:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
173 | scanf("%c%d%d%*c",&qe,&l,&r);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
ソースコード
#include <bits/stdc++.h>
#define MOD 1000000007LL
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
struct valu{
ll sum=0,l=0,r=0;
int flag=0;
valu(){}
valu(ll a,ll b,ll c,int f){
sum=a;
l=b;
r=c;
flag=f;
}
};
int n;
int fie[10000000];
struct segtree{
static const int N=1<<17;
valu val[1<<18];
void update(int k,ll v){
k+=N-1;
val[k]=valu(v,v,v,1);
int nl=k-N+1,nr=k+1-N+1;
int s=1;
while(k>0){
int pr=k;
k=(k-1)/2;
if(pr==k*2+1){
nr+=s;
}else{
nl-=s;
}
s*=2;
if(fie[(nl+nr)/2-1]==0){
val[k]=valu((val[k*2+1].sum+val[k*2+2].sum)%MOD,val[k*2+1].l,val[k*2+2].r,0);
}else{
valu vl=val[k*2+1];
valu vr=val[k*2+2];
if(vl.flag==1 && vr.flag==1){
val[k]=valu(vl.sum*vr.sum%MOD,vl.sum*vr.sum%MOD,vl.sum*vr.sum%MOD,1);
}else if(vl.flag==1){
val[k]=valu((vl.sum*vr.l+vr.r)%MOD,vl.sum*vr.l%MOD,vr.r,0);
}else if(vr.flag==1){
val[k]=valu((vl.r*vr.sum+vl.l)%MOD,vl.l,vr.sum*vl.r%MOD,0);
}else{
val[k]=valu((vl.r*vr.l+vl.l+vr.r)%MOD,vl.l,vr.r,0);
}
}
//printf("%d %lld %d %d %lld %lld %lld\n",k,v,nl,nr,val[k].sum,val[k*2+1].sum,val[k*2+2].sum);
}
}
void update2(int v){
stack<int> st;
int l=0,r=N;
int k=0;
int s=N;
while(1){
st.push(k);
if(v<(l+r)/2-1){
r=(l+r)/2;
k=k*2+1;
}else if(v==(l+r)/2-1){
break;
}else if(v>(l+r)/2-1){
l=(l+r)/2;
k=k*2+2;
}
s/=2;
}
//printf("%d %d %d\n",l,r,v);
int nl=l,nr=r;
int pr=-1;
s/=2;
while(st.size()){
k=st.top();
//printf("%d ",k);
st.pop();
if(pr!=-1){
if(pr==k*2+1){
nr+=s;
}else{
nl-=s;
}
s*=2;
}
pr=k;
//printf("%d %d %d %d %lld %lld ",nl,nr,(nl+nr)/2-1,fie[(nl+nr)/2-1],val[k*2+1].sum,val[k*2+2].sum);
if(fie[(nl+nr)/2-1]==0){
val[k]=valu((val[k*2+1].sum+val[k*2+2].sum)%MOD,val[k*2+1].l,val[k*2+2].r,0);
}else{
valu vl=val[k*2+1];
valu vr=val[k*2+2];
if(vl.flag==1 && vr.flag==1){
val[k]=valu(vl.sum*vr.sum%MOD,vl.sum*vr.sum%MOD,vl.sum*vr.sum%MOD,1);
}else if(vl.flag==1){
val[k]=valu((vl.sum*vr.l+vr.r)%MOD,vl.sum*vr.l%MOD,vr.r,0);
}else if(vr.flag==1){
val[k]=valu((vl.r*vr.sum+vl.l)%MOD,vl.l,vr.sum*vl.r%MOD,0);
}else{
val[k]=valu((vl.r*vr.l+vl.l+vr.r)%MOD,vl.l,vr.r,0);
}
}
}
//printf("\n");
}
valu query(int a,int b,int k=0,int l=0,int r=N){
//printf("%d %d %lld\n",l,r,val[k].sum);
if(b<=l || r<=a)return valu(0,0,0,-1);
if(a<=l && r<=b)return val[k];
int mid=(l+r)/2;
valu vl=query(a,b,k*2+1,l,mid);
valu vr=query(a,b,k*2+2,mid,r);
//printf("%d %d %lld %lld\n",l,r,vl.sum,vr.sum);
if(vl.flag==-1){
return vr;
}
if(vr.flag==-1){
return vl;
}
if(fie[mid-1]==1){
if(vl.flag==1 && vr.flag==1){
return valu(vl.sum*vr.sum%MOD,vl.sum*vr.sum%MOD,vl.sum*vr.sum%MOD,1);
}
if(vl.flag==1){
return valu((vl.sum*vr.l+vr.r)%MOD,vl.sum*vr.l%MOD,vr.r,0);
}
if(vr.flag==1){
return valu((vl.r*vr.sum+vl.l)%MOD,vl.l,vr.sum*vl.r%MOD,0);
}
return valu((vl.r*vr.l+vl.l+vr.r)%MOD,vl.l,vr.r,0);
}else{
return valu((vl.sum+vr.sum)%MOD,vl.l,vr.r,0);
}
}
};
int va[1000000];
segtree seg;
int main(void){
scanf("%d%*c",&n);
//printf("%d\n",n);
for(int i=0;i<n;i++){
char c;
scanf("%c%*c",&c);
//printf("%c\n",c);
if(i%2==0){
va[i/2]=(c-'0');
seg.update(i/2,c-'0');
}else{
if(c=='+'){
fie[i/2]=0;
}else{
fie[i/2]=1;
}
}
}
for(int i=0;i<n/2;i++){
seg.update2(i);
}
int q;
scanf("%d%*c",&q);
for(int i=0;i<q;i++){
char qe;
int l,r;
scanf("%c%d%d%*c",&qe,&l,&r);
if(qe=='!'){
l--;
r--;
if(l%2==0){
l/=2;
r/=2;
swap(va[l],va[r]);
seg.update(l,va[l]);
seg.update(r,va[r]);
}else{
l/=2;
r/=2;
swap(fie[l],fie[r]);
seg.update2(l);
seg.update2(r);
}
}else{
l/=2;
r/=2;
r++;
printf("%lld\n",seg.query(l,r));
}
}
return 0;
}