fork download
copy 
  1. #include <bits/stdc++.h> 
  2.  
  3. using namespace std;
  4.  
  5. #define endl "\n" 
  6. typedef long long int ll;
  7. typedef vector<int> vi;
  8.  
  9.  
  10. int main(){
  11.     int t;
  12.     cin>>t;
  13.  
  14.     for(int testcase=0; testcase<t; testcase++){
  15.         int n; cin>>n;
  16.  
  17.         vector<pair<int, int>> v(n);
  18.         map<pair<int, int>, int> m;
  19.         for (int i = 0; i < n; i++)
  20.         {
  21.             cin>>v[i].first>>v[i].second;
  22.             m[v[i]]++;
  23.         }
  24.  
  25.         vector<pair<int, int>> l;
  26.         vector<pair<int, int>> r;
  27.  
  28.         for(int i=0; i<v.size(); i++){
  29.             l.push_back({v[i].first, i});
  30.             r.push_back({v[i].second, i});
  31.         }
  32.  
  33.         sort(l.begin(), l.end(), [](pair<int, int> a, pair<int, int> b){
  34.             return a.first < b.first;
  35.         });
  36.  
  37.  
  38.         sort(r.begin(), r.end(), [](pair<int, int> a, pair<int, int> b){
  39.             return a.first > b.first;
  40.         });
  41.  
  42.         vi R(n);
  43.         vi L(n);
  44.  
  45.         set<int> predictor;
  46.         for(auto item:l){
  47.             auto it = predictor.lower_bound(v[item.second].second);
  48.  
  49.             if(it!=predictor.end()){
  50.                 R[item.second] = *it;
  51.             }
  52.  
  53.             predictor.insert(v[item.second].second);
  54.         }
  55.  
  56.         // cout<<"theend";
  57.  
  58.         predictor.clear();
  59.         for(auto item:r){
  60.             auto it = predictor.upper_bound(v[item.second].first);
  61.  
  62.             if(it!=predictor.end()){
  63.                 L[item.second] = *prev(it);
  64.             }
  65.  
  66.             predictor.insert(v[item.second].first);
  67.         }
  68.  
  69.         for (int i = 0; i < n; i++) {
  70.             int res;
  71.             if (m[v[i]] >= 2) {
  72.                 res = 0;
  73.             } else {
  74.                 res = R[i] - L[i] - (v[i].second - v[i].first);
  75.                 // res = R[i];
  76.             }
  77.  
  78.             cout<<res<<endl;
  79.         }
  80.  
  81.     }
  82.  
  83.     return 0;
  84. }
Success #stdin #stdout 0s 5288KB
comments (?)
stdin
copy 
4
3
3 8
2 5
4 5
2
42 42
1 1000000000
3
42 42
1 1000000000
42 42
6
1 10
3 10
3 7
5 7
4 4
1 2
stdout
copy 
-5
-6
4
1000000000
-999999999
0
-999999999
0
-9
3
6
5
4
8
https://ideone.com/9lCyPe
language:
C++14 (clang 8.0)
created:
3 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!