| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 788393 |
2023-07-20T07:54:41 Z |
canadavid1 |
Pairs (IOI07_pairs) |
C++14 |
|
97 ms |
5316 KB |
#include <bits/stdc++.h>
using namespace std;
#define all(x) begin(x),end(x)
using i64 = int64_t;
using u64 = uint64_t;
using u32 = uint32_t;
using i32 = int32_t;
// idea: k-d tree
/*
int median(vector<int>& p,int s, int e)
{
if (e-s <= 10)
{
vector<int> v; v.reserve(10);
for(int i = s; i < e; i++) v.push_back(p[i]);
sort(all(v));
return v[v.size()/2];
}
vector<int> m;
int diff = (e-s)/5;
m.push_back(median(p,s,s+diff));
m.push_back(median(p,s+diff,s+2*diff));
m.push_back(median(p,s+2*diff,e-2*diff));
m.push_back(median(p,e-2*diff,e-diff));
m.push_back(median(p,e-diff,e));
sort(all(m));
return m[2];
// slight bias to the right
// split into 5
} */
namespace d1 // confirmed works for all N
{
void d1()
{
i32 N,D,M;
cin >> N >> D >> M;
vector<i32> p(N);
for(auto && i : p) cin >> i;
sort(all(p));
i64 c=0;
for(u32 i = 0; i < p.size();i++)
{
// binary search for furthest after it
i32 thrs = p[i]+D;
i32 l = i;
i32 r = p.size();
while(r-l > 1)
{
i32 m = (r+l)/2;
if(p[m]>thrs) r = m;
else l = m;
}
c += (l-i);
}
cout << c << "\n";
}
} // d1
namespace d2
{
#define MAXDIM 75010
using pt = array<int,2>;
//using rect = array<int,4>; // sx,sy,ex,ey
struct rect
{
int sx,sy,ex,ey;
const bool contains(const rect& other) const
{
for(int i : {other.sx,other.ex}) if (i < sx || i > ex) return false;
for(int i : {other.sy,other.ey}) if (i < sy || i > ey) return false;
return true;
}
const bool contains(const pt& other) const
{
return sx <= other[0] && other[0] <= ex && sy <= other[1] && other[1] <= ey;
}
const bool intersects(const rect& other) const
{
if (other.ex < sx || ex < other.sx) return false;
if (other.ey < sy || ey < other.sy) return false;
return true;
}
};
pair<rect,rect> split(rect bounds, pt point, int axis)
{
pair<rect,rect> a = {bounds,bounds};
if(axis)
{
// split along y axis
a.first.ey = point[1];
a.second.sy = point[1];
}
else
{
// split along x axis
a.first.ex = point[0];
a.second.sx = point[0];
}
return a;
}
struct KDtree
{
KDtree *a=nullptr,*b=nullptr;
pt p; // the split point. Is not included in further ranges.
int pcount; // count of points in total in this block. includes l,r and split points.
};
template<typename T, typename ...Args>
T* new_T(Args ... args)
{
static T* arrptr = nullptr;
static int c = 1024;
if(c >= 1024)
{
arrptr = new T[1024];
c = 0;
}
arrptr[c].~T();
return new(arrptr+(c++)) T(args...);
}
KDtree* makeTree(vector<pt>& p, int s=0,int e=INT_MIN,int d=0)
{
if(e==INT_MIN) e = p.size();
if(e<=s) return nullptr;
int axis = d%2;
sort(p.begin()+s,p.begin()+e,[&](pt a,pt b){
if(a[axis] != b[axis]) return a[axis] < b[axis];
return a[(axis+1)%2] < a[(axis+1)%2];
});
int sr = (s+e)/2;
int er = (s+e)/2;
while(sr > s && p[sr-1]==p[(s+e)/2]) sr--;
while(er < e && p[er]==p[(s+e)/2]) er++;
KDtree *t = new_T<KDtree>();
t->p = p[sr];
t->pcount = e-s;
t->a = makeTree(p,s,sr,d+1);
t->b = makeTree(p,er,e,d+1);
return t;
}
template<typename T>
T& at(vector<vector<T>>& o,int x, int y)
{
return o[MAXDIM+y][x];
}
void print_tree(KDtree*t,vector<vector<char>>& o,rect bounds = {0,-MAXDIM,2*MAXDIM-1,MAXDIM-1},int d = 0)
{
if(t==nullptr) return;
int axis = d%2;
rect a,b;
tie(a,b) = split(bounds,t->p,axis);
int count = t->pcount;
if(t->a != nullptr) count -= t->a->pcount;
if(t->b != nullptr) count -= t->b->pcount;
if(axis) for(int i = bounds.sx+1; i < bounds.ex; i++)
{at(o,i,t->p[1]) = '-';}
else for(int i = bounds.sy+1; i < bounds.ey; i++)
at(o,t->p[0],i) = '|';;
at(o,t->p[0],t->p[1]) = '0'+d;
print_tree(t->a,o,a,d+1);
print_tree(t->b,o,b,d+1);
}
i64 range_count(KDtree* t,const rect& range,rect bounds = {0,-30,60,30},int d=0)
{
if(t==nullptr) return 0;
if (range.contains(bounds)) return t->pcount;
if (!range.intersects(bounds)) return 0;
if(t->pcount==0) return 0; // might be unneccesary
int axis = d%2;
rect a,b;
tie(a,b) = split(bounds,t->p,axis);
i64 count = 0;
if (range.contains(t->p))
{
count = t->pcount;
if(t->a != nullptr) count -= t->a->pcount;
if(t->b != nullptr) count -= t->b->pcount;
}
count += range_count(t->a,range,a,d+1);
count += range_count(t->b,range,b,d+1);
return count;
}
void d2()
{
// k-d tree
i32 N,D,M;
cin >> N >> D >> M;
vector<pt> p(N);
for(auto && i : p)
{
int x,y;
cin >> x >> y;
i = {x+y,x-y};
}
// diagonal k-d tree?
// make k-d tree
// transform points into (x+y,x-y) coordinates
// metric is now absmax
// circles become squares aligned to the grid
// make k-d tree
KDtree *root = makeTree(p); // this permutes the elements in p
#ifdef PRINT
vector<vector<char>> o(2*MAXDIM,vector<char>(2*MAXDIM,' '));
print_tree(root,o);
at(o,3,1) = '*';
for(auto & i : o)
{
for(auto &j : i) cout << j;
cout << "\n";
}
#endif
i64 total_count=0;
for(auto i : p)
{
// range count for each point
// exclude self, and this double counts
// calculate range of it
rect range = {i[0]-D,i[1]-D,i[0]+D,i[1]+D};
i64 c = range_count(root,range)-1;
//cout << (i[0]+i[1])/2 << " " << (i[0]-i[1])/2 << ":\t" << c << "\n";
total_count += c;
}
total_count /= 2; // double count each pair
cout << total_count << "\n";
}
} // d2
namespace d3 {
// 3d diagonal k-d tree does not work
// might be possible to do 4d, but encounter curse of dimens
void d3() {}
}
int main()
{
cin.tie(nullptr)->sync_with_stdio(false);
i32 B;
cin >> B;
switch(B)
{
case 1: d1::d1();break;
case 2: d2::d2();break;
case 3: d3::d3();break;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
1100 KB |
Output is correct |
| 2 |
Correct |
16 ms |
1092 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
1492 KB |
Output is correct |
| 2 |
Correct |
24 ms |
1492 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
1492 KB |
Output is correct |
| 2 |
Correct |
20 ms |
1492 KB |
Output is correct |
| 3 |
Correct |
19 ms |
1468 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
324 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
92 ms |
2052 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
96 ms |
5000 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
97 ms |
5316 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
