Submission #1046046

#	Time	Username	Problem	Language	Result	Execution time	Memory
1046046		mickey080929	Cell Automaton (JOI23_cell)	C++17	17 / 100	8079 ms	18392 KiB

cell

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;

struct LazySegmentTree{
    vector<ll> tree;
    vector<ll> lazy;
    void init(ll n) {
        ll sz = 1 << __lg(n-1) + 2;
        tree.assign(sz, 0);
        lazy.assign(sz, 0);
    }
    void propagate(ll node, ll s, ll e) {
        tree[node] += lazy[node];
        if (s != e) {
            lazy[node*2] += lazy[node];
            lazy[node*2+1] += lazy[node];
        }
        lazy[node] = 0;
    }
    void update(ll node, ll s, ll e, ll l, ll r, ll val) {
        propagate(node, s, e);
        if (l > e || s > r) return;
        if (l <= s && e <= r) {
            lazy[node] = val;
            propagate(node, s, e);
            return;
        }
        ll mid = s + e >> 1;
        update(node*2, s, mid, l, r, val);
        update(node*2+1, mid+1, e, l, r, val);
        tree[node] = min(tree[node*2], tree[node*2+1]);
    }
    ll query(ll node, ll s, ll e, ll l, ll r) {
        propagate(node, s, e);
        if (l > e || s > r) return 1;
        if (l <= s && e <= r) return tree[node];
        ll mid = s + e >> 1;
        return min(query(node*2, s, mid, l, r), query(node*2+1, mid+1, e, l, r));
    }
    ll FindLeft(ll node, ll s, ll e, ll l, ll r) {
        propagate(node, s, e);
        if (l > e || s > r || tree[node] == 1) return -1;
        if (s == e) {
            if (tree[node] == 0) return s;
            return -1;
        }
        ll mid = s + e >> 1;
        ll t = FindLeft(node*2, s, mid, l, r);
        if (t != -1) return t;
        return FindLeft(node*2+1, mid+1, e, l, r);
    }
    ll FindRight(ll node, ll s, ll e, ll l, ll r) {
        propagate(node, s, e);
        if (l > e || s > r || tree[node] == 1) return -1;
        if (s == e) {
            if (tree[node] == 0) return s;
            return -1;
        }
        ll mid = s + e >> 1;
        ll t = FindRight(node*2+1, mid+1, e, l, r);
        if (t != -1) return t;
        return FindRight(node*2, s, mid, l, r);
    }
};

LazySegmentTree seg;

ll solve(vector<pll> a, ll T) {
    ll N = a.size();
    vector<array<ll,3>> upd;
    vector<ll> t;
    for (ll i=0; i<N; i++) {
        upd.push_back({a[i].first - T, a[i].second - T, 1});
        upd.push_back({a[i].first + T + 1, a[i].second - T, -1});
        t.push_back(a[i].second - T);
        t.push_back(a[i].second + T);
    }
    sort(t.begin(), t.end());
    t.erase(unique(t.begin(), t.end()), t.end());
    sort(upd.begin(), upd.end());
    ll M = t.size();
    seg.init(M);
    ll ans = 0;
    vector<ll> cnt(2, 0);
    for (ll i=0; i<upd.size(); i++) {
        if (i + 1 == upd.size()) break;
        if (upd[i][2] == 1) {
            ll li = lower_bound(t.begin(), t.end(), upd[i][1]) - t.begin() + 1;
            ll ri = lower_bound(t.begin(), t.end(), upd[i][1] + 2*T) - t.begin() + 1;
            ll retl = seg.query(1, 1, M, li-1, li-1);
            ll retr = seg.query(1, 1, M, ri+1, ri+1);
            bool flag = false;
            if (li - 1 >= 1 && retl == 1) {
                ll s = seg.FindRight(1, 1, M, 1, li-1);
                ll e = seg.FindLeft(1, 1, M, li-1, M);
                if (s == -1) s = 0;
                if (e == -1) e = M + 1;
                s ++; e --;
                ll sv = t[s - 1], ev = t[e - 1];
                if (e >= ri) flag = true;
                else {
                    cnt[0] -= (ev - sv + 1) / 2;
                    cnt[1] -= (ev - sv + 1) / 2;
                    if (abs(ev) % 2 == abs(sv) % 2) {
                        cnt[abs(ev) % 2] --;
                    }
                }
            }
            if (ri + 1 <= M && !flag && retr == 1) {
                ll s = seg.FindRight(1, 1, M, 1, ri+1);
                ll e = seg.FindLeft(1, 1, M, ri+1, M);
                if (s == -1) s = 0;
                if (e == -1) e = M + 1;
                s ++; e --;
                ll sv = t[s - 1], ev = t[e - 1];
                cnt[0] -= (ev - sv + 1) / 2;
                cnt[1] -= (ev - sv + 1) / 2;
                if (abs(ev) % 2 == abs(sv) % 2) {
                    cnt[abs(ev) % 2] --;
                }
            }
            seg.update(1, 1, M, li, ri, 1);
            if (!flag) {
                ll s = seg.FindRight(1, 1, M, 1, li);
                ll e = seg.FindLeft(1, 1, M, li, M);
                if (s == -1) s = 0;
                if (e == -1) e = M + 1;
                s ++; e --;
                ll sv = t[s - 1], ev = t[e - 1];
                cnt[0] += (ev - sv + 1) / 2;
                cnt[1] += (ev - sv + 1) / 2;
                if (abs(ev) % 2 == abs(sv) % 2) {
                    cnt[abs(ev) % 2] ++;
                }
            }
        }
        else {
            ll li = lower_bound(t.begin(), t.end(), upd[i][1]) - t.begin() + 1;
            ll ri = lower_bound(t.begin(), t.end(), upd[i][1] + 2*T) - t.begin() + 1;
            {
                ll s = seg.FindRight(1, 1, M, 1, li);
                ll e = seg.FindLeft(1, 1, M, li, M);
                if (s == -1) s = 0;
                if (e == -1) e = M + 1;
                s ++; e --;
                ll sv = t[s - 1], ev = t[e - 1];
                cnt[0] -= (ev - sv + 1) / 2;
                cnt[1] -= (ev - sv + 1) / 2;
                if (abs(ev) % 2 == abs(sv) % 2) {
                    cnt[abs(ev) % 2] --;
                }
            }
            seg.update(1, 1, M, li, ri, -1);
            ll retl = seg.query(1, 1, M, li-1, li-1);
            ll retr = seg.query(1, 1, M, ri+1, ri+1);
            bool flag = false;
            if (li-1 >= 1 && retl) {
                ll s = seg.FindRight(1, 1, M, 1, li-1);
                ll e = seg.FindLeft(1, 1, M, li-1, M);
                if (s == -1) s = 0;
                if (e == -1) e = M + 1;
                s ++; e --;
                ll sv = t[s - 1], ev = t[e - 1];
                cnt[0] += (ev - sv + 1) / 2;
                cnt[1] += (ev - sv + 1) / 2;
                if (abs(ev) % 2 == abs(sv) % 2) {
                    cnt[abs(ev) % 2] ++;
                }
                if (e >= ri) flag = true;
            }
            if (ri + 1 <= M && retr && !flag) {
                ll s = seg.FindRight(1, 1, M, 1, ri+1);
                ll e = seg.FindLeft(1, 1, M, ri+1, M);
                if (s == -1) s = 0;
                if (e == -1) e = M + 1;
                s ++; e --;
                ll sv = t[s - 1], ev = t[e - 1];
                cnt[0] += (ev - sv + 1) / 2;
                cnt[1] += (ev - sv + 1) / 2;
                if (abs(ev) % 2 == abs(sv) % 2) {
                    cnt[abs(ev) % 2] ++;
                }
            }
        }
        if (upd[i+1][0] == upd[i][0]) continue;
        //printf("%d %d\n", upd[i][0], upd[i+1][0]);
        vector<ll> cnt2(2, 0);
        ll l = upd[i][0], r = upd[i+1][0] - 1;
        cnt2[0] = cnt2[1] = (r - l + 1) / 2;
        if (abs(r) % 2 == abs(l) % 2) {
            cnt2[abs(l) % 2] ++;
        }
        ans += cnt[0] * cnt2[0] + cnt[1] * cnt2[1];
        //printf("\n");
    }
    return ans;
}

int main() {
    ios_base :: sync_with_stdio(false); cin.tie(NULL);
    ll N, Q;
    cin >> N >> Q;
    vector<pll> a;
    for (ll i=0; i<N; i++) {
        ll x, y;
        cin >> x >> y;
        a.push_back({x+y, x-y});
        //printf("%d %d\n", x+y, x-y);
    }
    while (Q --) {
        ll t;
        cin >> t;
        if (t == 0) {
            cout << N << '\n';
        }
        else {
            cout << solve(a, t) - solve(a, t-1) << '\n';
        }
    }
}

Compilation message (stderr)

cell.cpp: In member function 'void LazySegmentTree::init(ll)':
cell.cpp:12:32: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   12 |         ll sz = 1 << __lg(n-1) + 2;
      |                      ~~~~~~~~~~^~~
cell.cpp: In member function 'void LazySegmentTree::update(ll, ll, ll, ll, ll, ll)':
cell.cpp:32:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   32 |         ll mid = s + e >> 1;
      |                  ~~^~~
cell.cpp: In member function 'll LazySegmentTree::query(ll, ll, ll, ll, ll)':
cell.cpp:41:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   41 |         ll mid = s + e >> 1;
      |                  ~~^~~
cell.cpp: In member function 'll LazySegmentTree::FindLeft(ll, ll, ll, ll, ll)':
cell.cpp:51:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   51 |         ll mid = s + e >> 1;
      |                  ~~^~~
cell.cpp: In member function 'll LazySegmentTree::FindRight(ll, ll, ll, ll, ll)':
cell.cpp:63:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   63 |         ll mid = s + e >> 1;
      |                  ~~^~~
cell.cpp: In function 'll solve(std::vector<std::pair<long long int, long long int> >, ll)':
cell.cpp:89:19: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::array<long long int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |     for (ll i=0; i<upd.size(); i++) {
      |                  ~^~~~~~~~~~~
cell.cpp:90:19: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::array<long long int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |         if (i + 1 == upd.size()) break;
      |             ~~~~~~^~~~~~~~~~~~~

• Subtask 1: 0 / 4
• Subtask 2: 0 / 12
• Subtask 3: 0 / 8
• Subtask 4: 0 / 8
• Subtask 5: 17 / 17
• Subtask 6: 0 / 25
• Subtask 7: 0 / 26