結果
問題 | No.772 Dynamic Distance Sum |
ユーザー | tonegawa |
提出日時 | 2024-05-06 09:43:50 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 17,528 bytes |
コンパイル時間 | 2,218 ms |
コンパイル使用メモリ | 159,728 KB |
実行使用メモリ | 58,496 KB |
最終ジャッジ日時 | 2024-11-28 15:29:16 |
合計ジャッジ時間 | 117,618 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 TLE * 1 |
other | AC * 1 RE * 9 TLE * 17 |
ソースコード
#include <iostream>#include <string>#include <vector>#include <array>#include <tuple>#include <stack>#include <queue>#include <deque>#include <algorithm>#include <set>#include <map>#include <unordered_set>#include <unordered_map>#include <bitset>#include <cmath>#include <functional>#include <cassert>#include <climits>#include <iomanip>#include <numeric>#include <memory>#include <random>#include <thread>#include <chrono>#define allof(obj) (obj).begin(), (obj).end()#define range(i, l, r) for(int i=l;i<r;i++)#define unique_elem(obj) obj.erase(std::unique(allof(obj)), obj.end())#define bit_subset(i, S) for(int i=S, zero_cnt=0;(zero_cnt+=i==S)<2;i=(i-1)&S)#define bit_kpop(i, n, k) for(int i=(1<<k)-1,x_bit,y_bit;i<(1<<n);x_bit=(i&-i),y_bit=i+x_bit,i=(!i?(1<<n):((i&~y_bit)/x_bit>>1)|y_bit))#define bit_kth(i, k) ((i >> k)&1)#define bit_highest(i) (i?63-__builtin_clzll(i):-1)#define bit_lowest(i) (i?__builtin_ctzll(i):-1)#define sleepms(t) std::this_thread::sleep_for(std::chrono::milliseconds(t))using ll = long long;using ld = long double;using ul = uint64_t;using pi = std::pair<int, int>;using pl = std::pair<ll, ll>;using namespace std;template<typename F, typename S>std::ostream &operator<<(std::ostream &dest, const std::pair<F, S> &p){dest << p.first << ' ' << p.second;return dest;}template<typename T>std::ostream &operator<<(std::ostream &dest, const std::vector<std::vector<T>> &v){int sz = v.size();if(sz==0) return dest;for(int i=0;i<sz;i++){int m = v[i].size();for(int j=0;j<m;j++) dest << v[i][j] << (i!=sz-1&&j==m-1?'\n':' ');}return dest;}template<typename T>std::ostream &operator<<(std::ostream &dest, const std::vector<T> &v){int sz = v.size();if(sz==0) return dest;for(int i=0;i<sz-1;i++) dest << v[i] << ' ';dest << v[sz-1];return dest;}template<typename T, size_t sz>std::ostream &operator<<(std::ostream &dest, const std::array<T, sz> &v){if(sz==0) return dest;for(int i=0;i<sz-1;i++) dest << v[i] << ' ';dest << v[sz-1];return dest;}template<typename T>std::ostream &operator<<(std::ostream &dest, const std::set<T> &v){for(auto itr=v.begin();itr!=v.end();){dest << *itr;itr++;if(itr!=v.end()) dest << ' ';}return dest;}template<typename T, typename E>std::ostream &operator<<(std::ostream &dest, const std::map<T, E> &v){for(auto itr=v.begin();itr!=v.end();){dest << '(' << itr->first << ", " << itr->second << ')';itr++;if(itr!=v.end()) dest << '\n';}return dest;}std::ostream &operator<<(std::ostream &dest, __int128_t value) {std::ostream::sentry s(dest);if (s) {__uint128_t tmp = value < 0 ? -value : value;char buffer[128];char *d = std::end(buffer);do {--d;*d = "0123456789"[tmp % 10];tmp /= 10;} while (tmp != 0);if (value < 0) {--d;*d = '-';}int len = std::end(buffer) - d;if (dest.rdbuf()->sputn(d, len) != len) {dest.setstate(std::ios_base::badbit);}}return dest;}template<typename T>vector<T> make_vec(size_t sz, T val){return std::vector<T>(sz, val);}template<typename T, typename... Tail>auto make_vec(size_t sz, Tail ...tail){return std::vector<decltype(make_vec<T>(tail...))>(sz, make_vec<T>(tail...));}template<typename T>vector<T> read_vec(size_t sz){std::vector<T> v(sz);for(int i=0;i<(int)sz;i++) std::cin >> v[i];return v;}template<typename T, typename... Tail>auto read_vec(size_t sz, Tail ...tail){auto v = std::vector<decltype(read_vec<T>(tail...))>(sz);for(int i=0;i<(int)sz;i++) v[i] = read_vec<T>(tail...);return v;}long long max(long long a, int b){return std::max(a, (long long)b);}long long max(int a, long long b){return std::max((long long)a, b);}long long min(long long a, int b){return std::min(a, (long long)b);}long long min(int a, long long b){return std::min((long long)a, b);}long long modulo(long long a, long long m){a %= m; return a < 0 ? a + m : a;}template<typename T>struct safe_vector : std::vector<T>{using std::vector<T>::vector;T& operator [](size_t i){return this->at(i);}};template<typename T, int N>struct safe_array : std::array<T, N>{using std::array<T, N>::array;T& operator [](size_t i){return this->at(i);}};ll ceil_div(ll x, ll y){assert(y > 0);return (x + (x > 0 ? y - 1 : 0)) / y;}ll floor_div(ll x, ll y){assert(y > 0);return (x + (x > 0 ? 0 : -y + 1)) / y;}void io_init(){std::cin.tie(nullptr);std::ios::sync_with_stdio(false);}template<typename top_tree_structure>struct toptree{using tts = top_tree_structure;using HVal = typename tts::HVal;using LVal = typename tts::LVal;static constexpr auto id = tts::id;static constexpr auto to_light = tts::to_light;static constexpr auto merge_ll = tts::merge_light;static constexpr auto merge_hl = tts::merge_heavy_light;static constexpr auto merge_hh = tts::merge_heavy;struct node{node *Hl, *Hr, *Hp;node *Lt, *Ll, *Lr, *Lp;int ALLsz, Lsz;bool flip;HVal val, ALLsum, ALLsumrev;LVal Lsum;node(HVal _val = id()): Hl(nullptr), Hr(nullptr), Hp(nullptr), Lt(nullptr), Ll(nullptr), Lr(nullptr), Lp(nullptr),ALLsz(1), Lsz(1), flip(false), val(_val), ALLsum(_val), ALLsumrev(_val), Lsum(to_light(_val)){}template<bool is_heavy>bool is_root(){if constexpr (is_heavy){return !Hp || (Hp->Hl != this && Hp->Hr != this);}else{return !Lp || (Lp->Ll != this && Lp->Lr != this);}}};static node *make_node(HVal val){return new node(val);}toptree(){}private:template<bool is_heavy>static void push_down(node *v){if constexpr (is_heavy){if(v->flip){if(v->Hl) flip(v->Hl);if(v->Hr) flip(v->Hr);v->flip = false;}}}static void flip(node *v){std::swap(v->Hl, v->Hr);std::swap(v->ALLsum, v->ALLsumrev);v->flip ^= 1;}template<bool is_heavy>static void update(node *v){if constexpr (is_heavy){v->ALLsz = 1;v->ALLsum = v->ALLsumrev = v->val;HVal c = id(), crev = id();if(v->Hl){v->ALLsz += v->Hl->ALLsz;v->ALLsum = merge_hh(v->Hl->ALLsum, v->ALLsum);crev = v->Hl->ALLsumrev;}if(v->Hr){v->ALLsz += v->Hr->ALLsz;v->ALLsumrev = merge_hh(v->Hr->ALLsumrev, v->ALLsumrev);c = v->Hr->ALLsum;}if(v->Lt){v->ALLsz += v->Lt->Lsz;c = merge_hl(c, v->Lt->Lsum);crev = merge_hl(crev, v->Lt->Lsum);}v->ALLsum = merge_hh(v->ALLsum, c);v->ALLsumrev = merge_hh(v->ALLsumrev, crev);}else{v->Lsum = to_light(v->ALLsum);v->Lsz = v->ALLsz;if(v->Ll){v->Lsz += v->Ll->Lsz;v->Lsum = merge_ll(v->Lsum, v->Ll->Lsum);}if(v->Lr){v->Lsz += v->Lr->Lsz;v->Lsum = merge_ll(v->Lsum, v->Lr->Lsum);}}}template<bool is_heavy>static void rotate_right(node *v){if constexpr (is_heavy){node *p = v->Hp, *pp = p->Hp;if((p->Hl = v->Hr)) v->Hr->Hp = p;v->Hr = p, p->Hp = v;update<1>(p), update<1>(v);if((v->Hp = pp)){if(pp->Hl == p) pp->Hl = v;if(pp->Hr == p) pp->Hr = v;update<1>(pp);}}else{node *p = v->Lp, *pp = p->Lp;if((p->Ll = v->Lr)) v->Lr->Lp = p;v->Lr = p, p->Lp = v;update<0>(p), update<0>(v);if((v->Lp = pp)){if(pp->Ll == p) pp->Ll = v;if(pp->Lr == p) pp->Lr = v;update<0>(pp);}}}template<bool is_heavy>static void rotate_left(node *v){if constexpr (is_heavy){node *p = v->Hp, *pp = p->Hp;if((p->Hr = v->Hl)) v->Hl->Hp = p;v->Hl = p, p->Hp = v;update<1>(p), update<1>(v);if((v->Hp = pp)){if(pp->Hl == p) pp->Hl = v;if(pp->Hr == p) pp->Hr = v;update<1>(pp);}}else{node *p = v->Lp, *pp = p->Lp;if((p->Lr = v->Ll)) v->Ll->Lp = p;v->Ll = p, p->Lp = v;update<0>(p), update<0>(v);if((v->Lp = pp)){if(pp->Ll == p) pp->Ll = v;if(pp->Lr == p) pp->Lr = v;update<0>(pp);}}}template<bool is_heavy>static void splay(node *v){if constexpr (is_heavy){node *u = nullptr;push_down<1>(v);while(!v->template is_root<1>()){node *p = v->Hp;if(p->template is_root<1>()){u = p;push_down<1>(p), push_down<1>(v);if(p->Hl == v) rotate_right<1>(v);else rotate_left<1>(v);}else{node *pp = p->Hp;if(pp->template is_root<1>()) u = pp;push_down<1>(pp), push_down<1>(p), push_down<1>(v);if(pp->Hl == p){if(p->Hl == v) rotate_right<1>(p);else rotate_left<1>(v);rotate_right<1>(v);}else{if(p->Hr == v) rotate_left<1>(p);else rotate_right<1>(v);rotate_left<1>(v);}}}if(u){node *Ll = u->Ll, *Lr = u->Lr, *Lp = u->Lp;u->Ll = u->Lr = u->Lp = nullptr;if((v->Ll = Ll)) Ll->Lp = v;if((v->Lr = Lr)) Lr->Lp = v;if((v->Lp = Lp)){if(Lp->Ll == u) Lp->Ll = v;if(Lp->Lr == u) Lp->Lr = v;if(Lp->Lt == u) Lp->Lt = v;}}}else{push_down<0>(v);while(!v->template is_root<0>()){node *p = v->Lp;if(p->template is_root<0>()){push_down<0>(p), push_down<0>(v);if(p->Ll == v) rotate_right<0>(v);else rotate_left<0>(v);}else{node *pp = p->Lp;push_down<0>(pp), push_down<0>(p), push_down<0>(v);if(pp->Ll == p){if(p->Ll == v) rotate_right<0>(p);else rotate_left<0>(v);rotate_right<0>(v);}else{if(p->Lr == v) rotate_left<0>(p);else rotate_right<0>(v);rotate_left<0>(v);}}}}}static void insert_light(node *p, node *c){push_down<0>(p);push_down<0>(c);if((c->Ll = p->Lt)) p->Lt->Lp = c;update<0>(c);p->Lt = c;c->Lp = p;update<1>(p);}static void erase_light(node *p, node *c){splay<0>(c);node *l = c->Ll, *r = c->Lr;c->Ll = c->Lr = c->Lp = nullptr;if(l && r){l->Lp = r->Lp = nullptr;while(l->Lr) l = l->Lr;splay<0>(l);l->Lr = r;r->Lp = l;update<0>(l);}else if(r) l = r;if(l) l->Lp = p;p->Lt = l;update<1>(p);}static void swap_light(node *p, node *a, node *b){push_down<0>(a);splay<0>(b);node *l = b->Ll, *r = b->Lr;b->Ll = b->Lr = b->Lp = nullptr;if((a->Ll = l)) l->Lp = a;if((a->Lr = r)) r->Lp = a;if((a->Lp = p)) p->Lt = a;update<0>(a);update<0>(b);}static node *expose(node *v){node *c = nullptr;for(node *u = v; u; u = u->Hp){splay<1>(u);if(c && u->Hr) swap_light(u, u->Hr, c);else if(c) erase_light(u, c);else if(u->Hr) insert_light(u, u->Hr);u->Hr = c;update<1>(u);c = u;}splay<1>(v);return c;}public:// vを根にするstatic node *evert(node *v){expose(v);flip(v);push_down<1>(v);return v;}// 非連結であることが保証されている場合static void _link(node *p, node *c){evert(c);expose(p);c->Hp = p;p->Hr = c;update<1>(p);}// 辺(a, b)があることが保証されている場合static bool _cut(node *u, node *v){evert(u);return cut_from_parent(v);}// 連結なことが保証されている場合static node *_lca(node *u, node *v){expose(u);return expose(v);}// cの親との辺を切る, false: 辺を切れなかったstatic bool cut_from_parent(node *c){expose(c);node *p = c->Hl;if(p == nullptr) return false;c->Hl = p->Hp = nullptr;update<1>(c);return true;}static node *get_root(node *v){expose(v);while(v->Hl){push_down<1>(v);v = v->Hl;}splay<1>(v);return v;}// 同じ連結成分かstatic bool is_same(node *u, node *v){if(!u || !v) return false;return get_root(u) == get_root(v);}static node *lca(node *u, node *v){if(!is_same(u, v)) return nullptr;return _lca(u, v);}static int size_subtree(node *v){expose(v);return 1 + (v->Lt ? v->Lt->Lsz : 0);}static void set(node *v, HVal x){expose(v);v->val = x;update<1>(v);}static HVal get(node *v){expose(v);return v->val;}static LVal query_subtree(node *v){expose(v);if(!v->Hl){return to_light(v->ALLsum);}else{HVal r = id();if(v->Lt) r = merge_hl(r, v->Lt->Lsum);return to_light(merge_hh(v->val, r));}}// evert(v) -> query_subtree(v) と同じ(実際にはevertしない)static LVal query_rerooting(node *v){expose(v);if(!v->Hl){return to_light(v->ALLsum);}else{LVal parrev = to_light(v->Hl->ALLsumrev);if(v->Lt) parrev = merge_ll(parrev, v->Lt->Lsum);return to_light(merge_hl(v->val, parrev));}}// 頂点vに対するcの部分木のLValをf(v, c)とする// vからf(v, c)が最小の隣り合う頂点cへ移動を繰り返して停止する頂点を返す(必ず停止する必要がある)// LVal/*static node *centroid(node *v){auto find_next = [&]() -> void {};}*/static node *aaa(node *v, int limit){// Hrに移動した時の値auto get_sum_r = [&](node *a, HVal subsum) -> LVal {assert(a->Hr);return to_light(merge_hh(a->Hr->ALLsum, subsum));};// Hlに移動した時の値, 新たなsubsumauto get_sum_l = [&](node *a, HVal subsum) -> std::pair<LVal, HVal> {assert(a->Hl);if(a->Lt) subsum = merge_hl(subsum, v->Lt->Lsum);subsum = merge_hh(v->val, subsum);HVal lch = subsum;if(a->Hl->Hr) lch = merge_hh(a->Hl->Hr->ALLsum, subsum);if(a->Hl->Lt) lch = merge_hl(lch, a->Hl->Lt->Lsum);return {to_light(merge_hh(a->Hl->val, lch)), subsum};};evert(v);HVal subsum = id();while(true){push_down<1>(v);int maxtype = -1;LVal maxval;if(v->Hr){LVal x = get_sum_r(v, subsum);if(maxtype == -1 || maxval.addmax < x.addmax) maxtype = 0, maxval = x;}if(v->Lt){if(maxtype == -1 || maxval.addmax < v->Lt->Lsum.addmax) maxtype = 1, maxval = v->Lt->Lsum;}if(v->Hl){auto [x, y] = get_sum_l(v, subsum);if(maxtype == -1 || maxval.addmax < x.addmax) maxtype = 2, subsum = y, maxval = x;}if(maxtype == -1){break;}if(maxval.addmax < limit){break;}if(maxtype == 0){v = v->Hr;}else if(maxtype == 1){subsum = id();v = v->Lt;while(true){maxval = to_light(v->ALLsum);node *u = v;if(v->Ll && maxval.addmax < v->Ll->Lsum.addmax){u = v->Ll;maxval = v->Ll->Lsum;}if(v->Lr && maxval.addmax < v->Lr->Lsum.addmax){u = v->Lr;}if(u == v) break;v = u;}}else{v = v->Hl;}}while(v->Hl){v = v->Hl;push_down<1>(v);}expose(v);return v;}};template<typename T>struct distance_sum{struct F{ T distsum, add, len; };struct G{ T distsum, add, addmax; };using HVal = F;using LVal = G;static constexpr HVal id(){ return {0, 0, 0}; }static constexpr LVal to_light(const HVal &v){ return {v.distsum, v.add, v.add}; }static constexpr HVal merge_heavy_light(const HVal &a, const LVal &b){ return {a.distsum + b.distsum, a.add + b.add, a.len}; }static constexpr HVal merge_heavy(const HVal &p, const HVal &c){ return {p.distsum + c.distsum + p.len * c.add, p.add + c.add, p.len + c.len}; }static constexpr LVal merge_light(const LVal &a, const LVal &b){ return {a.distsum + b.distsum, a.add + b.add, std::max(a.addmax, b.addmax)}; }};int main(){io_init();int n, q;std::cin >> n >> q;using tt = toptree<distance_sum<ll>>;using node = typename tt::node;vector<node*> v(n);range(i, 0, n) v[i] = tt::make_node({0, 1, 0});map<pair<int, int>, node*> E;ll S = 0;range(i, 0, q){int t;std::cin >> t;if(t == 1){int a, b, c;std::cin >> a >> b >> c;a = (a - 1 + S) % n;b = (b - 1 + S) % n;if(a > b) swap(a, b);node *e = tt::make_node({0, 0, c});tt::_link(v[a], e);tt::_link(v[b], e);E[{a, b}] = e;}else if(t == 2){int a, b;std::cin >> a >> b;a = (a - 1 + S) % n;b = (b - 1 + S) % n;if(a > b) swap(a, b);auto itr = E.find({a, b});node *e = itr->second;E.erase(itr);tt::_cut(v[a], e);tt::_cut(v[b], e);}else{int a;std::cin >> a;a = (a - 1 + S) % n;int newval = !v[a]->val.add;tt::set(v[a], {0, newval, 0});int one = v[a]->ALLsum.add;auto u = tt::aaa(v[a], one / 2 + 1);ll ans = tt::query_rerooting(u).distsum;std::cout << ans << '\n';S = (S + ans) % n;}}}