結果

問題 No.619 CardShuffle
ユーザー rickythetarickytheta
提出日時 2017-12-19 10:50:54
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 3,403 bytes
コンパイル時間 2,036 ms
コンパイル使用メモリ 156,512 KB
実行使用メモリ 9,916 KB
最終ジャッジ日時 2023-08-24 14:16:40
合計ジャッジ時間 6,675 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
6,628 KB
testcase_01 WA -
testcase_02 AC 4 ms
6,560 KB
testcase_03 WA -
testcase_04 AC 3 ms
6,556 KB
testcase_05 AC 4 ms
6,560 KB
testcase_06 WA -
testcase_07 AC 3 ms
6,600 KB
testcase_08 WA -
testcase_09 AC 3 ms
6,520 KB
testcase_10 AC 4 ms
6,564 KB
testcase_11 AC 3 ms
6,568 KB
testcase_12 AC 3 ms
6,568 KB
testcase_13 WA -
testcase_14 AC 3 ms
6,608 KB
testcase_15 AC 4 ms
6,568 KB
testcase_16 WA -
testcase_17 AC 189 ms
9,732 KB
testcase_18 WA -
testcase_19 AC 197 ms
9,916 KB
testcase_20 AC 83 ms
6,740 KB
testcase_21 WA -
testcase_22 AC 140 ms
9,768 KB
testcase_23 WA -
testcase_24 AC 138 ms
9,764 KB
testcase_25 AC 77 ms
6,596 KB
testcase_26 WA -
testcase_27 AC 230 ms
9,708 KB
testcase_28 WA -
testcase_29 AC 234 ms
9,852 KB
testcase_30 AC 85 ms
6,712 KB
testcase_31 AC 3 ms
6,604 KB
testcase_32 AC 72 ms
6,660 KB
testcase_33 WA -
testcase_34 WA -
testcase_35 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define FOR(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define FORR(i,a,b) for(int i=(int)(b)-1;i>=(int)(a);i--)

typedef long long ll;
typedef pair<int,int> pii;
const ll MOD = 1000000007ll;

int n;
char s[125252];
const int N = 1<<17;
ll dat1[2*N], dat2[2*N];
set<pii> sf;

void set1(int p, ll v){
  p += N-1;
  dat1[p] = v;
  while(p>0){
    p = (p-1)/2;
    dat1[p] = dat1[2*p+1] * dat1[2*p+2] % MOD;
  }
}
void set2(int p, ll v){
  p += N-1;
  dat2[p] = v;
  while(p>0){
    p = (p-1)/2;
    dat2[p] = (dat2[2*p+1] + dat2[2*p+2]) % MOD;
  }
}

ll query1(int l, int r, int a, int b, int k){
  if(r<=a || b<=l)return 1ll;
  if(l<=a && b<=r)return dat1[k];
  int m = (a+b)/2;
  return query1(l,r,a,m,2*k+1) * query1(l,r,m,b,2*k+2) % MOD;
}
ll query2(int l, int r, int a, int b, int k){
  if(r<=a || b<=l)return 0ll;
  if(l<=a && b<=r)return dat2[k];
  int m = (a+b)/2;
  return (query2(l,r,a,m,2*k+1) + query2(l,r,m,b,2*k+2)) % MOD;
}

inline pii getrange(int p){
  return *sf.lower_bound(pii(p, -1));
}

int main(){
  scanf("%d",&n);
  s[0] = '0';
  s[1] = '+';
  REP(i,n)scanf("%s",s+i+2);
  n += 2;
  s[n++] = '+';
  s[n++] = '0';
  // init mul(dat1)
  REP(i,n)dat1[i+N-1] = (isdigit(s[i]) ? s[i]-'0' : 1);
  FORR(i,0,N-1)dat1[i] = dat1[2*i+1] * dat1[2*i+2] % MOD;
  // get ranges split by '+'
  int bef = 0;
  REP(i,n)if(s[i]=='+'){
    int first = bef;
    int second = i-1;
    sf.insert(pii(second, first));
    i++;
    bef = i;
  }
  // init add(dat2)
  for(pii P : sf){
    int first = P.second;
    int second = P.first;
    dat2[first+N-1] = query1(first, second+1, 0, N, 0);
  }
  FORR(i,0,N-1)dat2[i] = (dat2[2*i+1] + dat2[2*i+2]) % MOD;
  // querying
  int Q;
  scanf("%d", &Q);
  while(Q--){
    char buf[2];
    int x, y;
    scanf("%s%d%d", buf, &x, &y);
    x = x-1+2;
    y = y-1+2;
    if(buf[0] == '!'){
      // swap
      if(s[x]==s[y])continue;
      if(isdigit(s[x])){
        swap(s[x], s[y]);
        // mul
        set1(x, s[x]-'0');
        set1(y, s[y]-'0');
        // add
        pii P;
        P = getrange(x);
        set2(P.second, query1(P.second, P.first+1, 0, N, 0));
        P = getrange(y);
        set2(P.second, query1(P.second, P.first+1, 0, N, 0));
      }else{
        if(s[x]=='+')swap(x,y);
        // split at x ('*' -> '+')
        pii P = getrange(x);
        int first = P.second;
        int second = P.first;
        sf.erase(P);
        pii Q = pii(x-1, first);
        pii R = pii(second, x+1);
        sf.insert(Q); sf.insert(R);
        set2(Q.second, query1(Q.second, Q.first+1, 0, N, 0));
        set2(R.second, query1(R.second, R.first+1, 0, N, 0));
        swap(s[x], s[y]);
        // join at y ('+' -> '*')
        P = getrange(y-1);
        Q = getrange(y+1);
        set2(Q.second, 1ll);
        sf.erase(P); sf.erase(Q);
        R = pii(Q.first, P.second);
        sf.insert(R);
        set2(R.second, query1(R.second, R.first+1, 0, N, 0));
      }
    }else{
      // answer
      pii P = getrange(x);
      pii Q = getrange(y);
      ll ans = 0ll;
      if(P==Q){
        ans = query1(x, y+1, 0, N, 0);
      }else{
        ans = query1(x, P.first+1, 0, N, 0);
        ans += query1(Q.second, y+1, 0, N, 0);
        ans += query2(P.first+1, Q.second, 0, N, 0);
        ans %= MOD;
      }
      printf("%lld\n", ans);
    }
  }
  return 0;
}
0