Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //#pragma GCC optimize("Ofast")
- //#pragma GCC optimize ("unroll-loops")
- //#pragma GCC optimize ("fast-math")
- //#pragma GCC target("avx2")
- #define _CRT_SECURE_NO_WARNINGS
- #include <iostream>
- #include <algorithm>
- #include <string>
- #include <cmath>
- #include <vector>
- #include <map>
- #include <set>
- #include <list>
- #include <ctime>
- #include <stack>
- #include <queue>
- #include <iomanip>
- #include <cstdlib>
- #include <unordered_map>
- #include <unordered_set>
- #include <cstddef>
- #include <deque>
- #include <cstdio>
- #include <fstream>
- #include <random>
- #include <climits>
- #include <random>
- #include <cassert>
- using namespace std;
- #define forn(i, j, k) for(int i = (int)(j); i < (int)(k); i++)
- #define forn1(i, j, k) for(int i = (int)(j); i <= (int)(k); i++)
- #define pb push_back
- #define f first
- #define s second
- #define sz(a) ((int)((a).size()))
- #define endl '\n'
- const int INF = 1e9+1;
- const int MOD = 1e9 + 7;
- const int MOD1 = 998244353;
- const double EPS = 1e-4;
- typedef long long ll;
- typedef unsigned long long ull;
- typedef long double ld;
- //std::mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
- #define dbg(x) cerr << #x << " = " << x << '\n';
- struct Node {
- ll val = 0;
- int cnt = 0;
- Node* left = nullptr;
- Node* right = nullptr;
- };
- Node* root = new Node();
- ll sum_children(Node* ver) {
- ll res = 0;
- if (ver->left != nullptr) {
- res += ver->left->val;
- }
- if (ver->right != nullptr) {
- res += ver->right->val;
- }
- return res;
- }
- void update(Node* ver, ll l, ll r, ll i, ll j, int delta) {
- if (l == i && r == j) {
- ver->cnt += delta;
- if (ver->cnt >= 1) {
- ver->val = r - l + 1;
- } else {
- ver->val = sum_children(ver);
- }
- return;
- }
- ll d = (l + r) / 2;
- if (ver->left == nullptr) {
- ver->left = new Node();
- }
- if (ver->right == nullptr) {
- ver->right = new Node();
- }
- if (j <= d) {
- update(ver->left, l, d, i, j, delta);
- } else if (d + 1 <= i) {
- update(ver->right, d + 1, r, i, j, delta);
- } else {
- update(ver->left, l, d, i, d, delta);
- update(ver->right, d + 1, r, d + 1, j, delta);
- }
- if (ver->cnt >= 1) {
- ver->val = r - l + 1;
- } else {
- ver->val = sum_children(ver);
- }
- }
- struct Pr {
- ll y1 = 0;
- ll y2 = 0;
- };
- void solve() {
- int k, n;
- cin >> k >> n;
- ll MIN_COORD = 0, MAX_COORD = k;
- ll x = 0, y = 0, ans = 0;
- set<ll> X = {0, k};
- std::unordered_map<ll, vector<Pr>> beg, en;
- forn(i, 0, n) {
- char t;
- ll del;
- cin >> t >> del;
- if (t == 'N') {
- beg[x].push_back({y, y + del + k});
- en[x + k].push_back({y, y + del + k});
- y += del;
- } else if (t == 'S') {
- beg[x].push_back({y - del, y + k});
- en[x + k].push_back({y - del, y + k});
- y -= del;
- } else if (t == 'E') {
- beg[x].push_back({y, y + k});
- en[x + del + k].push_back({y, y + k});
- x += del;
- } else if (t == 'W') {
- beg[x - del].push_back({y, y + k});
- en[x + k].push_back({y, y + k});
- x -= del;
- }
- X.insert(x);
- X.insert(x + k);
- MIN_COORD = min(MIN_COORD, y);
- MAX_COORD = max(MAX_COORD, y + k);
- }
- vector<ll> pos;
- for (auto i : X ) {
- pos.push_back(i);
- }
- forn(i, 0, pos.size() - 1) {
- for (auto obj : en[pos[i]]) {
- update(root, 0, MAX_COORD - MIN_COORD, obj.y1 - MIN_COORD, obj.y2 - 1 - MIN_COORD, -1);
- }
- for (auto obj : beg[pos[i]]) {
- update(root, 0, MAX_COORD - MIN_COORD, obj.y1 - MIN_COORD, obj.y2 - 1 - MIN_COORD, 1);
- }
- ans += (pos[i + 1] - pos[i]) * root->val;
- }
- cout << ans << endl;
- }
- int32_t main() {
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- cout.tie(nullptr);
- int t = 1;
- #ifdef LOCAL
- freopen("input.txt", "r", stdin);
- //freopen("output.txt", "w", stdout);
- cin >> t;
- #else
- t = 1;
- #endif
- while(t--){
- solve();
- #ifdef LOCAL
- cout << "__________________________" << endl;
- #endif
- }
- #ifdef LOCAL
- cerr << endl << "finished in " << clock() * 1.0 / CLOCKS_PER_SEC << " sec" << endl;
- #endif
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement