fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using ll = long long;
  5.  
  6. const ll oo = 2e18;
  7. const int N = 2e5+5;
  8. const int M = 3e4+5;
  9.  
  10. struct Cand {
  11.     ll dist;
  12.     int r, c;
  13.     int u, v;
  14.     bool operator<(const Cand& o) const {
  15.         if (dist != o.dist) return dist > o.dist;
  16.         if (r != o.r) return r < o.r;
  17.         return c < o.c;
  18.     } 
  19. };
  20.  
  21. int n, m, mask[N];
  22. pair<int, int> history[M];
  23.  
  24. set<int> rows;
  25. set<Cand> pool;
  26. Cand gap[N], partial[N];
  27.  
  28. ll get_dist(int r, int c, int idx) {
  29.     if (idx <= 0 || idx > n) return oo;
  30.     ll d = oo;
  31.     if (mask[idx] & 1) d = min(d, 1LL * (r - idx) * (r - idx) + 1LL * (c - 1) * (c - 1));
  32.     if (mask[idx] & 2) d = min(d, 1LL * (r - idx) * (r - idx) + 1LL * (c - 2) * (c - 2));
  33.     return d;
  34. }
  35.  
  36. Cand calc(int u, int v) {
  37.     Cand best = {-1, -1, -1, u, v};
  38.     if (u == v) {
  39.         if (__builtin_popcount(mask[u]) == 1) {
  40.             best.r = u;
  41.             best.c = (mask[u] & 1) ? 2 : 1;
  42.             best.dist = 1;
  43.         }
  44.         return best;
  45.     }
  46.     if (u == 0 && v == n + 1) return {oo, 1, 1, 0, n + 1};
  47.     if (u + 1 > v - 1) return best;
  48.  
  49.     auto update = [&](int r, int c) {
  50.         ll d = min(get_dist(r, c, u), get_dist(r, c, v));
  51.         Cand cur = {d, r, c, u, v};
  52.         if (best.dist == -1 || cur < best) best = cur;
  53.     };
  54.  
  55.     if (u == 0) {
  56.         for (int c = 1; c <= 2; c++) update(1, c);
  57.     } else if (v == n + 1) {
  58.         for (int c = 1; c <= 2; c++) update(n, c);
  59.     } else {
  60.         int mid = (u + v) / 2;
  61.         for (int r = max(u + 1, mid - 1); r <= min(v - 1, mid + 1); r++)
  62.             for (int c = 1; c <= 2; c++) update(r, c);
  63.     }
  64.     return best;
  65. }
  66.  
  67. void remove(int u, int v) {
  68.     Cand &temp = (u == v) ? partial[u] : gap[u];
  69.     if (temp.dist != -1) {
  70.         pool.erase(temp);
  71.         temp.dist = -1;
  72.     }
  73. }
  74.  
  75. void add(int u, int v) {
  76.     Cand res = calc(u, v);
  77.     if (res.dist != -1) {
  78.         pool.insert(res);
  79.         if (u == v) partial[u] = res;
  80.         else gap[u] = res;
  81.     }
  82. }
  83.  
  84. void solve() {
  85.     cin >> n >> m;
  86.  
  87.     rows.insert(0);
  88.     rows.insert(n + 1);
  89.     for (int i = 0; i <= n + 1; i++) {
  90.         gap[i].dist = -1;
  91.         partial[i].dist = -1;
  92.     }
  93.     add(0, n + 1);
  94.  
  95.     for (int i = 1; i <= m; i++) {
  96.         char op; cin >> op;
  97.         if (op == 'E') {
  98.             Cand best = *pool.begin();
  99.             int r = best.r, c = best.c;
  100.             cout << r << ' ' << c << '\n';
  101.  
  102.             history[i] = {r, c};
  103.             int u = best.u, v = best.v;
  104.             remove(u, v);
  105.             if (u == v) {
  106.                 auto it = rows.find(r);
  107.                 int prv = *prev(it), nxt = *next(it);
  108.                 remove(prv, r); remove(r, nxt);
  109.  
  110.                 mask[r] |= (1 << (c - 1));
  111.  
  112.                 add(prv, r); add(r, nxt);
  113.             } else {
  114.                 auto it = rows.upper_bound(r);
  115.                 int prv = *prev(it), nxt = *it;
  116.  
  117.                 mask[r] |= (1 << (c - 1));
  118.                 rows.insert(r);
  119.  
  120.                 add(prv, r); add(r, nxt); add(r, r);
  121.             }
  122.         } else if (op == 'L') {
  123.             int p; cin >> p;
  124.             int r = history[p].first, c = history[p].second;
  125.  
  126.             auto it = rows.find(r);
  127.             int prv = *prev(it), nxt = *next(it);
  128.             remove(prv, r); remove(r, nxt); remove(r, r);
  129.  
  130.             mask[r] &= ~(1 << (c - 1));
  131.             if (__builtin_popcount(mask[r]) == 0) {
  132.                 rows.erase(it); add(prv, nxt);
  133.             } else {
  134.                 add(prv, r); add(r, nxt); add(r, r);
  135.             }
  136.         }
  137.     }
  138. }
  139.  
  140. int main() {
  141.     ios_base::sync_with_stdio(false); cin.tie(NULL);
  142.  
  143.     #define TASK "XLH"
  144.     if (fopen(TASK".INP", "r")) {
  145.         freopen(TASK".INP", "r", stdin);
  146.         freopen(TASK".OUT", "w", stdout);
  147.     }
  148.  
  149.     int tests = 1; // cin >> tests;
  150.     while (tests--) solve();
  151.  
  152.     #ifdef LOCAL
  153.     cerr << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
  154.     #endif
  155.     return 0;
  156. }
Success #stdin #stdout 0s 7776KB
comments (?)
stdin
copy 
10 9
E
E
E
E
L 3
E
E
L 6
E
stdout
copy 
1 1
10 2
5 2
7 1
4 2
2 2
4 1
https://ideone.com/GIjGnr
language:
C++14 (gcc 8.3)
created:
19 hours 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!