oj.uz

Submission #298946

# Submission time Handle Problem Language Result Execution time Memory
298946 2020-09-14T11:04:04 Z mhy908 Circle selection (APIO18_circle_selection) C++14
87 / 100
 3000 ms 561044 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);}
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){
    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;
}
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;
        updlist.eb(mp(arr[i].F.S-arr[i].S.F, i), l[i]);
        updlist.eb(mp(arr[i].F.S+arr[i].S.F, i), l[i]);
        updlist.eb(mp(arr[i].F.S-arr[i].S.F, i), r[i]);
        updlist.eb(mp(arr[i].F.S+arr[i].S.F, i), r[i]);
    }
    svec(updlist);
    for(auto i:updlist)update(1, 1, idx.size(), i.S, i.F);
    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: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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 113016 KB Output is correct
2 Correct 80 ms 113016 KB Output is correct
3 Correct 76 ms 113016 KB Output is correct
4 Correct 76 ms 113016 KB Output is correct
5 Correct 75 ms 113020 KB Output is correct
6 Correct 78 ms 113144 KB Output is correct
7 Correct 78 ms 113144 KB Output is correct
8 Correct 77 ms 113144 KB Output is correct
9 Correct 76 ms 113144 KB Output is correct
10 Correct 77 ms 113144 KB Output is correct
11 Correct 75 ms 113144 KB Output is correct
12 Correct 75 ms 113272 KB Output is correct
13 Correct 76 ms 113144 KB Output is correct
14 Correct 75 ms 113144 KB Output is correct
15 Correct 75 ms 113184 KB Output is correct
16 Correct 78 ms 113784 KB Output is correct
17 Correct 80 ms 113912 KB Output is correct
18 Correct 78 ms 113912 KB Output is correct
19 Correct 97 ms 118564 KB Output is correct
20 Correct 96 ms 118696 KB Output is correct
21 Correct 98 ms 118564 KB Output is correct
22 Correct 96 ms 118568 KB Output is correct
23 Correct 98 ms 118568 KB Output is correct
24 Correct 100 ms 118568 KB Output is correct
25 Correct 96 ms 118560 KB Output is correct
26 Correct 97 ms 118564 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2709 ms 542684 KB Output is correct
2 Correct 2756 ms 545644 KB Output is correct
3 Correct 2723 ms 544132 KB Output is correct
4 Correct 2825 ms 542424 KB Output is correct
5 Correct 2185 ms 503804 KB Output is correct
6 Correct 2618 ms 550868 KB Output is correct
7 Correct 2528 ms 543696 KB Output is correct
8 Correct 2553 ms 548428 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 113016 KB Output is correct
2 Correct 861 ms 236724 KB Output is correct
3 Correct 2757 ms 551976 KB Output is correct
4 Correct 2783 ms 559740 KB Output is correct
5 Correct 2741 ms 544096 KB Output is correct
6 Correct 1324 ms 333896 KB Output is correct
7 Correct 659 ms 223060 KB Output is correct
8 Correct 162 ms 134120 KB Output is correct
9 Correct 2714 ms 549164 KB Output is correct
10 Correct 2897 ms 559344 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2590 ms 551732 KB Output is correct
2 Correct 2219 ms 558724 KB Output is correct
3 Correct 2760 ms 559956 KB Output is correct
4 Correct 2278 ms 559432 KB Output is correct
5 Correct 2264 ms 559528 KB Output is correct
6 Correct 2709 ms 559676 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 113016 KB Output is correct
2 Correct 80 ms 113016 KB Output is correct
3 Correct 76 ms 113016 KB Output is correct
4 Correct 76 ms 113016 KB Output is correct
5 Correct 75 ms 113020 KB Output is correct
6 Correct 78 ms 113144 KB Output is correct
7 Correct 78 ms 113144 KB Output is correct
8 Correct 77 ms 113144 KB Output is correct
9 Correct 76 ms 113144 KB Output is correct
10 Correct 77 ms 113144 KB Output is correct
11 Correct 75 ms 113144 KB Output is correct
12 Correct 75 ms 113272 KB Output is correct
13 Correct 76 ms 113144 KB Output is correct
14 Correct 75 ms 113144 KB Output is correct
15 Correct 75 ms 113184 KB Output is correct
16 Correct 78 ms 113784 KB Output is correct
17 Correct 80 ms 113912 KB Output is correct
18 Correct 78 ms 113912 KB Output is correct
19 Correct 97 ms 118564 KB Output is correct
20 Correct 96 ms 118696 KB Output is correct
21 Correct 98 ms 118564 KB Output is correct
22 Correct 96 ms 118568 KB Output is correct
23 Correct 98 ms 118568 KB Output is correct
24 Correct 100 ms 118568 KB Output is correct
25 Correct 96 ms 118560 KB Output is correct
26 Correct 97 ms 118564 KB Output is correct
27 Correct 120 ms 124528 KB Output is correct
28 Correct 122 ms 124528 KB Output is correct
29 Correct 121 ms 124528 KB Output is correct
30 Correct 125 ms 124656 KB Output is correct
31 Correct 127 ms 124784 KB Output is correct
32 Correct 122 ms 124528 KB Output is correct
33 Correct 840 ms 235472 KB Output is correct
34 Correct 838 ms 235464 KB Output is correct
35 Correct 859 ms 236288 KB Output is correct
36 Correct 776 ms 236584 KB Output is correct
37 Correct 767 ms 236636 KB Output is correct
38 Correct 801 ms 236624 KB Output is correct
39 Correct 323 ms 180944 KB Output is correct
40 Correct 329 ms 180588 KB Output is correct
41 Correct 322 ms 181464 KB Output is correct
42 Correct 328 ms 185308 KB Output is correct
43 Correct 542 ms 235600 KB Output is correct
44 Correct 541 ms 235580 KB Output is correct
45 Correct 542 ms 235540 KB Output is correct
46 Correct 545 ms 235600 KB Output is correct
47 Correct 543 ms 235608 KB Output is correct
48 Correct 544 ms 235612 KB Output is correct
49 Correct 543 ms 235476 KB Output is correct
50 Correct 550 ms 235484 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 113016 KB Output is correct
2 Correct 80 ms 113016 KB Output is correct
3 Correct 76 ms 113016 KB Output is correct
4 Correct 76 ms 113016 KB Output is correct
5 Correct 75 ms 113020 KB Output is correct
6 Correct 78 ms 113144 KB Output is correct
7 Correct 78 ms 113144 KB Output is correct
8 Correct 77 ms 113144 KB Output is correct
9 Correct 76 ms 113144 KB Output is correct
10 Correct 77 ms 113144 KB Output is correct
11 Correct 75 ms 113144 KB Output is correct
12 Correct 75 ms 113272 KB Output is correct
13 Correct 76 ms 113144 KB Output is correct
14 Correct 75 ms 113144 KB Output is correct
15 Correct 75 ms 113184 KB Output is correct
16 Correct 78 ms 113784 KB Output is correct
17 Correct 80 ms 113912 KB Output is correct
18 Correct 78 ms 113912 KB Output is correct
19 Correct 97 ms 118564 KB Output is correct
20 Correct 96 ms 118696 KB Output is correct
21 Correct 98 ms 118564 KB Output is correct
22 Correct 96 ms 118568 KB Output is correct
23 Correct 98 ms 118568 KB Output is correct
24 Correct 100 ms 118568 KB Output is correct
25 Correct 96 ms 118560 KB Output is correct
26 Correct 97 ms 118564 KB Output is correct
27 Correct 2709 ms 542684 KB Output is correct
28 Correct 2756 ms 545644 KB Output is correct
29 Correct 2723 ms 544132 KB Output is correct
30 Correct 2825 ms 542424 KB Output is correct
31 Correct 2185 ms 503804 KB Output is correct
32 Correct 2618 ms 550868 KB Output is correct
33 Correct 2528 ms 543696 KB Output is correct
34 Correct 2553 ms 548428 KB Output is correct
35 Correct 75 ms 113016 KB Output is correct
36 Correct 861 ms 236724 KB Output is correct
37 Correct 2757 ms 551976 KB Output is correct
38 Correct 2783 ms 559740 KB Output is correct
39 Correct 2741 ms 544096 KB Output is correct
40 Correct 1324 ms 333896 KB Output is correct
41 Correct 659 ms 223060 KB Output is correct
42 Correct 162 ms 134120 KB Output is correct
43 Correct 2714 ms 549164 KB Output is correct
44 Correct 2897 ms 559344 KB Output is correct
45 Correct 2590 ms 551732 KB Output is correct
46 Correct 2219 ms 558724 KB Output is correct
47 Correct 2760 ms 559956 KB Output is correct
48 Correct 2278 ms 559432 KB Output is correct
49 Correct 2264 ms 559528 KB Output is correct
50 Correct 2709 ms 559676 KB Output is correct
51 Correct 120 ms 124528 KB Output is correct
52 Correct 122 ms 124528 KB Output is correct
53 Correct 121 ms 124528 KB Output is correct
54 Correct 125 ms 124656 KB Output is correct
55 Correct 127 ms 124784 KB Output is correct
56 Correct 122 ms 124528 KB Output is correct
57 Correct 840 ms 235472 KB Output is correct
58 Correct 838 ms 235464 KB Output is correct
59 Correct 859 ms 236288 KB Output is correct
60 Correct 776 ms 236584 KB Output is correct
61 Correct 767 ms 236636 KB Output is correct
62 Correct 801 ms 236624 KB Output is correct
63 Correct 323 ms 180944 KB Output is correct
64 Correct 329 ms 180588 KB Output is correct
65 Correct 322 ms 181464 KB Output is correct
66 Correct 328 ms 185308 KB Output is correct
67 Correct 542 ms 235600 KB Output is correct
68 Correct 541 ms 235580 KB Output is correct
69 Correct 542 ms 235540 KB Output is correct
70 Correct 545 ms 235600 KB Output is correct
71 Correct 543 ms 235608 KB Output is correct
72 Correct 544 ms 235612 KB Output is correct
73 Correct 543 ms 235476 KB Output is correct
74 Correct 550 ms 235484 KB Output is correct
75 Correct 2843 ms 553128 KB Output is correct
76 Correct 2844 ms 555688 KB Output is correct
77 Correct 2774 ms 550268 KB Output is correct
78 Correct 2758 ms 550984 KB Output is correct
79 Correct 2814 ms 561044 KB Output is correct
80 Correct 2799 ms 550816 KB Output is correct
81 Correct 2696 ms 559512 KB Output is correct
82 Correct 2745 ms 559440 KB Output is correct
83 Correct 2712 ms 559928 KB Output is correct
84 Correct 2901 ms 560264 KB Output is correct
85 Correct 2667 ms 559248 KB Output is correct
86 Correct 2691 ms 559936 KB Output is correct
87 Execution timed out 3128 ms 558288 KB Time limit exceeded
88 Halted 0 ms 0 KB -