oj.uz

Submission #298929

# Submission time Handle Problem Language Result Execution time Memory
298929 2020-09-14T10:49:41 Z mhy908 Circle selection (APIO18_circle_selection) C++14
37 / 100
 3000 ms 531256 KB 
#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);}
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))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){
    tree[point].vc.eb(val);
    if(s==e)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){
    tree[point].init();
    if(s==e)return;
    init(point*2, s, (s+e)/2);
    init(point*2+1, (s+e)/2+1, e);
}

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;
}

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

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:42:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |         for(int i=0; i<par.size(); i++)par[i]=i;
      |                      ~^~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 113016 KB Output is correct
2 Correct 77 ms 113144 KB Output is correct
3 Correct 78 ms 113016 KB Output is correct
4 Correct 81 ms 113144 KB Output is correct
5 Correct 78 ms 113016 KB Output is correct
6 Correct 77 ms 113144 KB Output is correct
7 Correct 78 ms 113144 KB Output is correct
8 Correct 76 ms 113144 KB Output is correct
9 Correct 77 ms 113144 KB Output is correct
10 Correct 78 ms 113144 KB Output is correct
11 Correct 78 ms 113144 KB Output is correct
12 Correct 78 ms 113144 KB Output is correct
13 Correct 78 ms 113124 KB Output is correct
14 Correct 78 ms 113144 KB Output is correct
15 Correct 78 ms 113144 KB Output is correct
16 Correct 81 ms 113784 KB Output is correct
17 Correct 80 ms 113784 KB Output is correct
18 Correct 82 ms 113784 KB Output is correct
19 Correct 108 ms 118388 KB Output is correct
20 Correct 104 ms 118388 KB Output is correct
21 Correct 108 ms 118352 KB Output is correct
22 Correct 107 ms 118388 KB Output is correct
23 Correct 109 ms 118388 KB Output is correct
24 Correct 109 ms 118388 KB Output is correct
25 Correct 107 ms 118388 KB Output is correct
26 Correct 109 ms 118388 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3109 ms 525932 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 113016 KB Output is correct
2 Correct 1195 ms 231768 KB Output is correct
3 Execution timed out 3118 ms 531256 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3104 ms 531016 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 113016 KB Output is correct
2 Correct 77 ms 113144 KB Output is correct
3 Correct 78 ms 113016 KB Output is correct
4 Correct 81 ms 113144 KB Output is correct
5 Correct 78 ms 113016 KB Output is correct
6 Correct 77 ms 113144 KB Output is correct
7 Correct 78 ms 113144 KB Output is correct
8 Correct 76 ms 113144 KB Output is correct
9 Correct 77 ms 113144 KB Output is correct
10 Correct 78 ms 113144 KB Output is correct
11 Correct 78 ms 113144 KB Output is correct
12 Correct 78 ms 113144 KB Output is correct
13 Correct 78 ms 113124 KB Output is correct
14 Correct 78 ms 113144 KB Output is correct
15 Correct 78 ms 113144 KB Output is correct
16 Correct 81 ms 113784 KB Output is correct
17 Correct 80 ms 113784 KB Output is correct
18 Correct 82 ms 113784 KB Output is correct
19 Correct 108 ms 118388 KB Output is correct
20 Correct 104 ms 118388 KB Output is correct
21 Correct 108 ms 118352 KB Output is correct
22 Correct 107 ms 118388 KB Output is correct
23 Correct 109 ms 118388 KB Output is correct
24 Correct 109 ms 118388 KB Output is correct
25 Correct 107 ms 118388 KB Output is correct
26 Correct 109 ms 118388 KB Output is correct
27 Correct 144 ms 124144 KB Output is correct
28 Correct 152 ms 124272 KB Output is correct
29 Correct 148 ms 124160 KB Output is correct
30 Correct 151 ms 124272 KB Output is correct
31 Correct 146 ms 124396 KB Output is correct
32 Correct 149 ms 124272 KB Output is correct
33 Correct 1075 ms 231900 KB Output is correct
34 Correct 1100 ms 231392 KB Output is correct
35 Correct 1139 ms 231388 KB Output is correct
36 Correct 1128 ms 232280 KB Output is correct
37 Correct 1127 ms 232180 KB Output is correct
38 Correct 1151 ms 232156 KB Output is correct
39 Correct 628 ms 176604 KB Output is correct
40 Correct 625 ms 176428 KB Output is correct
41 Correct 637 ms 176564 KB Output is correct
42 Correct 628 ms 180720 KB Output is correct
43 Correct 1078 ms 232156 KB Output is correct
44 Correct 1054 ms 232412 KB Output is correct
45 Correct 1049 ms 232280 KB Output is correct
46 Correct 1079 ms 232156 KB Output is correct
47 Correct 1069 ms 231900 KB Output is correct
48 Correct 1066 ms 231896 KB Output is correct
49 Correct 1072 ms 232156 KB Output is correct
50 Correct 1065 ms 232024 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 113016 KB Output is correct
2 Correct 77 ms 113144 KB Output is correct
3 Correct 78 ms 113016 KB Output is correct
4 Correct 81 ms 113144 KB Output is correct
5 Correct 78 ms 113016 KB Output is correct
6 Correct 77 ms 113144 KB Output is correct
7 Correct 78 ms 113144 KB Output is correct
8 Correct 76 ms 113144 KB Output is correct
9 Correct 77 ms 113144 KB Output is correct
10 Correct 78 ms 113144 KB Output is correct
11 Correct 78 ms 113144 KB Output is correct
12 Correct 78 ms 113144 KB Output is correct
13 Correct 78 ms 113124 KB Output is correct
14 Correct 78 ms 113144 KB Output is correct
15 Correct 78 ms 113144 KB Output is correct
16 Correct 81 ms 113784 KB Output is correct
17 Correct 80 ms 113784 KB Output is correct
18 Correct 82 ms 113784 KB Output is correct
19 Correct 108 ms 118388 KB Output is correct
20 Correct 104 ms 118388 KB Output is correct
21 Correct 108 ms 118352 KB Output is correct
22 Correct 107 ms 118388 KB Output is correct
23 Correct 109 ms 118388 KB Output is correct
24 Correct 109 ms 118388 KB Output is correct
25 Correct 107 ms 118388 KB Output is correct
26 Correct 109 ms 118388 KB Output is correct
27 Execution timed out 3109 ms 525932 KB Time limit exceeded
28 Halted 0 ms 0 KB -