Advertisement
playerr17

Untitled

Jul 13th, 2023
272
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.39 KB | None | 0 0
  1. //#pragma GCC optimize("Ofast")
  2. //#pragma GCC optimize ("unroll-loops")
  3. //#pragma GCC optimize ("fast-math")
  4. //#pragma GCC target("avx2")
  5. #define _CRT_SECURE_NO_WARNINGS
  6. #include <iostream>
  7. #include <algorithm>
  8. #include <string>
  9. #include <cmath>
  10. #include <vector>
  11. #include <map>
  12. #include <set>
  13. #include <list>
  14. #include <ctime>
  15. #include <stack>
  16. #include <queue>
  17. #include <iomanip>
  18. #include <cstdlib>
  19. #include <unordered_map>
  20. #include <unordered_set>
  21. #include <cstddef>
  22. #include <deque>
  23. #include <cstdio>
  24. #include <fstream>
  25. #include <random>
  26. #include <climits>
  27. #include <random>
  28. #include <cassert>
  29.  
  30. using namespace std;
  31. #define forn(i, j, k) for(int i = (int)(j); i < (int)(k); i++)
  32. #define forn1(i, j, k) for(int i = (int)(j); i <= (int)(k); i++)
  33. #define pb push_back
  34. #define f first
  35. #define s second
  36. #define sz(a) ((int)((a).size()))
  37. #define endl '\n'
  38. const int INF = 1e9+1;
  39. const int MOD = 1e9 + 7;
  40. const int MOD1 = 998244353;
  41. const double EPS = 1e-4;
  42. typedef long long ll;
  43. typedef unsigned long long ull;
  44. typedef long double ld;
  45. //std::mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
  46. #define dbg(x) cerr << #x << " = " << x << '\n';
  47.  
  48. struct Node {
  49.     ll val = 0;
  50.     int cnt = 0;
  51.     Node* left = nullptr;
  52.     Node* right = nullptr;
  53. };
  54.  
  55. Node* root = new Node();
  56.  
  57. ll sum_children(Node* ver) {
  58.     ll res = 0;
  59.     if (ver->left != nullptr) {
  60.         res += ver->left->val;
  61.     }
  62.     if (ver->right != nullptr) {
  63.         res += ver->right->val;
  64.     }
  65.     return res;
  66. }
  67.  
  68. void update(Node* ver, ll l, ll r, ll i, ll j, int delta) {
  69.     if (l == i && r == j) {
  70.         ver->cnt += delta;
  71.         if (ver->cnt >= 1) {
  72.             ver->val = r - l + 1;
  73.         } else {
  74.             ver->val = sum_children(ver);
  75.         }
  76.         return;
  77.     }
  78.     ll d = (l + r) / 2;
  79.     if (ver->left == nullptr) {
  80.         ver->left = new Node();
  81.     }
  82.     if (ver->right == nullptr) {
  83.         ver->right = new Node();
  84.     }
  85.     if (j <= d) {
  86.         update(ver->left, l, d, i, j, delta);
  87.     } else if (d + 1 <= i) {
  88.         update(ver->right, d + 1, r, i, j, delta);
  89.     } else {
  90.         update(ver->left, l, d, i, d, delta);
  91.         update(ver->right, d + 1, r, d + 1, j, delta);
  92.     }
  93.     if (ver->cnt >= 1) {
  94.         ver->val = r - l + 1;
  95.     } else {
  96.         ver->val = sum_children(ver);
  97.     }
  98. }
  99.  
  100. struct Pr {
  101.     ll y1 = 0;
  102.     ll y2 = 0;
  103. };
  104.  
  105. void solve() {
  106.     int k, n;
  107.     cin >> k >> n;
  108.     ll MIN_COORD = 0, MAX_COORD = k;
  109.     ll x = 0, y = 0, ans = 0;
  110.     set<ll> X = {0, k};
  111.     std::unordered_map<ll, vector<Pr>> beg, en;
  112.     forn(i, 0, n) {
  113.         char t;
  114.         ll del;
  115.         cin >> t >> del;
  116.         if (t == 'N') {
  117.             beg[x].push_back({y, y + del + k});
  118.             en[x + k].push_back({y, y + del + k});
  119.             y += del;
  120.         } else if (t == 'S') {
  121.             beg[x].push_back({y - del, y + k});
  122.             en[x + k].push_back({y - del, y + k});
  123.             y -= del;
  124.         } else if (t == 'E') {
  125.             beg[x].push_back({y, y + k});
  126.             en[x + del + k].push_back({y, y + k});
  127.             x += del;
  128.         } else if (t == 'W') {
  129.             beg[x - del].push_back({y, y + k});
  130.             en[x + k].push_back({y, y + k});
  131.             x -= del;
  132.         }
  133.         X.insert(x);
  134.         X.insert(x + k);
  135.         MIN_COORD = min(MIN_COORD, y);
  136.         MAX_COORD = max(MAX_COORD, y + k);
  137.     }
  138.     vector<ll> pos;
  139.     for (auto i : X ) {
  140.         pos.push_back(i);
  141.     }
  142.     forn(i, 0, pos.size() - 1) {
  143.         for (auto obj : en[pos[i]]) {
  144.             update(root, 0, MAX_COORD - MIN_COORD, obj.y1 - MIN_COORD, obj.y2 - 1 - MIN_COORD, -1);
  145.         }
  146.         for (auto obj : beg[pos[i]]) {
  147.             update(root, 0, MAX_COORD - MIN_COORD, obj.y1 - MIN_COORD, obj.y2 - 1 - MIN_COORD, 1);
  148.         }
  149.         ans += (pos[i + 1] - pos[i]) * root->val;
  150.     }
  151.     cout << ans << endl;
  152. }
  153.  
  154. int32_t main() {
  155.     ios_base::sync_with_stdio(false);
  156.     cin.tie(nullptr);
  157.     cout.tie(nullptr);
  158.     int t = 1;
  159. #ifdef LOCAL
  160.     freopen("input.txt", "r", stdin);
  161.     //freopen("output.txt", "w", stdout);
  162.     cin >> t;
  163. #else
  164.     t = 1;
  165. #endif
  166.     while(t--){
  167.         solve();
  168. #ifdef LOCAL
  169.         cout << "__________________________" << endl;
  170. #endif
  171.     }
  172. #ifdef LOCAL
  173.     cerr << endl << "finished in " << clock() * 1.0 / CLOCKS_PER_SEC << " sec" << endl;
  174. #endif
  175.     return 0;
  176. }
  177.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement