Submission #1225199

#TimeUsernameProblemLanguageResultExecution timeMemory
1225199LucasLeCell Automaton (JOI23_cell)C++20
17 / 100
8093 ms15948 KiB
#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, li); ll retr = seg.query(1, 1, M, ri, ri); bool flag = false; if (retl == 1) { ll e = seg.FindLeft(1, 1, M, li, M); if (e == -1) e = M + 1; e --; ll sv = t[li - 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 (!flag && retr == 1) { ll s = seg.FindRight(1, 1, M, 1, ri); if (s == -1) s = 0; s ++; ll sv = t[s - 1], ev = t[ri - 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 sv = t[li - 1], ev = t[ri - 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'; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...