Submission #786493

#	Time	Username	Problem	Language	Result	Execution time	Memory
786493		canadavid1	Pairs (IOI07_pairs)	C++14	30 / 100	103 ms	4232 KiB

pairs

#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;
}
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++) o[t->p[1]+MAXDIM][i] = '-';
    else     for(int i = bounds.sy+1; i < bounds.ey; i++) o[i+MAXDIM][t->p[0]] = '|';
    o[t->p[1]+MAXDIM][t->p[0]] = '0'+count;
    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
    /* vector<vector<char>> o(2*MAXDIM,vector<char>(2*MAXDIM,' '));
    print_tree(root,o);
    for(auto & i : o)
    {
        for(auto &j : i) cout << j;
        cout << "\n";
    } */
    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};
        total_count += range_count(root,range)-1;
    }
    total_count /= 2; // double count each pair
    cout << total_count << "\n";
}
} // d2


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();break;
    }
}

• Subtask 1: 6 / 6
• Subtask 2: 6 / 6
• Subtask 3: 6 / 6
• Subtask 4: 6 / 6
• Subtask 5: 6 / 6
• Subtask 6: 0 / 7
• Subtask 7: 0 / 7
• Subtask 8: 0 / 8
• Subtask 9: 0 / 8
• Subtask 10: 0 / 10
• Subtask 11: 0 / 10
• Subtask 12: 0 / 10
• Subtask 13: 0 / 10