fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define for1(i,m,n) for(int i=m,n_=(n);i<=n_;i++)
  5. #define for0(i,m,n) for(int i=m;i<n;i++)
  6. #define forr1(i,m,n) for(int i=m;i>=n;i--)
  7. #define forr2(i,m,n) for(int i=m;i>n;i--)
  8. #define mini(a,b) (a)=min((a),(b))
  9. #define maxi(a,b) (a)=max((a),(b))
  10. #define ll long long
  11. #define el '\n'
  12. #define fi first
  13. #define se second
  14. #define ii pair<int,int>
  15. #define vll(i) i.begin(),i.end()
  16. #define pb push_back
  17. #define fr front()
  18.  
  19. #define MASK(i) ((1ll) << (i))
  20. #define BIT(i,n) (((i)>>(n))&1)
  21.  
  22. const int N=1e5+11;
  23. const ll MOD=1e18;
  24. struct tri{
  25.  int val,x,y;
  26.  bool operator < (const tri &other ) const {
  27.   return val<other.val;
  28.  }
  29. };
  30. int dsu[N],a[N];
  31. vector<tri>adj;
  32. vector<int>s;
  33. vector<ii>ans;
  34. unordered_map<int,ll>ans_;
  35. int findd(int x){
  36.   if(dsu[x]==0) return x;
  37.   return dsu[x]=findd(dsu[x]);
  38. }
  39. void mergee(int x,int y){
  40.   if(y>x) swap(x,y);
  41.   a[x]+=a[y];
  42.   dsu[y]=x;
  43. }
  44. int main() {
  45.     ios::sync_with_stdio(0);
  46.     cin.tie(0);
  47.     cout.tie(0);
  48. freopen("costquery.inp", "r", stdin);
  49. freopen("costquery.out", "w", stdout);
  50. int n,q;cin>>n>>q;
  51. for0(i,1,n) {
  52.   int x,y,val;cin>>x>>y>>val;
  53.   adj.pb({val,x,y});
  54. }
  55. sort(vll(adj));
  56.  
  57. for1(i,1,q){
  58.  int l,r;cin>>l>>r;
  59.  l--;
  60.  ans.pb({l,r});
  61.  s.pb(l);
  62.  s.pb(r);
  63. }
  64. sort(vll(s));
  65. s.erase(unique(vll(s)),s.end());
  66. ll numpair=0;
  67. auto adj_=adj.begin();
  68. for1(i,1,n) a[i]=1;
  69. for(auto s_:s){
  70.  
  71.     while(adj_!=adj.end()){
  72.             auto [val,x,y]=*adj_;
  73.     if(val>s_) break;
  74.         int x_=findd(x),y_=findd(y);
  75.         //cout<<x_<<' '<<y_<<el;
  76.         numpair+=1ll*a[x_]*a[y_];
  77.         //cout<<numpair<<el<<el;
  78.         mergee(x_,y_);
  79.         adj_++;
  80.     }
  81.     ans_[s_]=numpair;
  82. }
  83. //for1(i,1,n) cout<<i<<' '<<findd(i)<<el;
  84. for(auto [l,r]:ans){
  85.     cout<<ans_[r]-ans_[l]<<' ' ;
  86. }
  87. }
  88.  
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/dPmEqu
truy van l r cho biet bao nhieu canh trong so cuc dai
language:
C++14 (gcc 8.3)
created:
8 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!