제출 #1045001

#제출 시각아이디문제언어결과실행 시간메모리
1045001MercubytheFirst다리 (APIO19_bridges)C++17
0 / 100
185 ms3676 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; #define pb push_back const ll mod = 1e9 + 7; const ll N = 2e5 + 37; template<typename T, size_t N> std::ostream& operator<<(std::ostream& os, const std::array<T, N>& a); template<typename T> std::ostream& operator<<(std::ostream& os, const std::vector<T>& v); template<typename T1, typename T2> std::ostream& operator<<(std::ostream& os, const std::pair<T1, T2>& p); template<typename T> std::ostream& operator<<(std::ostream& os, const std::set<T>& s); template<typename T, typename cmp> std::ostream& operator<<(std::ostream& os, const std::set<T, cmp>& s); const ll inf = (ll)1e9 + 37; using aaa = array<int, 3>; int n, m, Q; vector<vector<array<int, 3> > > g; vector<bool> vis; int ans = 0, car = -1; vector<int> change; void brute_dfs(int v) { if(vis[v]) { return; } ++ans; vis[v] = true; for(auto& a : g[v]) { a[1] = change[a[2]]; if(car <= a[1] and !vis[a[0]]) { brute_dfs(a[0]); } } } void brute() { while(Q--) { ans = 0; int qt; cin >> qt; if(qt == 1) { int idx, w; cin >> idx >> w; change[idx] = w; } else if(qt == 2) { int u; cin >> u >> car; vis.assign(n + 1, false); brute_dfs(u); // cout << u << ' ' << car << ' ' << vis << " : " << ans << endl; cout << ans << endl; } else assert(false); } } void line() { vector<int> tree(2 * m + 3); auto update = [&](int idx, int val) -> void { for(tree[idx += m] = val; idx > 1; idx >>= 1) tree[idx >> 1] = min(tree[idx], tree[idx ^ 1]); }; auto query = [&](int l, int r) -> int { int ans = inf; for(l += m, r += m; l <= r; l >>= 1, r >>= 1) { if(l % 2 == 1) { ans = min(ans, tree[l++]); } if(r % 2 == 0) { ans = min(ans, tree[r--]); } } assert(ans != inf); return ans; }; assert(m == n - 1); for(int i = 1; i <= m; ++i) { update(i, change[i]); } while(Q--) { int qt; cin >> qt; if(qt == 1) { int idx, w; cin >> idx >> w; update(idx, w); } else if(qt == 2) { int u, w; cin >> u >> w; int l = 1, r = u - 1, l_ans = u, r_ans = u; while(l <= r) { int mid = (l + r) / 2; if(query(mid, u-1) >= w) { r = mid - 1; l_ans = mid; } else { l = mid + 1; } } l = u, r = n - 1; while(l <= r) { int mid = (l + r) / 2; if(query(u, mid) >= w) { r_ans = mid; l = mid + 1; } else { r = mid - 1; } } cout << r_ans - l_ans + 1 << endl; } else assert(false); } } void solve() { cin >> n >> m; g.assign(n + 1, vector<aaa>()); change.assign(m + 1, -1); vis.assign(n + 1, false); for(int i = 1; i <= m; ++i) { int u, v, c; cin >> u >> v >> c; assert(u == i and v == i + 1); g[u].pb({v, c, i}); g[v].pb({u, c, i}); change[i] = c; } cin >> Q; if(n <= 1000 and m <= 1000 and Q <= 10'000) { brute(); return; } line(); } signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); // signed t; cin >> t; while(t--) solve(); } template<typename T, size_t N> std::ostream& operator<<(std::ostream& os, const std::array<T, N>& a) { os << "["; for(size_t i = 0; i + 1 < N; ++i) { os << a[i] << ", "; } if(N > 0) os << a[N - 1]; os << "]"; return os; } template<typename T1, typename T2> std::ostream& operator<<(std::ostream& os, const std::pair<T1, T2>& p) { os << "(" << p.first << ", " << p.second << ") "; return os; } template<typename T> std::ostream& operator<<(std::ostream& os, const std::vector<T>& v) { os << '['; for(auto x : v) os << x << ", "; os << "] "; return os; } template<typename T> std::ostream& operator<<(std::ostream& os, const std::set<T>& s) { os << "{"; for(auto x : s) os << x << ", "; os << "} "; return os; } template<typename T, typename cmp> std::ostream& operator<<(std::ostream& os, const std::set<T, cmp>& s) { os << "{"; for(auto x : s) os << x << ", "; os << "} "; return os; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...