結果

問題 No.2640 traO Stamps
ユーザー AerenAeren
提出日時 2024-02-19 21:49:37
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 71 ms / 2,000 ms
コード長 5,436 bytes
コンパイル時間 3,338 ms
コンパイル使用メモリ 260,972 KB
実行使用メモリ 7,680 KB
最終ジャッジ日時 2024-09-29 01:47:15
合計ジャッジ時間 7,562 ms
ジャッジサーバーID
(参考情報)
judge5 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 34
権限があれば一括ダウンロードができます

ソースコード

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

// #pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
// #include <x86intrin.h>
using namespace std;
#if __cplusplus >= 202002L
using namespace numbers;
#endif
template<class T>
struct floyd_warshall{
int n;
vector<vector<T>> dist;
floyd_warshall(int n): n(n), dist(n, vector<T>(n)){ }
// Assumes the graph has no negative cycle
// O(|V|^3)
template<class U>
void run(const vector<vector<U>> &adjm){
assert(!n && adjm.empty() || n == (int)adjm.size() && n == (int)adjm[0].size());
for(auto u = 0; u < n; ++ u) for(auto v = 0; v < n; ++ v) dist[u][v] = adjm[u][v];
for(auto w = 0; w < n; ++ w) for(auto u = 0; u < n; ++ u) for(auto v = 0; v < n; ++ v) dist[u][v] = min(dist[u][v], dist[u][w] + dist[w][v]);
}
template<class U>
void run(const vector<tuple<int, int, U>> &edge, bool directed = false){
vector<vector<T>> adjm(n, vector<T>(n, numeric_limits<T>::max() / 2));
for(auto u = 0; u < n; ++ u) adjm[u][u] = 0;
for(auto [u, v, w]: edge){
adjm[u][v] = min<T>(adjm[u][v], w);
if(!directed) adjm[v][u] = adjm[u][v];
}
run(adjm);
}
// Requires graph
template<class G>
void run(const G &g, bool directed = false){
vector<vector<T>> adjm(n, vector<T>(n, numeric_limits<T>::max() / 2));
for(auto u = 0; u < n; ++ u) adjm[u][u] = 0;
for(auto [u, v, w]: g.edge){
adjm[u][v] = min<T>(adjm[u][v], w);
if(!directed) adjm[v][u] = adjm[u][v];
}
run(adjm);
}
};
template<bool ALLOW_NON_PREFIX_QUERY, class T, class F, class I>
struct fenwick_tree{
int n;
vector<T> data;
F TT;
T T_id;
I Tinv;
fenwick_tree(F TT, T T_id, I Tinv): TT(TT), T_id(T_id), Tinv(Tinv){ }
fenwick_tree &operator=(const fenwick_tree &fw){
n = fw.n;
data = fw.data;
}
// O(n)
void build(int n){
this->n = n;
data.assign(n, T_id);
}
// O(n)
void build(int n, T x){
this->n = n;
data.assign(n, x);
for(auto i = 1; i <= n; ++ i) if(i + (i & -i) <= n) data[i + (i & -i) - 1] = TT(data[i + (i & -i) - 1], data[i - 1]);
}
// O(n)
template<class U>
void build(const vector<U> &a){
n = (int)a.size();
data.resize(n);
copy(a.begin(), a.end(), data.begin());
for(auto i = 1; i <= n; ++ i) if(i + (i & -i) <= n) data[i + (i & -i) - 1] = TT(data[i + (i & -i) - 1], data[i - 1]);
}
// O(log(n))
void update(int p, T x){
assert(0 <= p && p < n);
for(++ p; p <= n; p += p & -p) data[p - 1] = TT(data[p - 1], x);
}
// O(log(n))
T prefix(int r) const{
T s = T_id;
for(; r > 0; r -= r & -r) s = TT(s, data[r - 1]);
return s;
}
// O(log(n))
T query(int l, int r) const{
static_assert(ALLOW_NON_PREFIX_QUERY);
assert(0 <= l && l <= r && r <= n);
if(l == r) return T_id;
T sum_minus = T_id, sum_plus = T_id;
for(; l < r; r -= r & -r) sum_plus = TT(sum_plus, data[r - 1]);
for(; r < l; l -= l & -l) sum_minus = TT(sum_minus, data[l - 1]);
return TT(sum_plus, Tinv(sum_minus));
}
// O(log(n))
T query(int p) const{
static_assert(ALLOW_NON_PREFIX_QUERY);
return query(p, p + 1);
}
// pred(sum[0, r)) is T, T, ..., T, F, F, ..., F, returns max r with T
// O(log(n))
int max_pref(auto pred) const{
assert(pred(T_id));
int p = 0;
T sum = T_id;
for(auto i = __lg(n + 1); i >= 0; -- i) if(p + (1 << i) <= n && pred(TT(sum, data[p + (1 << i) - 1]))){
sum = TT(sum, data[p + (1 << i) - 1]);
p += 1 << i;
}
return p;
}
template<class output_stream>
friend output_stream &operator<<(output_stream &out, const fenwick_tree &fw){
out << "{";
for(auto i = 0; i < fw.n; ++ i){
out << fw.query(i);
if(i != fw.n - 1) out << ", ";
}
return out << '}';
}
};
template<class T, class F, class I>
auto make_fenwick_tree(F TT, T T_id, I Tinv){
return fenwick_tree<true, T, F, I>(TT, T_id, Tinv);
}
template<class T>
auto make_fenwick_tree_sum(){
return fenwick_tree<true, T, plus<>, negate<>>(plus<>(), T{0}, negate<>());
}
template<class T>
auto make_fenwick_tree_product(){
auto inverse = [](const T &x){ return 1 / x; };
return fenwick_tree<true, T, multiplies<>, decltype(inverse)>(multiplies<>(), T{1}, inverse);
}
template<class T>
auto make_fenwick_tree_min(){
auto TT = [&](const T &x, const T &y)->T{ return min(x, y); };
return fenwick_tree<false, T, decltype(TT), negate<>>(TT, numeric_limits<T>::max(), negate<>());
}
template<class T>
auto make_fenwick_tree_max(){
auto TT = [&](const T &x, const T &y)->T{ return max(x, y); };
return fenwick_tree<false, T, decltype(TT), negate<>>(TT, numeric_limits<T>::max(), negate<>());
}
int main(){
cin.tie(0)->sync_with_stdio(0);
cin.exceptions(ios::badbit | ios::failbit);
int n, m, k;
cin >> n >> m >> k;
vector<int> pos(k + 1);
vector<tuple<int, int, int>> edge(m);
for(auto &u: pos){
cin >> u, -- u;
}
for(auto &[u, v, w]: edge){
cin >> u >> v >> w, -- u, -- v;
}
floyd_warshall<long long> floyd(n);
floyd.run(edge);
vector<long long> init(k);
for(auto i = 0; i < k; ++ i){
init[i] = floyd.dist[pos[i]][pos[i + 1]];
}
auto fw = make_fenwick_tree_sum<long long>();
fw.build(init);
int qn;
cin >> qn;
for(auto qi = 0; qi < qn; ++ qi){
int type;
cin >> type;
if(type == 1){
int i, u;
cin >> i >> u, -- u;
if(i > 0){
fw.update(i - 1, floyd.dist[pos[i - 1]][u] - floyd.dist[pos[i - 1]][pos[i]]);
}
if(i < k){
fw.update(i, floyd.dist[u][pos[i + 1]] - floyd.dist[pos[i]][pos[i + 1]]);
}
pos[i] = u;
}
else{
int ql, qr;
cin >> ql >> qr;
cout << fw.query(ql, qr) << "\n";
}
}
return 0;
}
/*
*/
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0