結果

問題 No.619 CardShuffle
ユーザー rickythetarickytheta
提出日時 2017-12-19 16:16:31
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 230 ms / 3,000 ms
コード長 3,404 bytes
コンパイル時間 1,648 ms
コンパイル使用メモリ 156,480 KB
実行使用メモリ 10,024 KB
最終ジャッジ日時 2023-08-24 14:39:56
合計ジャッジ時間 7,095 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
6,640 KB
testcase_01 AC 3 ms
6,740 KB
testcase_02 AC 4 ms
6,592 KB
testcase_03 AC 3 ms
6,672 KB
testcase_04 AC 4 ms
6,676 KB
testcase_05 AC 3 ms
6,600 KB
testcase_06 AC 3 ms
6,564 KB
testcase_07 AC 4 ms
6,604 KB
testcase_08 AC 4 ms
6,644 KB
testcase_09 AC 4 ms
6,888 KB
testcase_10 AC 4 ms
6,684 KB
testcase_11 AC 3 ms
6,556 KB
testcase_12 AC 4 ms
6,688 KB
testcase_13 AC 3 ms
6,600 KB
testcase_14 AC 3 ms
6,652 KB
testcase_15 AC 4 ms
6,600 KB
testcase_16 AC 199 ms
8,860 KB
testcase_17 AC 186 ms
9,964 KB
testcase_18 AC 201 ms
8,644 KB
testcase_19 AC 185 ms
9,808 KB
testcase_20 AC 80 ms
6,660 KB
testcase_21 AC 187 ms
8,664 KB
testcase_22 AC 142 ms
10,024 KB
testcase_23 AC 189 ms
8,720 KB
testcase_24 AC 140 ms
9,820 KB
testcase_25 AC 76 ms
6,768 KB
testcase_26 AC 205 ms
8,624 KB
testcase_27 AC 230 ms
9,960 KB
testcase_28 AC 204 ms
8,620 KB
testcase_29 AC 225 ms
9,780 KB
testcase_30 AC 84 ms
6,668 KB
testcase_31 AC 3 ms
6,552 KB
testcase_32 AC 72 ms
6,840 KB
testcase_33 AC 164 ms
8,652 KB
testcase_34 AC 156 ms
8,636 KB
testcase_35 AC 80 ms
6,804 KB
権限があれば一括ダウンロードができます

ソースコード

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, 0ll);
        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