Submission #1045020

#	Time	Username	Problem	Language	Result	Execution time	Memory
1045020		MercubytheFirst	Bridges (APIO19_bridges)	C++17	13 / 100	128 ms	22616 KiB

bridges

#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<ll, 3>;
ll n, m, Q;

vector<vector<array<ll, 3> > > g;
vector<bool> vis;
ll ans = 0, car = -1;
vector<ll> change;
void brute_dfs(ll 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;
    ll qt;
    cin >> qt;
    if(qt == 1) {
      ll idx, w;
      cin >> idx >> w;
      change[idx] = w;
    }
    else if(qt == 2) {
      ll 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<ll> tree(2 * m + 3);

  auto update = [&](ll idx, ll val) -> void
  { 
    for (tree[idx += m] = val; idx > 1; idx >>= 1) tree[idx>>1] = min(tree[idx], tree[idx^1]);
  };

  auto query = [&](ll l, ll r) -> ll
  {
    ll res = inf;
    for (l += m, r += m; l <= r; l >>= 1, r >>= 1) {
        if (l&1) res = min(res, tree[l++]);
        if ((r&1)^1) res = min(res,tree[r--]);
    }
    return res;
  };
  assert(m == n - 1);
  for(ll i = 1; i <= m; ++i) {
    update(i, change[i]);
  }
  while(Q--) {
    ll qt;
    cin >> qt;
    if(qt == 1) {
      ll idx, w;
      cin >> idx >> w;
      update(idx, w);
    }
    else if(qt == 2) {
      ll u, w;
      cin >> u >> w;
      ll l = 1, r = u - 1, l_ans = u, r_ans = u;
      while(l <= r) {
        ll mid = (l + r) / 2;
        if(query(mid, u-1) >= w) {
          r = mid - 1;
          l_ans = mid;
        }
        else {
          l = mid + 1;
        }
      }
      l = u, r = m;
      while(l <= r) {
        ll 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(ll i = 1; i <= m; ++i) {
    ll u, v, c;
    cin >> u >> v >> c;
    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;
}

• Subtask 1: 13 / 13
• Subtask 2: 0 / 16
• Subtask 3: 0 / 17
• Subtask 4: 0 / 14
• Subtask 5: 0 / 13
• Subtask 6: 0 / 27