제출 #1044974

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1044974		MercubytheFirst	다리 (APIO19_bridges)	C++17	13 / 100	128 ms	12892 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<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 * n);

  auto update = [&](int idx, int val) -> void
  { 
    for(tree[idx += n] = 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 += n, r += n; l <= r; l >>= 1, r >>= 1) {
      if(l % 2 == 1) {
        ans = min(ans, tree[l++]);
      }
      if(r % 2 == 0) {
        ans = min(ans, tree[r--]);
      }
    }
    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;
    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