結果
問題 | No.619 CardShuffle |
ユーザー | heyshb |
提出日時 | 2017-12-19 18:13:20 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 310 ms / 3,000 ms |
コード長 | 2,362 bytes |
コンパイル時間 | 2,342 ms |
コンパイル使用メモリ | 145,784 KB |
実行使用メモリ | 8,364 KB |
最終ジャッジ日時 | 2023-08-24 14:53:42 |
合計ジャッジ時間 | 7,871 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge14 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
7,616 KB |
testcase_01 | AC | 3 ms
7,544 KB |
testcase_02 | AC | 3 ms
7,612 KB |
testcase_03 | AC | 3 ms
7,620 KB |
testcase_04 | AC | 2 ms
7,536 KB |
testcase_05 | AC | 3 ms
7,544 KB |
testcase_06 | AC | 3 ms
7,612 KB |
testcase_07 | AC | 3 ms
7,624 KB |
testcase_08 | AC | 2 ms
7,708 KB |
testcase_09 | AC | 2 ms
7,616 KB |
testcase_10 | AC | 2 ms
7,748 KB |
testcase_11 | AC | 3 ms
7,688 KB |
testcase_12 | AC | 3 ms
7,620 KB |
testcase_13 | AC | 2 ms
7,628 KB |
testcase_14 | AC | 3 ms
7,872 KB |
testcase_15 | AC | 3 ms
7,544 KB |
testcase_16 | AC | 237 ms
8,036 KB |
testcase_17 | AC | 144 ms
8,172 KB |
testcase_18 | AC | 235 ms
8,168 KB |
testcase_19 | AC | 145 ms
8,132 KB |
testcase_20 | AC | 167 ms
8,100 KB |
testcase_21 | AC | 221 ms
8,212 KB |
testcase_22 | AC | 81 ms
8,032 KB |
testcase_23 | AC | 220 ms
8,212 KB |
testcase_24 | AC | 82 ms
8,116 KB |
testcase_25 | AC | 97 ms
8,108 KB |
testcase_26 | AC | 248 ms
8,364 KB |
testcase_27 | AC | 203 ms
8,036 KB |
testcase_28 | AC | 247 ms
8,140 KB |
testcase_29 | AC | 205 ms
8,188 KB |
testcase_30 | AC | 234 ms
8,100 KB |
testcase_31 | AC | 2 ms
7,664 KB |
testcase_32 | AC | 153 ms
8,032 KB |
testcase_33 | AC | 175 ms
8,192 KB |
testcase_34 | AC | 310 ms
8,144 KB |
testcase_35 | AC | 35 ms
7,616 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; typedef long long LL; const int MOD = 1e9+7; int N; char v[200010]; const int blk = 200; int bl[200010],L[200010],R[200010]; int S[200010],rv[200010],lv[200010],mv[200010],B; int fp[200010],lp[200010]; void upd(int &x) { if (x < 0) x += MOD; if (x >= MOD) x -= MOD; } int calc(int l,int r)//num---num { assert(!(l==1 && r==100000)); int sum = 0,nowv = 1; for (int i=l;i<=r;i+=2) { nowv = (1LL * nowv * (v[i] - '0')) % MOD; if (v[i+1] == '+' || i==r) { upd(sum += nowv); nowv = 1; } } return sum; } void build(int b) { fp[b] = lp[b] = 0; for (int i=L[b]+1;i<R[b];i+=2) { if (v[i] == '+') { if (!fp[b]) fp[b] = i; lp[b] = i; } } S[b] = calc(L[b],R[b]-1); if (fp[b]) { lv[b] = calc(L[b],fp[b]-1); rv[b] = calc(lp[b]+1,R[b]-1); mv[b] = S[b] - lv[b]; upd(mv[b]); upd(mv[b] -= rv[b]); } } int query(int x,int y) { if (bl[x] == bl[y]) return calc(x,y); int sum = 0,nowv = 1; for (int i=x;i<R[bl[x]];i+=2) { nowv = 1LL * nowv * (v[i] - '0') % MOD; if (v[i+1] == '+') { upd(sum += nowv); nowv = 1; } } for (int i=bl[x]+1;i<bl[y];i++) { if (v[R[i]] == '+') { if (fp[i]) { nowv = 1LL * nowv * lv[i] % MOD; upd(sum += nowv); upd(sum += S[i]); upd(sum -= lv[i]); } else { nowv = 1LL * nowv * S[i] % MOD; upd(sum += nowv); } nowv = 1; } else { if (fp[i]) { nowv = 1LL * nowv * lv[i] % MOD; upd(sum += nowv); upd(sum += mv[i]); nowv = rv[i]; } else { nowv = 1LL * nowv * S[i] % MOD; } } } for (int i=L[bl[y]];i<=y;i+=2) { nowv = 1LL * nowv * (v[i] - '0') % MOD; if (v[i+1] == '+' || i==y) { upd(sum += nowv); nowv = 1; } } return sum; } int main() { scanf("%d",&N); for (int i=1;i<=N;i++)bl[i] = (i - 1) / blk + 1; B = bl[N]; for (int i=1;i<=N;i++) { if (bl[i] != bl[i-1]) L[bl[i]] = i; if (bl[i] != bl[i+1]) R[bl[i]] = i; } for (int i=1;i<=N;i++) { char tmp[2]; scanf("%s",tmp); v[i] = tmp[0]; } for (int i=1;i<=B;i++) { build(i); } int Q; scanf("%d",&Q); while(Q--) { char tmp[2]; int x,y; scanf("%s",tmp); scanf("%d%d",&x,&y); if (tmp[0] == '?') { printf("%d\n",query(x,y)); } else { if (v[x] != v[y]) { swap(v[x],v[y]); build(bl[x]); build(bl[y]); } } } }