fork download
copy 
  1. // F.R.I.E.N.D.S
  2. // Time Complexity:- O(NlogN)
  3. // Space Complexity:- O(N)
  4.  
  5. // Idea?
  6. // 1. For Each index 'i', find the set of those intervals which contains 'i'
  7. // 2. If you have set of intervals which contains i, store the indices of those intervals in a Fenwick Tree
  8. // 3. Now, answer for current index 'i' will be Sum(Y[i]) - Sum(X[i] - 1)
  9. // 4. Remember Friendship (i, i) won't be counted.
  10. // 5. Remember Frienship (i, j) and (j, i) are same.
  11. // 6. Hence, our answer is friendship / 2
  12.  
  13. #include <bits/stdc++.h>
  14. using namespace std;
  15.  
  16. void Saraff(){
  17.     int N;
  18.     cin >> N;
  19.  
  20.     vector <array <int, 3>> store;
  21.     vector <int> X(N + 1), Y(N + 1), BIT(N + 1);
  22.  
  23.     for(int i=1; i<=N; i++){
  24.         cin >> X[i] >> Y[i];
  25.  
  26.         store.push_back({X[i], Y[i], i});
  27.     }
  28.  
  29.     auto Add = [&](int pos, int value){
  30.         while(pos <= N){
  31.             BIT[pos] += value;
  32.             pos += pos & -pos;
  33.         }
  34.     };
  35.  
  36.     auto Sum = [&](int pos){
  37.         int res = 0;
  38.         while(pos > 0){
  39.             res += BIT[pos];
  40.             pos -= pos & -pos;
  41.         }
  42.         return res;
  43.     };
  44.  
  45.     sort(store.begin(), store.end());
  46.  
  47.     int j = 0;
  48.     priority_queue <array <int, 2>> pq;
  49.  
  50.     int friendship = 0;
  51.     for(int i=1; i<=N; i++){
  52.         // insert all those end time whose whose start time <= i
  53.         while(j < N && store[j][0] <= i){
  54.             Add(store[j][2], 1);
  55.             pq.push({-store[j][1], store[j][2]});
  56.             j++;
  57.         }
  58.  
  59.         // remove all those end time which is strictly less than i
  60.         while(!pq.empty() && -pq.top()[0] < i){
  61.             Add(pq.top()[1], -1);
  62.             pq.pop();
  63.         }
  64.  
  65.         friendship += Sum(Y[i]) - Sum(X[i] - 1);
  66.         if(Sum(i) - Sum(i - 1) > 0){
  67.             friendship--;
  68.         }
  69.     }
  70.  
  71.     cout << friendship / 2 << "\n";
  72. }
  73.  
  74. signed main(){
  75.     ios_base::sync_with_stdio(false);
  76.     cin.tie(nullptr);
  77.     cout.tie(nullptr);
  78.  
  79.     int test = 1;
  80.     cin>>test;
  81.  
  82.     while(test--){
  83.         Saraff();
  84.     }
  85. }
Success #stdin #stdout 0.01s 5516KB
comments (?)
stdin
copy 
1
6
2 4
1 3
5 6
1 2
1 2
1 6
stdout
copy 
3
https://ideone.com/nFbIVE
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
secret

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!