fork download
copy 
  1. /// KoJa
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. #define task "test"
  5. #define pb push_back
  6. #define SZ(a) (a).begin(), (a).end()
  7. #define SZZ(a, Begin, End) (a) + (Begin), (a) + (Begin) + (End)
  8. #define BIT(a) (1LL << (a))
  9. #define vec vector
  10. #define fi first
  11. #define se second
  12. #define mp make_pair
  13. #define MASK(x, i) (((x) >> (i))&1)
  14.  
  15. typedef long long ll;
  16. typedef pair<int, int> ii;
  17.  
  18. template <class T>
  19. inline bool maximize(T &a, const T &b) { return (a < b ? (a = b, 1) : 0); }
  20. template <class T>
  21. inline bool minimize(T &a, const T &b) { return (a > b ? (a = b, 1) : 0); }
  22. void fastio()
  23. {
  24.     ios_base::sync_with_stdio(NULL);
  25.     cin.tie(NULL);
  26.     if (fopen(task ".inp", "r"))
  27.     {
  28.         freopen(task ".inp", "r", stdin);
  29.         freopen(task ".out", "w", stdout);
  30.     }
  31.     else if (fopen(task ".in", "r"))
  32.     {
  33.         freopen(task ".in", "r", stdin);
  34.         freopen(task ".out", "w", stdout);
  35.     }
  36. }
  37. const int N = int(1e6) + 5;
  38. const ll INF = 1e18;
  39. int n, m;
  40. struct Rectangle
  41. {
  42.     int x, y, u, v;
  43.     Rectangle(){}
  44.     Rectangle(int _x, int _y, int _u, int _v)
  45.     {
  46.         x = _x;
  47.         y = _y;
  48.         u = _u;
  49.         v = _v;
  50.     }
  51. } rect[N], queries[N];
  52.  
  53. struct Line
  54. {
  55.     int x, l, r, id, type;
  56.     Line(){}
  57.     Line(int _x, int _l, int _r, int _id, int _type)
  58.     {
  59.         x = _x;
  60.         l = _l;
  61.         r = _r;
  62.         id = _id;
  63.         type = _type;
  64.     }
  65.     bool operator < (const Line &other) { return ((x < other.x)||((x == other.x)&&(type < other.type)));}
  66. };
  67.  
  68. vec<ii> points;
  69. vec<int> val;
  70. vec<Line> sweepline;
  71. void init()
  72. {
  73.     cin >> n >> m;
  74.     ++n;
  75.     rect[1] = Rectangle(-1e9, -1e9, 1e9, 1e9);
  76.     val.pb(-1e9);
  77.     val.pb(1e9);
  78.     for(int i = 2; i <= n; i++)
  79.     {
  80.         cin >> rect[i].x >> rect[i].y >> rect[i].u >> rect[i].v;
  81.         val.pb(rect[i].y);
  82.         val.pb(rect[i].v);
  83.     }
  84.     for(int i = 1; i <= m; i++)
  85.     {
  86.         cin >> queries[i].x >> queries[i].y >> queries[i].u >> queries[i].v;
  87.         val.pb(queries[i].y);
  88.         val.pb(queries[i].v);
  89.     }
  90. }
  91. vec<vec<int>> adj(N);
  92. int depth[N], par[N][20], parPoints[N];
  93. void dfs(int u, int p)
  94. {
  95.     for(int v : adj[u])
  96.     {
  97.         if(v == p)
  98.             continue;
  99.         par[v][0] = u;
  100.         depth[v] = depth[u] + 1;
  101.         dfs(v, u);
  102.     }
  103. }
  104. int lca(int u, int v)
  105. {
  106.     if(depth[u] < depth[v])
  107.         swap(u, v);
  108.     for(int i = 19; i >= 0; i--)
  109.         if(depth[par[u][i]] >= depth[v])
  110.             u = par[u][i];
  111.     if(u == v)
  112.         return u;
  113.     for(int i = 19; i >= 0; i--)
  114.         if(par[u][i] != par[v][i])
  115.         {
  116.             u = par[u][i];
  117.             v = par[v][i];
  118.         }
  119.     return par[u][0];
  120. }
  121. int getDist(int u, int v)
  122. {
  123.     return depth[u] + depth[v] - 2 * depth[lca(u, v)];
  124. }
  125. ii qu[N];
  126. class SegmentTree
  127. {
  128. private:
  129.     int n;
  130.     vec<int> st, lz;
  131.     void pushDown(int id)
  132.     {
  133.         if(lz[id] == 0)
  134.             return;
  135.         st[2 * id] = lz[id];
  136.         st[2 * id + 1] = lz[id];
  137.         lz[2 * id] = lz[id];
  138.         lz[2 *id + 1] = lz[id];
  139.         lz[id] = 0;
  140.     }
  141.     void update(int u, int v, int val, int l, int r, int id)
  142.     {
  143.         if((u > v)||(l > r)||(l > v)||(u > r))
  144.             return;
  145.         if((u <= l)&&(r <= v))
  146.         {
  147.             st[id] = val;
  148.             lz[id] = val;
  149.             return;
  150.         }
  151.         pushDown(id);
  152.         int mid = (l + r) >> 1;
  153.         update(u, v, val, l, mid, 2*id);
  154.         update(u, v, val, mid + 1, r, 2*id + 1);
  155.         if(st[2 * id])
  156.             st[id] = st[2 * id];
  157.         if(st[2*id + 1])
  158.             st[id] = st[2*id + 1];
  159.     }
  160.     int getVal(int pos, int l, int r, int id)
  161.     {
  162.         if((l > r)||(l > pos)||(pos > r))
  163.             return 0;
  164.         if(l == r)
  165.             return st[id];
  166.         pushDown(id);
  167.         int mid = (l + r) >> 1;
  168.         int res = 0;
  169.         if(pos <= mid)
  170.             res = max(res, getVal(pos, l, mid, 2*id));
  171.         else
  172.             res = max(res, getVal(pos, mid + 1, r, 2*id + 1));
  173.         return res;
  174.     }
  175. public:
  176.     SegmentTree(int _n = 0)
  177.     {
  178.         this->n = _n;
  179.         st = lz = vec<int>(4 * n + 7, 0);
  180.     }
  181.     void update(int l, int r, int val) { return update(l, r, val, 1, n, 1);}
  182.     int getVal(int pos) { return getVal(pos, 1, n, 1);}
  183. } it;
  184. void process(const int &tc)
  185. {
  186.     sort(SZ(val));
  187.     val.erase(unique(SZ(val)), val.end());
  188.     for(int i = 1; i <= m; i++)
  189.     {
  190.         queries[i].y = lower_bound(SZ(val), queries[i].y) - val.begin() + 1;
  191.         queries[i].v = lower_bound(SZ(val), queries[i].v) - val.begin() + 1;
  192.         points.pb(ii(queries[i].x, queries[i].y));
  193.         points.pb(ii(queries[i].u, queries[i].v));
  194.     }
  195.     sort(SZ(points));
  196.     points.erase(unique(SZ(points)), points.end());
  197.     for(int i = 1; i <= n; i++)
  198.     {
  199.         rect[i].y = lower_bound(SZ(val), rect[i].y) - val.begin() + 1;
  200.         rect[i].v = lower_bound(SZ(val), rect[i].v) - val.begin() + 1;
  201.         sweepline.pb(Line(rect[i].x, rect[i].y, rect[i].v, i, 0));
  202.         sweepline.pb(Line(rect[i].u, rect[i].y, rect[i].v, i, 2));
  203.     }
  204.     for(int i = 1; i <= m; i++)
  205.     {
  206.         int id1 = lower_bound(SZ(points), ii(queries[i].x, queries[i].y)) - points.begin() + 1;
  207.         int id2 = lower_bound(SZ(points), ii(queries[i].u, queries[i].v)) - points.begin() + 1;
  208.         qu[i] = ii(id1, id2);
  209.     }
  210.  
  211.     for(int i = 1; i <= (int)points.size(); i++)
  212.         sweepline.pb(Line(points[i - 1].fi, points[i - 1].se, points[i - 1].se, i, 1));
  213.  
  214.  
  215.  
  216.  
  217.     sort(SZ(sweepline));
  218.     it = SegmentTree((int)val.size());
  219.     for(auto &x : sweepline) {
  220.         if(x.type == 2)
  221.         {
  222.             it.update(x.l, x.r, par[x.id][0]);
  223.         }
  224.         else
  225.         {
  226.             int u = it.getVal(x.r);
  227.             if(u != 0)
  228.             {
  229.                 if(x.type == 0)
  230.                 {
  231.                     par[x.id][0] = u;
  232.                     adj[x.id].pb(u);
  233.                     adj[u].pb(x.id);
  234.                 }
  235.                 else
  236.                     parPoints[x.id] = u;
  237.             }
  238.             if(x.type == 0)
  239.             {
  240.                 it.update(x.l, x.r, x.id);
  241.             }
  242.         }
  243.     }
  244.     depth[0] = -1;
  245.     depth[1] = 0;
  246.     dfs(1, -1);
  247.     for(int i = 1; i < 20; i++)
  248.         for(int u = 1; u <= n + 1; u++)
  249.             par[u][i] = par[par[u][i - 1]][i - 1];
  250.     for(int i = 1; i <= m; i++)
  251.         cout << getDist(parPoints[qu[i].fi], parPoints[qu[i].se]) << '\n';
  252. }
  253. int main()
  254. {
  255.     fastio();
  256.     int t = 1;
  257.     // cin >> t;
  258.     for (int i = 1; i <= t; i++)
  259.     {
  260.         init();
  261.         process(i);
  262.     }
  263.     return 0;
  264. }
  265. /*
  266.     l <= u && v <= r
  267. */
  268.  
  269.  
Success #stdin #stdout 0.01s 32616KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/ibtXbv
language:
C++14 (gcc 8.3)
created:
19 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!