fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <map>
  4. #include <algorithm>
  5. #include <set>
  6. using namespace std;
  7.  
  8. struct Seg{
  9.     int l, r, index;
  10. };
  11.  
  12. int main() {
  13.     cin.tie(0)->sync_with_stdio(0);
  14.     int t;
  15.     cin >> t;
  16.     while (t--) {
  17.         int n;
  18.         cin >> n;
  19.         vector<Seg> seg(n);
  20.         vector<int> ans(n, 0);
  21.         for(int i = 0; i < n; i++){
  22.             cin >> seg[i].l >> seg[i].r;
  23.             seg[i].index = i;
  24.         }
  25.         sort(seg.begin(), seg.end(), [](const Seg& a, const Seg& b) {
  26.             if (a.l != b.l) return a.l < b.l;
  27.             return a.r > b.r;
  28.         });
  29.  
  30.         set<int> r;
  31.         for(auto u: seg){
  32.             auto it = r.lower_bound(u.r);
  33.             if(it != r.end()) {
  34.                 ans[u.index] += *it - u.r;
  35.             }
  36.             r.insert(u.r);
  37.         }
  38.  
  39.         for(auto& u: seg){
  40.             u.r = - u.r;
  41.             u.l = - u.l;
  42.             swap(u.l, u.r);
  43.         }
  44.  
  45.  
  46. 		sort(seg.begin(), seg.end(), [](const Seg& a, const Seg& b) {
  47.             if (a.l != b.l) return a.l < b.l;
  48.             return a.r > b.r;
  49.         });
  50.  
  51.         set<int> l;
  52.         for(auto u: seg){
  53.             auto it = l.lower_bound(u.r);
  54.             if(it != l.end()) {
  55.                 ans[u.index] += *it - u.r;
  56.             }
  57.             l.insert(u.r);
  58.         }
  59.  
  60. 		for(int i = 1; i < seg.size(); i++){
  61. 			if(seg[i].l == seg[i-1].l && seg[i].r == seg[i-1].r){
  62. 				ans[seg[i].index] = 0;
  63. 				ans[seg[i-1].index] = 0;
  64. 			}
  65. 		}
  66.  
  67.         for(auto u: ans){
  68.             cout << u << endl;
  69.         }
  70.     }
  71.     return 0;
  72. }
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 
0
0
1
999999999
0
0
0
0
0
2
3
2
4
8
https://ideone.com/f67UV3
language:
C++ (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!