This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(v) v.begin(), v.end()
#define pii pair<int, int>
class Seg{
vector<ll> st;
int len = 1;
public:
Seg(int n){
while(len < n) len *= 2;
st.resize(len * 2, 0);
}
void add(int idx, ll val, int i, int s, int e){
if(idx < s || idx >= e) return;
if(idx == s && s + 1 == e){
st[i] += val;
return;
}
add(idx, val, i * 2, s, (s + e) / 2);
add(idx, val, i * 2 + 1, (s + e) / 2, e);
st[i] = st[i * 2] + st[i * 2 + 1];
}
void add(int idx, ll val){
add(idx, val, 1, 0, len);
}
ll qry(int l, int r, int i, int s, int e){
if(l >= e || s >= r) return 0;
if(l <= s && e <= r) return st[i];
return qry(l, r, i * 2, s, (s + e) / 2) + qry(l, r, i * 2 + 1, (s + e) / 2, e);
}
ll qry(int l, int r){
return qry(l, r, 1, 0, len);
}
};
int d, m;
vector<int> coords;
int cmpr(int x){
return lower_bound(all(coords), x) - coords.begin();
}
tuple<int, int, int> cget(int x, int y){
if((x + y) % 2 == 1) return {1, (x + y + 1) / 2 + d + m, (x - y + 1) / 2 + d + m};
else return {0, (x + y) / 2 + d + m, (x - y) / 2 + d + m};
}
int main()
{
int b, n; cin >> b >> n >> d >> m;
if(b == 1){
vector<pair<int, int>> q;
vector<int> ad;
for (int i = 0; i < n; i++) {
int a; cin >> a;
ad.push_back(a);
q.push_back({a - d, a + d});
coords.push_back(a);
coords.push_back(a - d);
coords.push_back(a + d);
}
sort(all(coords));
Seg st(coords.size() + 1);
for (auto &i : ad)
st.add(cmpr(i), 1);
ll res = 0;
for (auto &[f, t] : q)
res += st.qry(cmpr(f), cmpr(t) + 1) - 1;
cout << res / 2 << endl;
}
if(b == 2){
vector<array<int, 5>> evo; // t (0s, 1, 2e), y, x, xx, i
vector<array<int, 5>> eve; // t (0s, 1, 2e), y, x, xx, i
for (int i = 0; i < n; i++)
{
int sx, sy; cin >> sx >> sy;
int p, x, y; tie(p, x, y) = cget(sx, sy);
if(p == 0) eve.push_back({x, 1, y, -1, -1});
else evo.push_back({x, 1, y, -1, -1});
for (int j = 0; j < 2; j++)
{
pii up, ri, dw, lf;
up = {sx, sy + d - j};
ri = {sx + d - j, sy};
dw = {sx, sy - d + j};
lf = {sx - d + j, sy};
tie(p, up.first, up.second) = cget(up.first, up.second);
tie(p, ri.first, ri.second) = cget(ri.first, ri.second);
tie(p, dw.first, dw.second) = cget(dw.first, dw.second);
tie(p, lf.first, lf.second) = cget(lf.first, lf.second);
if(p == 0){
eve.push_back({up.first, 2, ri.second, up.second, i});
eve.push_back({dw.first, 0, dw.second, lf.second, i});
}
else{
evo.push_back({up.first, 2, ri.second, up.second, i});
evo.push_back({dw.first, 0, dw.second, lf.second, i});
}
}
}
ll res = 0;
for (auto &ev : vector<vector<array<int, 5>>>({eve, evo})) {
sort(all(ev));
Seg st(3 * m + 2 * d + 5);
for (auto &e : ev) {
auto& [y, t, x, xx, i] = e;
if(t == 1){
st.add(x, 1);
}
if(t == 0){
res -= st.qry(xx, x + 1);
}
if(t == 2){
res += st.qry(xx, x + 1);
}
}
}
cout << (res - (ll)n) / 2LL << endl;
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |