#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
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;
| ~~~~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
67 ms |
18392 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
67 ms |
18392 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
100 ms |
856 KB |
Output is correct |
| 2 |
Correct |
103 ms |
860 KB |
Output is correct |
| 3 |
Correct |
134 ms |
888 KB |
Output is correct |
| 4 |
Correct |
101 ms |
888 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
100 ms |
856 KB |
Output is correct |
| 2 |
Correct |
103 ms |
860 KB |
Output is correct |
| 3 |
Correct |
134 ms |
888 KB |
Output is correct |
| 4 |
Correct |
101 ms |
888 KB |
Output is correct |
| 5 |
Execution timed out |
8079 ms |
952 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
