Advertisement
skaram

Untitled

Jan 25th, 2023
735
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.20 KB | None | 0 0
  1. /// @author s_k_a_r_a
  2.  
  3. #ifndef Local
  4. // #pragma GCC optimize("Ofast")
  5. #include <bits/stdc++.h>
  6. #include <ext/pb_ds/assoc_container.hpp>
  7. #define debug(...)
  8. #endif
  9.  
  10. using namespace std;
  11.  
  12. #define int long long
  13.  
  14. typedef long long ll;
  15. typedef long double ld;
  16.  
  17. using str = string;
  18. #define vec vector
  19. #define all(x) (x).begin(), (x).end()
  20. #define rall(x) (x).rbegin(), (x).rend()
  21. #define sz(x) (int)(x).size()
  22. #define pb push_back
  23.  
  24. struct st {
  25.     static const int maxn = 16ll * 1024 * 1024 * 1024 * 1024 * 1024;
  26.     static const int inf = (int)1e15;
  27.     struct node {
  28.         int mn, cnt, l, r, rb;
  29.  
  30.         node(int cnt) : mn(0), cnt(cnt), l(-1), r(-1), rb(0) {}
  31.  
  32.         node(int mn, int cnt) : mn(mn), cnt(cnt), l(-1), r(-1), rb(0) {}
  33.     };
  34.     vec<node> t;
  35.  
  36.     st() {
  37.         t.pb({maxn});
  38.     }
  39.  
  40.     int mk(int c) {
  41.         t.pb({c});
  42.         return sz(t) - 1;
  43.     }
  44.  
  45.     int mk(int mn, int c) {
  46.         t.pb({mn, c});
  47.         return sz(t) - 1;
  48.     }
  49.  
  50.     int get() {
  51.         return maxn - (t[0].mn == 0 ? t[0].cnt : 0);
  52.     }
  53.  
  54.     int lq, rq, dq;
  55.  
  56.     void upd(int i = 0, int l = 0, int r = maxn) {
  57.         if (lq <= l && r <= rq) {
  58.             t[i].rb += dq, t[i].mn += dq;
  59.             return;
  60.         }
  61.         int m = (l + r) / 2;
  62.         if (t[i].l == -1)
  63.             t[i].l = mk(t[i].mn - t[i].rb, m - l);
  64.         if (t[i].r == -1)
  65.             t[i].r = mk(t[i].mn - t[i].rb, r - m);
  66.         if (lq < m)
  67.             upd(t[i].l, l, m);
  68.         if (m < rq)
  69.             upd(t[i].r, m, r);
  70.         int mn = t[t[i].l].mn, cnt = t[t[i].l].cnt;
  71.         if (mn > t[t[i].r].mn)
  72.             mn = t[t[i].r].mn, cnt = t[t[i].r].cnt;
  73.         else if (mn == t[t[i].r].mn)
  74.             cnt += t[t[i].r].cnt;
  75.         t[i].mn = mn + t[i].rb, t[i].cnt = cnt;
  76.     }
  77.  
  78.     void query(int l, int r, int d) {
  79.         lq = l, rq = r + 1, dq = d;
  80.         upd();
  81.     }
  82. };
  83.  
  84. struct q {
  85.     int x, ly, ry, md;
  86.  
  87.     bool operator<(q c) {
  88.         return x < c.x;
  89.     }
  90. };
  91.  
  92. void solve() {  // все запросы до 10^16, а начальная точка 10^15
  93.     int k, n;
  94.     cin >> k >> n;
  95.     int x = (int)1e15, y = (int)1e15;
  96.     vec<q> qs;
  97.     char c;
  98.     for (int i = 0, t; i < n; ++i) {
  99.         cin >> c >> t;
  100.         if (c == 'N')
  101.             qs.pb({x, y, y + k - 1 + t, 0}), qs.pb({x + k, y, y + k - 1 + t, 1}), y += t;
  102.         else if (c == 'E')
  103.             qs.pb({x, y, y + k - 1, 0}), qs.pb({x + k + t, y, y + k - 1, 1}), x += t;
  104.         else if (c == 'S')
  105.             qs.pb({x, y - t, y + k - 1, 0}), qs.pb({x + k, y - t, y + k - 1, 1}), y -= t;
  106.         else
  107.             qs.pb({x - t, y, y + k - 1, 0}), qs.pb({x + k, y, y + k - 1, 1}), x -= t;
  108.     }
  109.     sort(all(qs));
  110.     int ans = 0;
  111.     st t;
  112.     for (int i = 0; i < 2 * n; ++i) {
  113.         if (qs[i].md == 0)
  114.             t.query(qs[i].ly, qs[i].ry, 1);
  115.         if (qs[i].md == 1)
  116.             t.query(qs[i].ly, qs[i].ry, -1);
  117.         if (i != 2 * n - 1)
  118.             ans += t.get() * (qs[i + 1].x - qs[i].x);
  119.     }
  120.     cout << ans << '\n';
  121. }
  122.  
  123. signed main() {
  124.     ios::sync_with_stdio(false);
  125.     cin.tie(nullptr);
  126.  
  127.     int tt = 1;
  128.     //    cin >> tt;
  129.     while (tt--)
  130.         solve();
  131.  
  132.     return 0;
  133. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement