結果
| 問題 | No.619 CardShuffle |
| ユーザー |
 しらっ亭
|
| 提出日時 | 2017-12-19 03:57:40 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 200 ms / 3,000 ms |
| コード長 | 16,122 bytes |
| コンパイル時間 | 1,992 ms |
| コンパイル使用メモリ | 139,008 KB |
| 実行使用メモリ | 8,004 KB |
| 最終ジャッジ日時 | 2024-12-22 21:46:47 |
| 合計ジャッジ時間 | 6,417 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 35 |
コンパイルメッセージ
In member function 'void Treap<Val>::insert_b(Val) [with Val = int]',
inlined from 'void Main()' at main.cpp:489:45:
main.cpp:386:39: warning: 'void operator delete(void*, std::size_t)' called on unallocated object 'pool' [-Wfree-nonheap-object]
386 | root = insert_b(root, new node(val));
| ^~~~~~~~~~~~~
main.cpp: In function 'void Main()':
main.cpp:184:37: note: declared here
184 | static Node pool[500010];
| ^~~~
In member function 'void Treap<Val>::insert_b(Val) [with Val = int]',
inlined from 'void Main()' at main.cpp:586:18:
main.cpp:386:39: warning: 'void operator delete(void*, std::size_t)' called on unallocated object 'pool' [-Wfree-nonheap-object]
386 | root = insert_b(root, new node(val));
| ^~~~~~~~~~~~~
main.cpp: In function 'void Main()':
main.cpp:184:37: note: declared here
184 | static Node pool[500010];
| ^~~~
ソースコード
#include <iostream>#include <algorithm>#include <bitset>#include <map>#include <queue>#include <set>#include <stack>#include <string>#include <utility>#include <vector>#include <array>#include <unordered_map>#include <complex>#include <deque>#include <cassert>#include <cmath>#include <functional>#include <iomanip>#include <chrono>#include <random>#include <numeric>#include <tuple>#include <cstring>using namespace std;#define forr(x,arr) for(auto&& x:arr)#define _overload3(_1,_2,_3,name,...) name#define _rep2(i,n) _rep3(i,0,n)#define _rep3(i,a,b) for(int i=int(a);i<int(b);++i)#define rep(...) _overload3(__VA_ARGS__,_rep3,_rep2,)(__VA_ARGS__)#define _rrep2(i,n) _rrep3(i,0,n)#define _rrep3(i,a,b) for(int i=int(b)-1;i>=int(a);i--)#define rrep(...) _overload3(__VA_ARGS__,_rrep3,_rrep2,)(__VA_ARGS__)#define all(x) (x).begin(),(x).end()#define bit(n) (1LL<<(n))#define sz(x) ((int)(x).size())#define TEN(n) ((ll)(1e##n))#define fst first#define snd secondstring DBG_DLM(int &i){return(i++==0?"":", ");}#define DBG_B(exp){int i=0;os<<"{";{exp;}os<<"}";return os;}template<class T>ostream&operator<<(ostream&os,vector<T>v);template<class T>ostream&operator<<(ostream&os,set<T>v);template<class T>ostream&operator<<(ostream&os,queue<T>q);template<class T>ostream&operator<<(ostream&os,priority_queue<T>q);template<class T,class K>ostream&operator<<(ostream&os,pair<T,K>p);template<class T,class K>ostream&operator<<(ostream&os,map<T,K>mp);template<class T,class K>ostream&operator<<(ostream&os,unordered_map<T,K>mp);template<int I,class TPL>void DBG(ostream&os,TPL t){}template<int I,class TPL,class H,class...Ts>void DBG(ostream&os,TPL t){os<<(I==0?"":", ")<<get<I>(t);DBG<I+1,TPL,Ts...>(os,t);}template<class T,class K>void DBG(ostream&os,pair<T,K>p,string delim){os<<"("<<p.first<<delim<<p.second<<")";}template<class...Ts>ostream&operator<<(ostream&os,tuple<Ts...>t){os<<"(";DBG<0,tuple<Ts...>,Ts...>(os,t);os<<")";return os;}template<class T,class K>ostream&operator<<(ostream&os,pair<T,K>p){DBG(os,p,", ");return os;}template<class T>ostream&operator<<(ostream&os,vector<T>v){DBG_B(forr(t,v){os<<DBG_DLM(i)<<t;});}template<class T>ostream&operator<<(ostream&os,set<T>s){DBG_B(forr(t,s){os<<DBG_DLM(i)<<t;});}template<class T>ostream&operator<<(ostream&os,queue<T>q){DBG_B(for(;q.size();q.pop()){os<<DBG_DLM(i)<<q.front();});}template<class T>ostream&operator<<(ostream&os,priority_queue<T>q){DBG_B(for(;q.size();q.pop()){os<<DBG_DLM(i)<<q.top();});}template<class T,class K>ostream&operator<<(ostream&os,map<T,K>m){DBG_B(forr(p,m){os<<DBG_DLM(i);DBG(os,p,"->");});}template<class T,class K>ostream&operator<<(ostream&os,unordered_map<T,K>m){DBG_B(forr(p,m){os<<DBG_DLM(i);DBG(os,p,"->");});}#define DBG_OVERLOAD(_1,_2,_3,_4,_5,_6,macro_name,...)macro_name#define DBG_LINE(){char s[99];sprintf(s,"line:%3d | ",__LINE__);cerr<<s;}#define DBG_OUTPUT(v){cerr<<(#v)<<"="<<(v);}#define DBG1(v,...){DBG_OUTPUT(v);}#define DBG2(v,...){DBG_OUTPUT(v);cerr<<", ";DBG1(__VA_ARGS__);}#define DBG3(v,...){DBG_OUTPUT(v);cerr<<", ";DBG2(__VA_ARGS__);}#define DBG4(v,...){DBG_OUTPUT(v);cerr<<", ";DBG3(__VA_ARGS__);}#define DBG5(v,...){DBG_OUTPUT(v);cerr<<", ";DBG4(__VA_ARGS__);}#define DBG6(v,...){DBG_OUTPUT(v);cerr<<", ";DBG5(__VA_ARGS__);}#define DEBUG0(){DBG_LINE();cerr<<endl;}#ifdef LOCAL#define out(...){DBG_LINE();DBG_OVERLOAD(__VA_ARGS__,DBG6,DBG5,DBG4,DBG3,DBG2,DBG1)(__VA_ARGS__);cerr<<endl;}#else#define out(...)#endifusing ll=long long;using pii=pair<int,int>;using pll=pair<ll,ll>;using pil=pair<int,ll>;using pli=pair<ll,int>;using vs=vector<string>;using vvs=vector<vs>;using vvvs=vector<vvs>;using vb=vector<bool>;using vvb=vector<vb>;using vvvb=vector<vvb>;using vi=vector<int>;using vvi=vector<vi>;using vvvi=vector<vvi>;using vl=vector<ll>;using vvl=vector<vl>;using vvvl=vector<vvl>;using vd=vector<double>;using vvd=vector<vd>;using vvvd=vector<vvd>;using vpii=vector<pii>;using vvpii=vector<vpii>;using vvvpii=vector<vvpii>;template<class A,class B>bool amax(A&a,const B&b){return b>a?a=b,1:0;}template<class A,class B>bool amin(A&a,const B&b){return b<a?a=b,1:0;}ll ri(){ll l;cin>>l;return l;} string rs(){string s;cin>>s;return s;}const int mod = 1e9+7;template<int MOD> struct Mint {int x;Mint() : x(0) {}Mint(int y) : x(y >= 0 ? y % MOD : MOD - (-y) % MOD) {}Mint(int64_t sll) : x(sll % MOD) { if (x < 0) x += MOD; }Mint &operator+=(const Mint &rhs){ if((x += rhs.x) >= MOD) x -= MOD; return *this; }Mint &operator-=(const Mint &rhs){ if((x += MOD - rhs.x) >= MOD) x -= MOD; return *this; }Mint &operator*=(const Mint &rhs){ x = 1LL*x*rhs.x % MOD; return *this; }Mint &operator/=(const Mint &rhs){ x = (1LL*x*rhs.inv().x) % MOD; return *this; }Mint operator-() const { return Mint(-x); }Mint operator+(const Mint &rhs) const { return Mint(*this) += rhs; }Mint operator-(const Mint &rhs) const { return Mint(*this) -= rhs; }Mint operator*(const Mint &rhs) const { return Mint(*this) *= rhs; }Mint operator/(const Mint &rhs) const { return Mint(*this) /= rhs; }bool operator<(const Mint &rhs) const { return x < rhs.x; }Mint inv() const {signed a = x, b = MOD, u = 1, v = 0, t;while (b) { t = a / b; a -= t * b; swap(a, b); u -= t * v; swap(u, v); }return Mint(u);}Mint operator^(uint64_t t) const {Mint e = *this, res = 1;for(; t; e *= e, t>>=1) if (t & 1) res *= e;return res;}};template<int MOD> ostream &operator<<(ostream &os, const Mint<MOD> &rhs) { return os << rhs.x; }template<int MOD> istream &operator>>(istream &is, Mint<MOD> &rhs) { int64_t s; is >> s; rhs = Mint<MOD>(s); return is; };using mint = Mint<mod>;using vm=vector<mint>;using vvm=vector<vm>;using vvvm=vector<vvm>;template<class V, class Merge> struct SegmentTree {const int n;const V unit_value;vector<V> val;SegmentTree(int _n) : n(1 << (33-__builtin_clz(_n-1))), unit_value(Merge::unit()), val(n, unit_value) {}V get(int i) const { return val[i + n / 2]; }void set(int i, const V &v) { val[i + n / 2] = v; }void build() {for (int i = n / 2 - 1; i > 0; i--) val[i] = Merge::merge(val[i * 2 + 0], val[i * 2 + 1]);}void update(int i, const V &v) {i += n / 2;val[i] = v;while (i > 1) {i >>= 1;val[i] = Merge::merge(val[i * 2 + 0], val[i * 2 + 1]);}}V query(int l, int r) const {l = max(0, min(n / 2, l)) + n / 2;r = max(0, min(n / 2, r)) + n / 2;V ret = unit_value;for (; l < r; l >>= 1, r >>= 1) {if (l & 1) ret = Merge::merge(ret, val[l++]);if (r & 1) ret = Merge::merge(ret, val[--r]);}return ret;}};struct MergeRangeMulQ {static mint merge(const mint &l, const mint &r) { return l * r; }static mint unit() { return 1; }};template<class V> using SegTreeMul = SegmentTree<V, MergeRangeMulQ>;struct MergeRangeSumQ {static mint merge(const mint &l, const mint &r) { return l + r; }static mint unit() { return 0; }};template<class V> using SegTreeSum = SegmentTree<V, MergeRangeSumQ>;template <class Val> struct Treap {struct Node {static Val comp(const Val& l, const Val& r) { return min(l, r); };Val v;int priority;Node *lef, *rig;int size_;Val summary;Node() {}Node(Val v) : v(v), priority(xor128()), lef(nullptr), rig(nullptr), size_(1), summary(v) {}void *operator new(std::size_t) {static Node pool[500010];static int p = 0;return pool + p++;}int size() const { return size_;}string to_string() const { string res; to_string(res); return res; }void to_string(string &res) const {res += "Node [v="; res += std::to_string(v);res += ", size="; res += std::to_string(size_);res += "]";}static int xor128() {static random_device rnd;static int x = 123456789, y = 362436069, z = 521288629, w = rnd();int t = x ^ (x << 11);x = y;y = z;z = w;w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));return w;}static void to_string(const Node* a, string &res, int indent) {if (a == nullptr) return;to_string(a->lef, res, indent + 2);for (int i = 0; i < indent; i++) res += ' ';a->to_string(res);res += '\n';to_string(a->rig, res, indent + 2);}static Node* update(Node* a) {if (a == nullptr) return nullptr;a->size_ = 1 + size(a->lef) + size(a->rig);a->summary = a->v;if (a->lef != nullptr) a->summary = comp(a->summary, a->lef->summary);if (a->rig != nullptr) a->summary = comp(a->summary, a->rig->summary);return a;}static int size(const Node* x) { return x == nullptr ? 0 : x->size_; }static vector<Node*> nodes(Node* a) {vector<Node*> ret(size(a));nodes(a, ret, 0, size(a));return ret;}static void nodes(Node* a, vector<Node*> &ns, int L, int R) {if (a == nullptr) return;nodes(a->lef, ns, L, L + size(a->lef));ns[L + size(a->lef)] = a;nodes(a->rig, ns, R - size(a->rig), R);}static Node* merge(Node* a, Node* b) {if (b == nullptr) return a;if (a == nullptr) return b;if (a->priority > b->priority) {a->rig = merge(a->rig, b);return update(a);}else {b->lef = merge(a, b->lef);return update(b);}}static pair<Node*, Node*> split(Node* a, int k) {if (a == nullptr) return make_pair(nullptr, nullptr);if (k <= size(a->lef)) {auto s = split(a->lef, k);a->lef = s.second;s.second = update(a);return s;}else {auto s = split(a->rig, k - size(a->lef) - 1);a->rig = s.first;s.first = update(a);return s;}}};using node = Node;using np = node*;static np merge_technically(np a, np b) {if (node::size(a) > node::size(b)) swap(a, b);for (np cur : node::nodes(a)) {cur->lef = cur->rig = nullptr;b = insert_b(b, cur);}return b;}static pair<np, np> split_less(np a, Val v) {if (a == nullptr) return make_pair(nullptr, nullptr);if (a->v < v) {auto s = split_less(a->rig, v);a->rig = s.first;s.first = node::update(a);return s;}else {auto s = split_less(a->lef, v);a->lef = s.second;s.second = node::update(a);return s;}}static pair<np, np> split_leq(np a, Val v) {if (a == nullptr) return make_pair(nullptr, nullptr);if (a->v <= v) {auto s = split_leq(a->rig, v);a->rig = s.first;s.first = node::update(a);return s;}else {auto s = split_leq(a->lef, v);a->lef = s.second;s.second = node::update(a);return s;}}static np insert_k(np a, int k, const Val v) {auto lr = node::split(a, k);return node::merge(node::merge(lr.first, new node(v)), lr.second);}static np insert_b(np a, np v) {auto lr = split_less(a, v->v);return node::merge(node::merge(lr.first, v), lr.second);}static np erase_k(np a, int k) {auto lr = node::split(a, k);auto mr = node::split(lr.second, 1);return node::merge(lr.first, mr.second);}static np erase_b(np a, Val v) {auto lr = split_less(a, v);auto mr = node::split(lr.second, 1);return node::merge(lr.first, mr.second);}static np get_k(np a, int k) {while (a != nullptr) {if (k < node::size(a->lef)) {a = a->lef;}else if (k == node::size(a->lef)) {break;}else {k = k - node::size(a->lef) - 1;a = a->rig;}}return a;}public:np root;Treap() : root(nullptr) {}Treap(np root) : root(root) {}Treap(Treap l, Treap r) : root(node::merge(l.root, r.root)) {}string to_string() const { string res; node::to_string(root, res, 0); return res; }int size() const { return node::size(root); }pair<Treap, Treap> split_k(int k) {auto lr = node::split(root, k);return make_pair(Treap(lr.first), Treap(lr.second));}void insert_k(const Val val, int k) {root = insert_k(root, k, val);}void erase_k(int k) {root = erase_k(root, k);}Val operator[](int k) const {assert(size() > k);return get_k(root, k)->v;}void insert_b(const Val val) {root = insert_b(root, new node(val));}void erase_b(const Val val) {if (contains_b(val)) root = erase_b(root, val);}int count_less_b(const Val q) const {auto a = root;int lsize = 0;while (a != nullptr) {if (a->v < q) {lsize += node::size(a->lef) + 1;a = a->rig;}else {a = a->lef;}}return lsize;}int count_leq_b(const Val q) const {auto a = root;int lsize = 0;while (a != nullptr) {if (a->v <= q) {lsize += node::size(a->lef) + 1;a = a->rig;}else {a = a->lef;}}return lsize;}int count_b(const Val q) const {return count_leq_b(q) - count_less_b(q);}bool contains_b(const Val q) const {auto a = root;while (a != nullptr) {if (a->v == q) return true;else if (a->v < q) a = a->rig;else a = a->lef;}return false;}pair<Treap, Treap> split_less_b(const Val v) {auto lr = split_less(root, v);return make_pair(Treap(lr.first), Treap(lr.second));}pair<Treap, Treap> split_leq_b(const Val v) {auto lr = split_leq(root, v);return make_pair(Treap(lr.first), Treap(lr.second));}};template<class Val> ostream& operator<<(ostream& os, const Treap<Val>& treap) {vi tr;rep(i, sz(treap)) tr.emplace_back(treap[i]);os << tr;return os;}template<class V, class Merge> ostream& operator<<(ostream& os, const SegmentTree<V, Merge>& segtree) {vector<V> seg;rep(i, segtree.n/2) seg.emplace_back(segtree.get(i));os << seg;return os;}void Main() {int n = ri();string C = "+";rep(i, n) C += rs()[0];C += '+';int m = (n+1)/2;out(C, m);SegTreeMul<mint> seg1(m);SegTreeSum<mint> seg2(m);Treap<int> sep;{mint mul = 1;rrep(i, m) {int val = C[2*i+1] - '0';char op = C[2*i];seg1.update(i, val);mul *= val;if (op == '+') {seg2.update(i, mul);mul = 1;}}}rep(i, sz(C)) if (C[i] == '+') sep.insert_b(i/2);out(seg1);out(seg2);out(sep);int Q = ri();rep(_, Q) {char t = rs()[0];out("#####", _, t);out(seg1, seg2);out(C, sep);if (t == '?') {int l = ri()-1, r = ri()-1;l /= 2;r /= 2;bool flg = sep[sep.count_leq_b(l) - 1] == sep[sep.count_leq_b(r) - 1];out(t, l, r, flg);mint ret;if (flg) {ret = seg1.query(l, r+1);}else {ret = seg2.query(l, r+1);out(ret);{int nex_l = sep[sep.count_less_b(l)];if (nex_l > l) {mint pls = seg1.query(l, nex_l);out(nex_l, pls);ret += pls;}}{int nex_r1 = sep[sep.count_leq_b(r)];if (nex_r1 != r + 1) {int pre_r = sep[sep.count_leq_b(r) - 1];mint ovr = seg2.get(pre_r);mint pls = seg1.query(pre_r, r+1);out(pre_r, ovr, pls);ret -= ovr;ret += pls;}}}cout << ret << '\n';}else if (t == '!') {const int ia = ri(), ib = ri();out(t, ia, ib);if (C[ia] == C[ib]) continue;if (ia & 1) {mint cur_a = C[ia] - '0';mint cur_b = C[ib] - '0';int a = ia / 2;int b = ib / 2;int ga = sep[sep.count_leq_b(a)-1];int gb = sep[sep.count_leq_b(b)-1];int ga1 = sep[sep.count_leq_b(a)];int gb1 = sep[sep.count_leq_b(b)];out(cur_a, cur_b, a, b);out(ga, ga1, gb, gb1);seg1.update(a, cur_b);seg1.update(b, cur_a);seg2.update(ga, seg1.query(ga, ga1));seg2.update(gb, seg1.query(gb, gb1));}else {int m = C[ia] == '*' ? ia : ib;int p = ia + ib - m;m = m / 2;p = p / 2;{int lef = sep[sep.count_less_b(m)-1];mint cur1 = seg1.query(lef, m);mint cur2 = seg2.get(lef);int rig = sep[sep.count_leq_b(m)];out(cur1, cur2);seg2.update(lef, cur1);seg2.update(m, seg1.query(m, rig));sep.insert_b(m);}{int lef = sep[sep.count_less_b(p)-1];mint cur2 = seg2.get(p);seg2.update(p, 0);seg2.update(lef, seg2.get(lef) * cur2);sep.erase_b(p);}}swap(C[ia], C[ib]);}else {assert(false);}}}signed main() {cin.tie(nullptr);ios::sync_with_stdio(false);Main();return 0;}