結果
| 問題 | No.619 CardShuffle |
| ユーザー |
 kwm_t
|
| 提出日時 | 2022-01-10 19:35:58 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 89 ms / 3,000 ms |
| コード長 | 3,205 bytes |
| コンパイル時間 | 4,103 ms |
| コンパイル使用メモリ | 232,864 KB |
| 実行使用メモリ | 6,964 KB |
| 最終ジャッジ日時 | 2024-11-14 11:02:07 |
| 合計ジャッジ時間 | 7,893 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 35 |
ソースコード
#include <bits/stdc++.h>#include <atcoder/all>using namespace std;using namespace atcoder;using mint = modint1000000007;const int mod = 1000000007;//using mint = modint998244353;//const int mod = 998244353;//const int INF = 1e9;//const long long LINF = 1e18;//const bool debug = false;#define rep(i, n) for (int i = 0; i < (n); ++i)#define rep2(i,l,r)for(int i=(l);i<(r);++i)#define rrep(i, n) for (int i = (n-1); i >= 0; --i)#define rrep2(i,l,r)for(int i=(r-1);i>=(l);--i)#define all(x) (x).begin(),(x).end()#define allR(x) (x).rbegin(),(x).rend()#define endl "\n"#define P pair<int,int>template<typename A, typename B> inline bool chmax(A & a, const B & b) { if (a < b) { a = b; return true; } return false; }template<typename A, typename B> inline bool chmin(A & a, const B & b) { if (a > b) { a = b; return true; } return false; }struct S {int pre;//0:+,1:*int type;//-1:e,0:(*,b.*),1:(a,b,c)mint h, b, t;};/*1*1(a,b,c)+(d,e,f) = (a,b+c+d+e,f)(a,b,c)*(d,e,f) = (a,b+c*d+e,f)0*0(b)+(e) = (b,0,e)(b)*(e) = (be)0*1(b)+(d,e,f) = (b,d+e,f)(b)*(d,e,f) = (b*d,e,f)1*0(a,b,c)+(e) = (a,b+c,e)(a,b,c)*(e) = (a,b,c*e)*/S op(S a, S b) {if (-1 == a.type)return b;if (-1 == b.type)return a;S ret;ret.pre = a.pre;if ((0 == a.type) && (0 == b.type) && (0 == b.pre)) {ret.h = a.b, ret.b = 0, ret.t = b.b, ret.type = 1;}else if ((0 == a.type) && (0 == b.type) && (1 == b.pre)) {ret.h = 0, ret.b = a.b * b.b, ret.t = 0, ret.type = 0;}else if ((0 == a.type) && (1 == b.type) && (0 == b.pre)) {ret.h = a.b, ret.b = b.h + b.b, ret.t = b.t, ret.type = 1;}else if ((0 == a.type) && (1 == b.type) && (1 == b.pre)) {ret.h = a.b * b.h, ret.b = b.b, ret.t = b.t, ret.type = 1;}else if ((1 == a.type) && (0 == b.type) && (0 == b.pre)) {ret.h = a.h, ret.b = a.b + a.t, ret.t = b.b, ret.type = 1;}else if ((1 == a.type) && (0 == b.type) && (1 == b.pre)) {ret.h = a.h, ret.b = a.b, ret.t = a.t * b.b, ret.type = 1;}else if ((1 == a.type) && (1 == b.type) && (0 == b.pre)) {ret.h = a.h, ret.b = a.b + a.t + b.h + b.b, ret.t = b.t, ret.type = 1;}else if ((1 == a.type) && (1 == b.type) && (1 == b.pre)) {ret.h = a.h, ret.b = a.b + a.t * b.h + b.b, ret.t = b.t, ret.type = 1;}else {//error}return ret;}S e() { return S{ 0,-1,0,0,0 }; }int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n; cin >> n;vector<S>v((n + 1) / 2, S{ 0, 0, 0, 0, 0 });rep(i, n) {if (0 == i % 2) {int c; cin >> c;v[i / 2].b = c;}else {char c; cin >> c;if ('+' != c)v[(i + 1) / 2].pre = 1;}}segtree<S, op, e>seg(v);int q; cin >> q;while (q--) {char t; cin >> t;int x, y; cin >> x >> y;if ('!' == t) {x--; y--;S getx, gety;if (0 == x % 2) {x /= 2, y /= 2;getx = seg.get(x);gety = seg.get(y);swap(getx.b, gety.b);}else {x++, y++;x /= 2, y /= 2;getx = seg.get(x);gety = seg.get(y);swap(getx.pre, gety.pre);}seg.set(x, getx);seg.set(y, gety);}else {x /= 2; y /= 2;auto get = seg.prod(x, y + 1);mint ans = get.b + get.h + get.t;cout << ans.val() << endl;}}return 0;}