Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /// @author s_k_a_r_a
- #ifndef Local
- // #pragma GCC optimize("Ofast")
- #include <bits/stdc++.h>
- #include <ext/pb_ds/assoc_container.hpp>
- #define debug(...)
- #endif
- using namespace std;
- #define int long long
- typedef long long ll;
- typedef long double ld;
- using str = string;
- #define vec vector
- #define all(x) (x).begin(), (x).end()
- #define rall(x) (x).rbegin(), (x).rend()
- #define sz(x) (int)(x).size()
- #define pb push_back
- struct st {
- static const int maxn = 16ll * 1024 * 1024 * 1024 * 1024 * 1024;
- static const int inf = (int)1e15;
- struct node {
- int mn, cnt, l, r, rb;
- node(int cnt) : mn(0), cnt(cnt), l(-1), r(-1), rb(0) {}
- node(int mn, int cnt) : mn(mn), cnt(cnt), l(-1), r(-1), rb(0) {}
- };
- vec<node> t;
- st() {
- t.pb({maxn});
- }
- int mk(int c) {
- t.pb({c});
- return sz(t) - 1;
- }
- int mk(int mn, int c) {
- t.pb({mn, c});
- return sz(t) - 1;
- }
- int get() {
- return maxn - (t[0].mn == 0 ? t[0].cnt : 0);
- }
- int lq, rq, dq;
- void upd(int i = 0, int l = 0, int r = maxn) {
- if (lq <= l && r <= rq) {
- t[i].rb += dq, t[i].mn += dq;
- return;
- }
- int m = (l + r) / 2;
- if (t[i].l == -1)
- t[i].l = mk(t[i].mn - t[i].rb, m - l);
- if (t[i].r == -1)
- t[i].r = mk(t[i].mn - t[i].rb, r - m);
- if (lq < m)
- upd(t[i].l, l, m);
- if (m < rq)
- upd(t[i].r, m, r);
- int mn = t[t[i].l].mn, cnt = t[t[i].l].cnt;
- if (mn > t[t[i].r].mn)
- mn = t[t[i].r].mn, cnt = t[t[i].r].cnt;
- else if (mn == t[t[i].r].mn)
- cnt += t[t[i].r].cnt;
- t[i].mn = mn + t[i].rb, t[i].cnt = cnt;
- }
- void query(int l, int r, int d) {
- lq = l, rq = r + 1, dq = d;
- upd();
- }
- };
- struct q {
- int x, ly, ry, md;
- bool operator<(q c) {
- return x < c.x;
- }
- };
- void solve() { // все запросы до 10^16, а начальная точка 10^15
- int k, n;
- cin >> k >> n;
- int x = (int)1e15, y = (int)1e15;
- vec<q> qs;
- char c;
- for (int i = 0, t; i < n; ++i) {
- cin >> c >> t;
- if (c == 'N')
- qs.pb({x, y, y + k - 1 + t, 0}), qs.pb({x + k, y, y + k - 1 + t, 1}), y += t;
- else if (c == 'E')
- qs.pb({x, y, y + k - 1, 0}), qs.pb({x + k + t, y, y + k - 1, 1}), x += t;
- else if (c == 'S')
- qs.pb({x, y - t, y + k - 1, 0}), qs.pb({x + k, y - t, y + k - 1, 1}), y -= t;
- else
- qs.pb({x - t, y, y + k - 1, 0}), qs.pb({x + k, y, y + k - 1, 1}), x -= t;
- }
- sort(all(qs));
- int ans = 0;
- st t;
- for (int i = 0; i < 2 * n; ++i) {
- if (qs[i].md == 0)
- t.query(qs[i].ly, qs[i].ry, 1);
- if (qs[i].md == 1)
- t.query(qs[i].ly, qs[i].ry, -1);
- if (i != 2 * n - 1)
- ans += t.get() * (qs[i + 1].x - qs[i].x);
- }
- cout << ans << '\n';
- }
- signed main() {
- ios::sync_with_stdio(false);
- cin.tie(nullptr);
- int tt = 1;
- // cin >> tt;
- while (tt--)
- solve();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement