fork download 
  1. // ~~ icebear ~~
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. #define int long long
  5. typedef long long ll;
  6. typedef pair<int, int> ii;
  7. typedef pair<int, ii> iii;
  8.  
  9. template<class T>
  10.     bool minimize(T &a, const T &b) {
  11.         if (a > b) return a = b, true;
  12.         return false;
  13.     }
  14.  
  15. template<class T>
  16.     bool maximize(T &a, const T &b) {
  17.         if (a < b) return a = b, true;
  18.         return false;
  19.     }
  20.  
  21. #define FOR(i,a,b) for(int i=(a); i<=(b); ++i)
  22. #define FORR(i,a,b) for(int i=(a); i>=(b); --i)
  23. #define REP(i, n) for(int i=0; i<(n); ++i)
  24. #define RED(i, n) for(int i=(n)-1; i>=0; --i)
  25. #define MASK(i) (1LL << (i))
  26. #define BIT(S, i) (((S) >> (i)) & 1)
  27. #define mp make_pair
  28. #define pb push_back
  29. #define fi first
  30. #define se second
  31. #define all(x) x.begin(), x.end()
  32. #define task "starofhope"
  33.  
  34. const int MOD = 1e9 + 7;
  35. const int inf = 1e9 + 27092008;
  36. const ll INF = 1e18 + 27092008;
  37. const int N = 3e5 + 5;
  38. int n, m, M, p, q, x[N], y[N], top[N], bot[N], lef[N], rig[N];
  39. vector<ii> G[2][N];
  40. vector<int> comx, comy;
  41. int dist[N][2];
  42. priority_queue<iii, vector<iii>, greater<iii>> Q;
  43. int ft[2][N];
  44. void update(int t, int x, int v) {
  45.     for(; x <= M; x += x & -x) ft[t][x] += v;
  46. }
  47. int get(int t, int x) {
  48.     int ans = 0;
  49.     for(; x; x -= x & -x) ans += ft[t][x];
  50.     return ans;
  51. }
  52. void upd(int l, int r, int v) {
  53.     update(0, l, l * v); update(0, r+1, -(r+1) * v);
  54.     update(1, l, v); update(1, r+1, -v);
  55. }
  56. int ask(int l, int r) {
  57.     return (get(1, r) * (r + 1) - get(0, r)) - (get(1, l - 1) * l - get(0, l - 1));
  58. }
  59.  
  60. vector<ii> line[N];
  61. vector<array<int, 3>> rect[N];
  62.  
  63. void buildGraph(bool S) {
  64.     if (S) {
  65.         FOR(i, 1, p + 2) swap(x[i], y[i]);
  66.         FOR(i, 1, q) {
  67.             swap(lef[i], bot[i]);
  68.             swap(rig[i], top[i]);
  69.         }
  70.         swap(comx, comy);
  71.     }
  72.  
  73.     M = p + 2 + 2 * q;
  74.     FOR(i, 1, M) line[i].clear();
  75.     FOR(i, 1, M) rect[i].clear();
  76.     FOR(i, 1, M) ft[0][i] = ft[1][i] = 0;
  77.  
  78.     FOR(i, 1, p + 2) line[x[i]].pb(mp(y[i], i));
  79.     FOR(i, 1, M) sort(all(line[i]));
  80.     FOR(i, 1, q) {
  81.         rect[lef[i]].pb({bot[i], top[i], +1ll});
  82.         rect[rig[i]+1].pb({bot[i], top[i], -1ll});
  83.     }
  84.  
  85.     FOR(i, 1, M) {
  86.         for(auto &e : rect[i]) upd(e[0], e[1], e[2]);
  87.         FOR(j, 1, (int)line[i].size() - 1) {
  88.             if (ask(line[i][j-1].fi, line[i][j].fi) == 0) {
  89.                 int u = line[i][j].se, v = line[i][j-1].se;
  90. //                cout << u << ' ' << v << ' ' << S << ' ' << comy[y[u]-1] << ' ' << comy[y[v]-1] << ' ' << abs(comy[y[u]-1] - comy[y[v]-1]) << '\n';
  91.                 G[S][u].pb(mp(v, abs(comy[y[u]-1] - comy[y[v]-1])));
  92.                 G[S][v].pb(mp(u, abs(comy[y[u]-1] - comy[y[v]-1])));
  93.             }
  94.         }
  95.     }
  96. }
  97.  
  98. void init(void) {
  99.     cin >> n >> m >> p >> q;
  100.     FOR(i, 1, p) cin >> x[i] >> y[i];
  101.     x[p + 1] = y[p + 1] = 1;
  102.     x[p + 2] = n; y[p + 2] = m;
  103.  
  104.     FOR(i, 1, p + 2) {
  105.         comx.pb(x[i]);
  106.         comy.pb(y[i]);
  107.     }
  108.  
  109.     FOR(i, 1, q) {
  110.         cin >> lef[i] >> bot[i] >> rig[i] >> top[i];
  111.         comx.pb(lef[i]); comx.pb(rig[i]);
  112.         comy.pb(bot[i]); comy.pb(top[i]);
  113.     }
  114.  
  115.     sort(all(comx)); sort(all(comy));
  116.     comx.resize(unique(all(comx)) - comx.begin());
  117.     comy.resize(unique(all(comy)) - comy.begin());
  118.  
  119.     FOR(i, 1, p + 2) {
  120.         x[i] = upper_bound(all(comx), x[i]) - comx.begin();
  121.         y[i] = upper_bound(all(comy), y[i]) - comy.begin();
  122.     }
  123.  
  124.     FOR(i, 1, q) {
  125.         lef[i] = upper_bound(all(comx), lef[i]) - comx.begin();
  126.         rig[i] = upper_bound(all(comx), rig[i]) - comx.begin();
  127.         bot[i] = upper_bound(all(comy), bot[i]) - comy.begin();
  128.         top[i] = upper_bound(all(comy), top[i]) - comy.begin();
  129.     }
  130. }
  131.  
  132. void process(void) {
  133.     REP(j, 2) buildGraph(j);
  134.     FOR(i, 1, p + 2) REP(j, 2) dist[i][j] = INF;
  135.     Q.push(mp(0, mp(p + 1, 1)));
  136.     dist[p + 1][1] = 0;
  137.     while(!Q.empty()) {
  138.         int du = Q.top().fi, u = Q.top().se.fi, t = Q.top().se.se;
  139.         Q.pop();
  140.         if (du != dist[u][t]) continue;
  141.         if (u <= p && minimize(dist[u][t^1], dist[u][t] + 1))
  142.             Q.push(mp(dist[u][t^1], mp(u, t^1)));
  143. //        cout << u << ' ' << t << ' ' << dist[u][t] << '\n';
  144.         for(ii x : G[t][u]) {
  145.             int v, w; tie(v, w) = x;
  146.             if (minimize(dist[v][t], dist[u][t] + w))
  147.                 Q.push(mp(dist[v][t], mp(v, t)));
  148.         }
  149.     }
  150.  
  151.     int ans = min(dist[p+2][0], dist[p+2][1]);
  152.     cout << (ans == INF ? -1 : ans) << '\n';
  153. //    cerr << (ans == INF ? -1 : ans) << '\n';
  154.  
  155.     FOR(i, 1, p + 2) {
  156.         G[0][i].clear();
  157.         G[1][i].clear();
  158.     }
  159.     comx.clear(); comy.clear();
  160. }
  161.  
  162. signed main() {
  163.     ios_base::sync_with_stdio(0);
  164.     cin.tie(0); cout.tie(0);
  165.     if (fopen(task".inp", "r")) {
  166.         freopen(task".inp", "r", stdin);
  167.         freopen(task".out", "w", stdout);
  168.     }
  169.     int tc = 1;
  170.     cin >> tc;
  171.     while(tc--) {
  172.         init();
  173.         process();
  174.     }
  175.     return 0;
  176. }
  177.  
Success #stdin #stdout 0.02s 42704KB
comments (?)
stdin 
Standard input is empty
stdout 
-1
https://ideone.com/7cqw8E
language:
C++14 (gcc 8.3)
created:
1 day 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!