結果

問題 No.619 CardShuffle
ユーザー rickythetarickytheta
提出日時 2017-12-19 16:16:31
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 214 ms / 3,000 ms
コード長 3,404 bytes
コンパイル時間 1,928 ms
コンパイル使用メモリ 168,320 KB
実行使用メモリ 10,032 KB
最終ジャッジ日時 2024-06-02 04:50:17
合計ジャッジ時間 6,573 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
6,816 KB
testcase_01 AC 4 ms
6,940 KB
testcase_02 AC 3 ms
6,940 KB
testcase_03 AC 4 ms
6,940 KB
testcase_04 AC 3 ms
6,940 KB
testcase_05 AC 3 ms
6,940 KB
testcase_06 AC 3 ms
6,940 KB
testcase_07 AC 3 ms
6,944 KB
testcase_08 AC 3 ms
6,940 KB
testcase_09 AC 3 ms
6,944 KB
testcase_10 AC 3 ms
6,940 KB
testcase_11 AC 3 ms
6,940 KB
testcase_12 AC 3 ms
6,940 KB
testcase_13 AC 3 ms
6,944 KB
testcase_14 AC 3 ms
6,940 KB
testcase_15 AC 3 ms
6,944 KB
testcase_16 AC 190 ms
8,620 KB
testcase_17 AC 178 ms
9,904 KB
testcase_18 AC 190 ms
8,668 KB
testcase_19 AC 167 ms
9,968 KB
testcase_20 AC 79 ms
6,940 KB
testcase_21 AC 173 ms
8,876 KB
testcase_22 AC 123 ms
9,916 KB
testcase_23 AC 176 ms
8,864 KB
testcase_24 AC 124 ms
9,904 KB
testcase_25 AC 78 ms
6,960 KB
testcase_26 AC 197 ms
8,752 KB
testcase_27 AC 205 ms
9,904 KB
testcase_28 AC 198 ms
8,828 KB
testcase_29 AC 214 ms
10,032 KB
testcase_30 AC 87 ms
7,560 KB
testcase_31 AC 4 ms
6,940 KB
testcase_32 AC 71 ms
7,396 KB
testcase_33 AC 155 ms
8,848 KB
testcase_34 AC 150 ms
8,784 KB
testcase_35 AC 81 ms
6,940 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:53:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   53 |   scanf("%d",&n);
      |   ~~~~~^~~~~~~~~
main.cpp:56:16: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   56 |   REP(i,n)scanf("%s",s+i+2);
      |           ~~~~~^~~~~~~~~~~~
main.cpp:81:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   81 |   scanf("%d", &Q);
      |   ~~~~~^~~~~~~~~~
main.cpp:85:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   85 |     scanf("%s%d%d", buf, &x, &y);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

ソースコード

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