#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
int b, n, d, m;
void arbeit1()
{
vector <int> v;
for(int i = 0;i<n;i++)
{
int x;
cin >> x;
v.push_back(x);
}
long long answer = 0;
sort(v.begin(), v.end());
for(int i = 0;i<n-1;i++)
{
if(v[i+1]-v[i]>d) continue;
int l = i + 1, r = n - 1, mid;
while(l+1<r)
{
mid = (l+r)/2;
if(v[mid]-v[i]<=d) l = mid;
else r = mid - 1;
}
if(v[r]-v[i]<=d) answer += r - i;
else answer += l - i;
}
cout << answer << '\n';
}
struct Plane2D
{
int offset;
Plane2D(){}
Plane2D(int offset)
{
this->offset = offset;
}
struct Event
{
int type; //1 -> left square side, point, right square side
int pos, height;
int l, r;
Event(){}
Event(int type, int pos)
{
this->type = type;
this->pos = pos;
}
Event(int type, int pos, int height) : Event(type, pos)
{//offset?
this->height = height;
}
Event(int type, int pos, int l, int r) : Event(type, pos)
{//offset?
this->l = l;
this->r = r;
}
bool operator <(Event other)
{
if(pos!=other.pos) return pos<other.pos;
return type<other.type;
}
};
vector <Event> v;
struct FenwickTree
{
int n;
vector <int> tree;
FenwickTree(){}
FenwickTree(int sz)
{
tree.assign(sz+10, 0);
this->n = sz + 3;
}
void update(int ind, int val)
{
ind++;
while(ind<n)
{
tree[ind] += val;
ind += ind&(-ind);
}
}
int query(int ind)
{
int sum = 0;
ind++;
while(ind>0)
{
sum += tree[ind];
ind -= ind&(-ind);
}
return sum;
}
int query(int l, int r)
{
return query(r) - query(l-1);
}
};
void addPoint(int x, int y)
{
v.push_back(Event(2, x, y+offset));
}
void addSquare(pair <int, int> centre, int side)
{
v.push_back(Event(1, centre.first-side, centre.second-side+offset, centre.second+side+offset));
v.push_back(Event(3, centre.first+side, centre.second-side+offset, centre.second+side+offset));
}
long long process()
{
long long answer = 0;
int maxCoordinate = 0;
for(Event e: v)
{
if(e.type==2) maxCoordinate = max(maxCoordinate, e.height);
if(e.type==1) maxCoordinate = max(maxCoordinate, e.r);
}
sort(v.begin(), v.end());
FenwickTree T(maxCoordinate);
for(Event e: v)
{
//cout << e.pos << " ";
if(e.type==1)
{
//cout << e.type << " -- " << e.l << " " << e.r << '\n';
answer -= T.query(e.l, e.r);
}
else if(e.type==2)
{
//cout << e.type << " -- " << e.height << '\n';
T.update(e.height, +1);
}
else if(e.type==3)
{
//cout << e.type << " -- " << e.l << " " << e.r << '\n';
answer += T.query(e.l, e.r);
}
}
return answer;
}
};
void arbeit2()
{
int offset = 0;
vector <pair <int, int>> v;
for(int i = 0;i<n;i++)
{
int x, y;
cin >> x >> y;
v.push_back({x+y, x-y});
if(x-y-d<0) offset = max(offset, -(x-y-d));
}
Plane2D P(offset);
for(pair <int, int> p: v)
{
P.addPoint(p.first, p.second);
P.addSquare(p, d);
}
cout << (P.process()-n)/2 << '\n';
}
Plane2D P[80];
void arbeit3()
{
for(int i = 1;i<=m;i++) P[i] = Plane2D(200);
for(int i = 0;i<n;i++)
{
int x, y, z;
cin >> x >> y >> z;
for(int p = 1;p<=m;p++)
{
if(abs(p-z)>d) continue;
P[p].addSquare({x+y, x-y}, d-abs(p-z));
}
P[z].addPoint(x+y, x-y);
}
long long answer = 0;
for(int i = 1;i<=m;i++) answer += P[i].process();
cout << (answer-n)/2 << '\n';
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> b >> n >> d >> m;
if(b==1) arbeit1();
else if(b==2) arbeit2();
else if(b==3) arbeit3();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
1024 KB |
Output is correct |
| 2 |
Correct |
21 ms |
1024 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
1024 KB |
Output is correct |
| 2 |
Correct |
30 ms |
1024 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
31 ms |
1024 KB |
Output is correct |
| 2 |
Correct |
33 ms |
1056 KB |
Output is correct |
| 3 |
Correct |
31 ms |
1176 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
1024 KB |
Output is correct |
| 2 |
Correct |
2 ms |
1152 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
62 ms |
12004 KB |
Output is correct |
| 2 |
Correct |
60 ms |
12004 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
80 ms |
12012 KB |
Output is correct |
| 2 |
Correct |
69 ms |
11992 KB |
Output is correct |
| 3 |
Correct |
78 ms |
12004 KB |
Output is correct |
| 4 |
Correct |
72 ms |
12004 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
83 ms |
12004 KB |
Output is correct |
| 2 |
Correct |
83 ms |
12000 KB |
Output is correct |
| 3 |
Correct |
81 ms |
12132 KB |
Output is correct |
| 4 |
Correct |
78 ms |
12012 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
2816 KB |
Output is correct |
| 2 |
Correct |
18 ms |
3584 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
112 ms |
14580 KB |
Output is correct |
| 2 |
Correct |
288 ms |
42780 KB |
Output is correct |
| 3 |
Correct |
283 ms |
42664 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
588 ms |
78868 KB |
Output is correct |
| 2 |
Correct |
1637 ms |
232892 KB |
Output is correct |
| 3 |
Correct |
1670 ms |
238364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1391 ms |
196500 KB |
Output is correct |
| 2 |
Correct |
2094 ms |
296996 KB |
Output is correct |
| 3 |
Correct |
2073 ms |
297396 KB |
Output is correct |
