Advertisement
Guest User

Untitled

a guest
Apr 25th, 2018
65
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.89 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. #define ll long long
  4. #define pb push_back
  5. #define vi vector<int>
  6. #define sz(a) (int((a).size()))
  7. #define mp make_pair
  8. #define f first
  9. #define s second
  10. #define pii pair<int, int>
  11.  
  12. using namespace std;
  13.  
  14. const int N = 100100;
  15. int n, m;
  16. pii a[N];
  17. vi vals, q;
  18.  
  19.  
  20. struct event {
  21.     int type;
  22.     int len, id;
  23.    
  24.     event() {}
  25.     event(int _type, int _len, int _id) {
  26.         type = _type;
  27.         len = _len;
  28.         id = _id;
  29.     }
  30.    
  31.     bool operator < (event other) {
  32.         return type < other.type;      
  33.     }
  34. };
  35.  
  36. vector<event> events[N + N + N];
  37. map<int, int> id;
  38. int ans[N];
  39. set<pii> lens;
  40.  
  41. int main() {
  42.     ios_base::sync_with_stdio(0), cin.tie(0);
  43.    
  44.     cin >> n;
  45.     for (int i = 1; i <= n; i++) {
  46.         int l, r;
  47.         cin >> l >> r;
  48.         r++;
  49.         a[i] = mp(l, r);
  50.         vals.pb(l);
  51.         vals.pb(r);
  52.     }
  53.    
  54.     cin >> m;
  55.     for (int i = 1; i <= m; i++) {
  56.         int x;
  57.         cin >> x;
  58.         vals.pb(x);
  59.         q.pb(x);
  60.     }
  61.    
  62.     sort(vals.begin(), vals.end());
  63.     vals.resize(unique(vals.begin(), vals.end()) - vals.begin());
  64.     for (int i = 0; i < sz(vals); i++) {
  65.         id[vals[i]] = i + 1;
  66.     }
  67.    
  68.     for (int i = 1; i <= n; i++) {
  69.         int l = a[i].f, r = a[i].s;
  70.         int len = r - l;
  71.         l = id[l], r = id[r];
  72.         events[l].pb(event(0, len, i));
  73.         events[r].pb(event(1, len, i));
  74.     }
  75.    
  76.     for (int i = 0; i < sz(q); i++) {
  77.         int x = q[i];
  78.         x = id[x];
  79.         events[x].pb(event(2, 0, i + 1));
  80.     }
  81.        
  82.     for (int i = 1; i <= sz(vals); i++) {
  83.         sort(events[i].begin(), events[i].end());
  84.     }
  85.    
  86.     for (int i = 1; i <= sz(vals); i++) {
  87.         for (int j = 0; j < sz(events[i]); j++) {
  88.             int len = events[i][j].len, type = events[i][j].type, id = events[i][j].id;
  89.             if (type == 0) {
  90.                 lens.insert(mp(len, id));
  91.             } else if (type == 1) {
  92.                 lens.erase(mp(len, id));
  93.             } else {
  94.                 if (lens.empty()) ans[id] = -1;
  95.                 else ans[id] = (*lens.begin()).s;
  96.             }
  97.         }
  98.     }
  99.    
  100.     for (int i = 1; i <= m; i++) {
  101.         cout << ans[i] << "\n";
  102.     }
  103.    
  104.     return 0;
  105. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement