結果

問題 No.772 Dynamic Distance Sum
ユーザー tonegawatonegawa
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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));
}
}
// vcLValf(v, c)
// vf(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, subsum
auto 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;
}
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0