fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. //#include <ext/pb_ds/assoc_container.hpp>
  4. //using namespace __gnu_pbds;
  5. //typedef tree<int,null_type,less<int>,rb_tree_tag,
  6. //tree_order_statistics_node_update> indexed_set;
  7. #define pb push_back
  8. #define eb emplace_back
  9. #define mp make_pair
  10. #define pii pair<int,int>
  11. #define pll pair<long long , long long>
  12. #define vi vector<int>
  13. #define vpii vector<pii>
  14. #define SZ(x) ((int)(x.size()))
  15. #define fi first
  16. #define se second
  17. #define FOR(i,n) for(int (i)=0;(i)<(n);++(i))
  18. #define FORI(i,n) for(int (i)=1;(i)<=(n);++(i))
  19. #define IN(x,y) ((y).find((x))!=(y).end())
  20. #define ALL(t) t.begin(),t.end()
  21. #define FOREACH(i,t) for (typeof(t.begin()) i=t.begin(); i!=t.end(); i++)
  22. #define REP(i,a,b) for(int (i)=(a);(i)<=(b);++i)
  23. #define REPD(i,a,b) for(int (i)=(a); (i)>=(b);--i)
  24. #define REMAX(a,b) (a)=max((a),(b));
  25. #define REMIN(a,b) (a)=min((a),(b));
  26. #define DBG cerr << "debug here" << endl;
  27. #define DBGV(vari) cerr << #vari<< " = "<< (vari) <<endl;
  28. #define nn <<' '<<
  29. #define ln <<'\n'
  30. #define io_faster ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  31. //template <typename T>
  32. //inline void read(T& x){
  33. //    bool Neg = false;
  34. //    char c;
  35. //    for (c = getchar(); c < '0' | c > '9'; c = getchar())
  36. //        if (c == '-') Neg = !Neg;
  37. //    x = c - '0';
  38. //    for (c = getchar(); c >= '0' && c <= '9'; c = getchar())
  39. //        x = x * 10 + c - '0';
  40. //    if (Neg) x = -x;
  41. //}
  42.  
  43. //template <typename T>
  44. //inline void write(T x)
  45. //{
  46. //    if (x < 0)
  47. //    {
  48. //        putchar('-'); x = -x;
  49. //    }
  50. //    T p = 1;
  51. //    for (T temp = x / 10; temp > 0; temp /= 10) p *= 10;
  52. //    for (; p > 0; x %= p, p /= 10) putchar(x / p + '0');
  53. //}
  54.  
  55. #define PROB "piepie"
  56. void file(){
  57.     if(fopen(PROB".in", "r")){
  58.         freopen(PROB".in","r",stdin);
  59.         freopen(PROB".out","w",stdout);
  60.     }
  61. }
  62. void sinh_(){
  63. //    srand(time(0));
  64. //    freopen(PROB".inp" , "w" , stdout);
  65. //    int n;
  66. }
  67. typedef long long ll;
  68. const int INF = 1e9;
  69. const int N = 1e5 + 5;
  70. int n , d , dis[2*N];
  71. int a[2*N] , b[2*N];
  72. struct cmpA{
  73.     bool operator()(const int &x , const int &y) const{
  74.         return b[x] > b[y];
  75.     }
  76. };
  77. struct cmpB{
  78.     bool operator() (const int &x , const int &y) const{
  79.         return a[x] > a[y];
  80.     }
  81. };
  82. multiset<int, cmpA> sA;
  83. multiset<int, cmpB> sB;
  84. deque<int> que;
  85. void readip(){
  86.     cin >> n >> d;
  87.     FOR(i , 2*n){
  88.         cin >> a[i] >> b[i];
  89.         dis[i] = -1;
  90.     }
  91.     FOR(i , n){
  92.         if (b[i] == 0)
  93.             dis[i] = 1, que.eb(i);
  94.         else sA.insert(i);
  95.         if (a[i + n] == 0)
  96.             dis[i + n] = 1, que.eb(i + n);
  97.         else sB.insert(i + n);
  98.     }
  99. }
  100.  
  101. void solve(){
  102.     while(!que.empty()){
  103.         int u = que.front(); que.pop_front();
  104.         if (u < n){
  105.             while(1){
  106.                 auto t = sB.lower_bound(u);
  107.                 if (t == sB.end() || a[*t] + d < a[u]) break;
  108.                 dis[*t] = dis[u] + 1;
  109.                 que.eb(*t); sB.erase(t);
  110.             }
  111.         }
  112.         else{
  113.             while(1){
  114.                 auto t = sA.lower_bound(u);
  115.                 if (t == sA.end() || b[*t] + d < b[u]) break;
  116.                 dis[*t] = dis[u] + 1;
  117.                 que.eb(*t); sA.erase(t);
  118.             }
  119.         }
  120.     }
  121.     FOR(i , n) cout << dis[i] ln;
  122. }
  123.  
  124. int main(){
  125.     sinh_();
  126.     io_faster
  127.     file();
  128.     int t = 1;
  129. //    cin >> t;
  130.     while (t--){
  131.         readip();
  132.         solve();
  133.     }
  134. }
  135.  
Success #stdin #stdout 0.01s 5456KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/dE9wCZ
language:
C++14 (gcc 8.3)
created:
2 years 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!