Submission #298963

#	Time	Username	Problem	Language	Result	Execution time	Memory
298963		mhy908	Circle selection (APIO18_circle_selection)	C++14	100 / 100	2384 ms	463068 KiB

circle_selection

#include <bits/stdc++.h>
#define mp make_pair
#define eb emplace_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define svec(x) sort(all(x))
#define press(x) x.erase(unique(all(x)), x.end());
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;

int n, ans[300010], l[300010], r[300010];
pair<pii, pii> arr[300010];
vector<int> idx;
bool cmp(pair<pii, pii> a, pair<pii, pii> b){return mp(a.S.F, -a.S.S)>mp(b.S.F, -b.S.S);}
inline bool is_con(int a, int b){
    LL d=(LL)(arr[a].F.F-arr[b].F.F)*(arr[a].F.F-arr[b].F.F)+(LL)(arr[a].F.S-arr[b].F.S)*(arr[a].F.S-arr[b].F.S);
    LL rs=(LL)(arr[a].S.F+arr[b].S.F)*(arr[a].S.F+arr[b].S.F);
    return rs>=d;
}

struct NODE{
    vector<pii> vc;
    vector<int> par;
    int findpar(int num){return num==par[num]?num:par[num]=findpar(par[num]);}
    void query(int s, int e, int num){
        int nw=lower_bound(all(vc), mp(s, 0))-vc.begin();
        while(1){
            nw=findpar(nw);
            //printf("%d %d\n", nw);
            if(nw>=vc.size()||vc[nw].F>e)break;
            int nw2=vc[nw].S;
            if(ans[arr[nw2].S.S])par[nw]=findpar(nw+1);
            else if(is_con(nw2, num)){
                par[nw]=findpar(nw+1);
                ans[arr[nw2].S.S]=arr[num].S.S;
            }
            nw++;
        }
    }
    void init(){
        //svec(vc);
        par.resize(vc.size()+1);
        for(int i=0; i<par.size(); i++)par[i]=i;
    }
}tree[2400010];
void update(int point, int s, int e, int num, pii val){
    if(s==e){
        tree[point].vc.eb(val);
        return;
    }
    if(num<=(s+e)/2)update(point*2, s, (s+e)/2, num, val);
    else update(point*2+1, (s+e)/2+1, e, num, val);
}
void query(int point, int s, int e, int sx, int ex, int sy, int ey, int num){
    if(e<sx||s>ex)return;
    if(sx<=s&&e<=ex){
        tree[point].query(sy, ey, num);
        return;
    }
    query(point*2, s, (s+e)/2, sx, ex, sy, ey, num);
    query(point*2+1, (s+e)/2+1, e, sx, ex, sy, ey, num);
}
void init(int point, int s, int e){
    if(s==e){
        svec(tree[point].vc);
        tree[point].init();
    }
    if(s==e)return;
    init(point*2, s, (s+e)/2);
    init(point*2+1, (s+e)/2+1, e);
    int sl=tree[point*2].vc.size(), sr=tree[point*2+1].vc.size();
    tree[point].vc.resize(sl+sr);
    for(int i=0, j=0, k=0; i<sl||j<sr;){
        if(j==sr||(i<sl&&tree[point*2].vc[i]<tree[point*2+1].vc[j]))tree[point].vc[k++]=tree[point*2].vc[i++];
        else tree[point].vc[k++]=tree[point*2+1].vc[j++];
    }
    tree[point].init();
}

inline int readChar();
template<class T=int> inline T readInt();
static const int buf_size=4096;
inline int getChar() {
    static char buf[buf_size];
    static int len=0, pos=0;
    if(pos==len)pos=0, len=fread(buf, 1, buf_size, stdin);
    if(pos==len)return -1;
    return buf[pos++];
}
inline int readChar() {
    int c=getChar();
    while(c<=32)c=getChar();
    return c;
}
template <class T>
inline T readInt() {
    int s=1, c=readChar();
    T x=0;
    if(c=='-')s=-1, c=getChar();
    while('0'<=c&&c<='9')x=x*10+c-'0', c=getChar();
    return s==1?x:-x;
}
vector<pair<pii, int> > updlist;

int main(){
    //scanf("%d", &n);
    n=readInt();
    for(int i=1; i<=n; i++){
        //scanf("%d %d %d", &arr[i].F.F, &arr[i].F.S, &arr[i].S.F);
        arr[i].F.F=readInt();
        arr[i].F.S=readInt();
        arr[i].S.F=readInt();
        idx.eb(arr[i].F.F-arr[i].S.F);
        idx.eb(arr[i].F.F+arr[i].S.F);
        arr[i].S.S=i;
    }
    sort(arr+1, arr+n+1, cmp);
    svec(idx); press(idx);
    for(int i=1; i<=n; i++){
        l[i]=lower_bound(all(idx), arr[i].F.F-arr[i].S.F)-idx.begin()+1;
        r[i]=lower_bound(all(idx), arr[i].F.F+arr[i].S.F)-idx.begin()+1;
        update(1, 1, idx.size(), l[i], mp(arr[i].F.S-arr[i].S.F, i));
        update(1, 1, idx.size(), l[i], mp(arr[i].F.S+arr[i].S.F, i));
        update(1, 1, idx.size(), r[i], mp(arr[i].F.S-arr[i].S.F, i));
        update(1, 1, idx.size(), r[i], mp(arr[i].F.S+arr[i].S.F, i));
    }
    init(1, 1, idx.size());
    for(int i=1; i<=n; i++){
        if(ans[arr[i].S.S])continue;
        query(1, 1, idx.size(), l[i], r[i], arr[i].F.S-arr[i].S.F, arr[i].F.S+arr[i].S.F, i);
    }
    for(int i=1; i<=n; i++)printf("%d ", ans[i]);
}

Compilation message (stderr)

circle_selection.cpp: In member function 'void NODE::query(int, int, int)':
circle_selection.cpp:32:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |             if(nw>=vc.size()||vc[nw].F>e)break;
      |                ~~^~~~~~~~~~~
circle_selection.cpp: In member function 'void NODE::init()':
circle_selection.cpp:45:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |         for(int i=0; i<par.size(); i++)par[i]=i;
      |                      ~^~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 12 / 12
• Subtask 3: 15 / 15
• Subtask 4: 23 / 23
• Subtask 5: 30 / 30
• Subtask 6: 13 / 13