vlatkovski

piepie fail again

Apr 11th, 2021
445
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef pair<int, int> pii;
  4.  
  5. const int N = 100100;
  6. const int M = 1<<19;
  7.  
  8. int n, D;
  9. pii vec[2][2*N];
  10. int pos[2][2*N];
  11. int dist[2][2*N];
  12.  
  13. struct segtree {
  14.     bitset<M> tree;
  15.     segtree() {
  16.         tree.set(); // all to 1
  17.     }
  18.     int query(int v, int tl, int tr, int r) {
  19.         if (tree[v] == 0) return -1;
  20.         if (tl == tr) return tl;
  21.         int tm = (tl + tr) / 2;
  22.         if (r <= tm) {
  23.             return query(2*v, tl, tm, r);
  24.         } else if (tree[2*v+1] == 1) {
  25.             return query(2*v+1, tm+1, tr, r);
  26.         } else {
  27.             return query(2*v, tl, tm, tm);
  28.         }
  29.     }
  30.     void update(int v, int tl, int tr, int i) {
  31.         if (tl == tr) {
  32.             tree[v] = 0;
  33. //          cout << "updated leaf " << tl << " to 0\n";
  34.             return;
  35.         }
  36.         int tm = (tl + tr) / 2;
  37.         if (i <= tm) {
  38.             update(2*v, tl, tm, i);
  39.         } else {
  40.             update(2*v+1, tm+1, tr, i);
  41.         }
  42.         tree[v] = tree[2*v] | tree[2*v+1];
  43.     }
  44. } tree[2];
  45.  
  46. int main() {
  47.     cin.tie(0)->sync_with_stdio(false);
  48.     #ifndef _DEBUG
  49.     freopen("piepie.in", "r", stdin);
  50.     freopen("piepie.out", "w", stdout);
  51.     #endif
  52.     cin >> n >> D;
  53.     for (int i = 0; i < 2*n; ++i) {
  54.         for (int j = 0; j < 2; ++j) {
  55.             cin >> vec[j][i].first;
  56.             vec[j][i].second = i;
  57.         }
  58.     }
  59.     for (int j = 0; j < 2; ++j) {
  60.         sort(vec[j], vec[j]+2*n);
  61.         for (int i = 0; i < 2*n; ++i) {
  62.             pos[j][vec[j][i].second] = i;
  63.         }
  64.     }
  65.     memset(dist, -1, sizeof(dist));
  66.     deque<tuple<int, int, int>> q;
  67.     for (int j = 0; j < 2; ++j) {
  68.         for (int i = 0; i < 2*n; ++i) {
  69.             int val = vec[j][i].first;
  70.             if (val == 0) {
  71.                 // source
  72.                 dist[j][i] = 0;
  73.                 q.emplace_front(j, i, val);
  74.                 tree[j].update(1, 0, 2*n-1, i);
  75.             }
  76.         }
  77.     }
  78.     while (!q.empty()) {
  79.         int j, i, minval;
  80.         tie(j, i, minval) = q.front();
  81.         q.pop_front();
  82.         int id = vec[j][i].second;
  83. //      cout<<"(j="<<j<<", i="<<i<<", minval="<<minval<<", val="<<val<<", id="<<id<<")\n";
  84.         // move up
  85.         int p = tree[j].query(1, 0, 2*n-1, i-1);
  86. //      cout << "if moving up p="<<p<<"\n";
  87.         if (p != -1 && dist[j][p] == -1 && vec[j][p].first >= minval) {
  88. //          cout << "moving up, p="<<p<<"\n";
  89.             dist[j][p] = dist[j][i];
  90.             q.emplace_front(j, p, minval);
  91.             tree[j].update(1, 0, 2*n-1, p);
  92.         }
  93.         // move to other side
  94.         p = pos[1-j][id];
  95.         if (dist[1-j][p] == -1) {
  96. //          cout << "moving side, p="<<p<<"\n";
  97.             dist[1-j][p] = dist[j][i] + 1;
  98.             int val_other = vec[1-j][p].first;
  99.             q.emplace_back(1-j, p, val_other-D);
  100.             tree[1-j].update(1, 0, 2*n-1, p);
  101.         }
  102.     }
  103.     for (int id = 0; id < n; ++id) {
  104.         int i = pos[0][id];
  105.         cout << dist[0][i] << '\n';
  106.     }
  107. }
  108.  
RAW Paste Data

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×