#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
struct seg_tree{
struct node{
int val = 0;
int l, r;
};
vector<node> tree;
int n;
int dbInd = 0;
void build(int v){
if(v >= n){
tree[v].l = tree[v].r = dbInd++;
}else{
build(v*2); build(v*2+1);
tree[v].l = tree[v*2].l;
tree[v].r = tree[v*2+1].r;
}
}
seg_tree(int dd){
n = dd;
tree.resize(2 * n + 1);
build(1);
}
void change(int v, int l, int r, int x){
if(l <= tree[v].l && tree[v].r <= r){
tree[v].val += x;
}else if(tree[v].r < l || r < tree[v].l){
}else{
change(v*2, l, r, x);
change(v*2+1, l, r, x);
tree[v].val = tree[v*2].val + tree[v*2+1].val;
}
}
int find(int v, int l, int r){
if(l <= tree[v].l && tree[v].r <= r){
return tree[v].val;
}else if(tree[v].r < l || r < tree[v].l){
return 0;
}else{
return find(v*2, l, r) + find(v*2+1, l, r);
}
}
};
long long f1(vector<int> &mas, int X){ // N log N
// mas isrikiuotas
long long ret = 0;
for(auto x : mas){
// cout << x << " prd " << upper_bound(mas.begin(), mas.end(), x + X) - lower_bound(mas.begin(), mas.end(), x - X) << endl;
ret += upper_bound(mas.begin(), mas.end(), x + X) - lower_bound(mas.begin(), mas.end(), x - X)-1;
}
return ret;
}
long long f2(vector<pair<int, int> > &ms, int d){
const int dd = 150001;
vector<vector<int> > pts(dd);
vector<pair<int, int> > mas;
for(int i = 0; i < (int)ms.size(); i++){
int X = ms[i].first + ms[i].second;
int Y = ms[i].first - ms[i].second;
pts[X].push_back(Y);
}
seg_tree medis(dd * 2 + 10);
sort(mas.begin(), mas.end());
long long ans = 0;
for(int i = 0; i < dd; i++){
if(i-d-1 >= 0){
for(auto x : pts[i-d-1]){
//cout << "X = " << x << endl;
medis.change(1, x +dd, x + dd, -1);
}
}
sort(pts[i].begin(), pts[i].end());
for(int j = 0; j < (int)pts[i].size(); j++){
ans += upper_bound(pts[i].begin() + j, pts[i].end(), pts[i][j] + d) - pts[i].begin() - j -1;
//cout << "prd " << (int)( upper_bound(pts[i].begin() + j + 1, pts[i].end(), pts[i][j] + d) - pts[i].begin() - j - 2) << endl;
ans += medis.find(1, pts[i][j]-d + dd, pts[i][j]+d + dd);
}
for(auto x : pts[i]){
medis.change(1, x+dd, x + dd, 1);
}
}
return ans;
}
void dar(vector<vector<int> > &mas, vector<vector<int> > &pref){ // precalc pref
int n = mas.size();
int m = mas[0].size();
for(int i = 0; i < n; i++){
int sm = 0;
for(int j = 0; j < m; j++){
sm += mas[i][j];
pref[i][j] = (i == 0 ? 0 : pref[i-1][j]) + sm;
}
}
}
int ad = 0, ak = 0, vd = 0, vk = 0;
int fd(vector<vector<int> > &pref, int x1, int y1, int x2, int y2){
ad = 0, ak = 0, vd = 0, vk = 0;
ad = pref[x2][y2];
if(x1 != 0) ak = pref[x1-1][y2];
if(y1 != 0) vd = pref[x2][y1-1];
if(y1 != 0 && x1 != 0) vk = pref[x1-1][y1-1];
return ad - ak - vd + vk;
}
int fdd(vector<vector<int> > &mas, int X, int Y, int dst){
int ret = 0;
//cout << "darau\n";
//for(auto x : mas)
for(int i = 0; i < (int)mas.size(); i++){
for(int j = 0; j < (int)mas.size(); j++){
if(max(abs(i-X), abs(j - Y)) <= dst) ret += mas[i][j];
}
}
//for(auto x : mas) if(abs(x.second.first - X) + abs(x.second.second - Y) <= dst) ret ++;
return ret;
}
int fddd(vector<pair<int, pair<int, int> > > mas, int X, int y, int z, int d){
int ret = 0;
for(auto x : mas){
if(x.first != X) continue;
if(abs(x.first - X) + abs(x.second.first - y) + abs(x.second.second - z) <= d){
ret++;
}
}
return ret;
}
const int dd = 12;
int sm[dd+1][dd+1][dd+1][3*dd+1] = {};
long long f3(vector<pair<int, pair<int, int> > > &mas, int d){
//cout << "STOP!" << endl;
//long long ps = 0;
//for(auto x : mas) for(auto y : mas) if(abs(x.first - y.first) + abs(x.second.first - y.second.first) + abs(x.second.second - y.second.second) <= d) ps++;
//cout << (ps-(int)mas.size())/2 << " ";
vector<vector<vector<int> > > trans, pref;
trans.resize(dd+1);
for(auto &x : trans){
x.resize(dd*3 + 1);
for(auto &y : x) y.resize(dd*3 + 1);
for(auto &z : x) for(auto &g : z) g = 0;
}
pref = trans;
vector<vector<pair<int, int> > > pts;
pts.resize(dd + 1);
for(auto x : mas){
int X = x.second.first;
int Y = x.second.second;
trans[x.first][X+Y][X-Y+dd]++;
pts[x.first].push_back({X+Y, X-Y + dd});
//cout << "trans " << X+Y << "; " << X-Y + dd << ", aukstuje " << x.first << endl;
}
for(int i = 0; i <= dd; i++){
dar(trans[i], pref[i]);
}
int X, Y, x1, x2, y1, y2;
for(int i = 0; i <= dd; i++){
for(int j = 0; j <= dd; j++){
for(int h = 0; h <= dd; h++){
for(int l = 0; l <= 3*dd; l++){ // jei turiu tik pozicija i-ajame aukste su koordinatem [j; h] ir d = l, kiek pasieksiu?
X = j + h;
Y = j - h + dd;
x1 = min(max(X - l, 0), dd*3);
y1 = min(max(Y - l, 0), dd*3);
x2 = max(min(X + l, dd*3), 0);
y2 = max(min(Y + l, dd*3), 0);
//cout << X << "; " << Y << ": " << x1 << "; " << y1 << "; " << x2 << "; " << y2 << endl;
sm[i][j][h][l] = fd(pref[i], x1, y1, x2, y2);
//if(fd(pref[i], x1, y1, x2, y2) != fddd(mas, i, j, h, l) ) cout << "sakau " << fd(pref[i], x1, y1, x2, y2) << " vs " << fddd(mas, i, j, h, l) << ", x=" << i << ", y=" << j << ", z=" << h <<", l = " << l << endl;
}
}
}
}
long long ans = 0;
for(auto x : mas){
int H, X, Y, L;
for(int i = -d ; i <= d; i++){
H = x.first + i;
if(H < 0 || H > dd) continue;
X = x.second.first;
Y = x.second.second;
L = d - abs(i);
//cout << "Sm[" << H << "][" << X << "][" << Y << "][" << L << "] = " << sm[H][X][Y][L] << endl;
ans += sm[H][X][Y][L];
}
ans--;
}
return ans/2ll;
}
/*
3 2 26 10
8 2 2
9 3 8
*/
void gen(){
int n = rand() % 4; int d = rand()%30 + 2;
cout << "3 " << n << " " << d << " 10" << "\n";
for(int i = 0; i < n; i++){
cout << rand()%10 << " " << rand()%10 << " " << rand() % 10 << endl;
}
cout << endl;
}
int main(){
srand(time(0));
gen();
int B, n, d, m; cin >> B >> n >> d >> m;
if(B == 1){
vector<int> ms(n); for(auto &x : ms) cin >> x;
sort(ms.begin(), ms.end());
cout << f1(ms, d) /2ll;
return 0;
}else if(B == 2){
vector<pair<int, int> > ms(n);
for(auto &x : ms) cin >> x.first >> x.second;
cout << f2(ms, d);
}else{
vector<pair<int, pair<int, int> > > ms(n);
for(auto &x : ms) cin >> x.first >> x.second.first >> x.second.second;
cout << f3(ms, d);
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
36 ms |
1072 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
59 ms |
1476 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
59 ms |
1484 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
10828 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
94 ms |
12860 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
134 ms |
13148 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
199 ms |
14760 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
716 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
67 ms |
3848 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
64 ms |
3896 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
74 ms |
3888 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
