oj.uz

Submission #298943

# Submission time Handle Problem Language Result Execution time Memory
298943 2020-09-14T11:00:47 Z mhy908 Circle selection (APIO18_circle_selection) C++14
37 / 100
 3000 ms 555412 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))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: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 75 ms 113016 KB Output is correct
2 Correct 80 ms 113116 KB Output is correct
3 Correct 77 ms 113152 KB Output is correct
4 Correct 77 ms 113016 KB Output is correct
5 Correct 76 ms 113144 KB Output is correct
6 Correct 76 ms 113144 KB Output is correct
7 Correct 77 ms 113144 KB Output is correct
8 Correct 77 ms 113144 KB Output is correct
9 Correct 78 ms 113144 KB Output is correct
10 Correct 81 ms 113144 KB Output is correct
11 Correct 76 ms 113272 KB Output is correct
12 Correct 78 ms 113144 KB Output is correct
13 Correct 75 ms 113144 KB Output is correct
14 Correct 76 ms 113144 KB Output is correct
15 Correct 85 ms 113144 KB Output is correct
16 Correct 77 ms 113916 KB Output is correct
17 Correct 77 ms 113912 KB Output is correct
18 Correct 76 ms 113912 KB Output is correct
19 Correct 92 ms 118692 KB Output is correct
20 Correct 90 ms 118692 KB Output is correct
21 Correct 95 ms 118692 KB Output is correct
22 Correct 94 ms 118692 KB Output is correct
23 Correct 103 ms 118820 KB Output is correct
24 Correct 103 ms 118692 KB Output is correct
25 Correct 97 ms 118692 KB Output is correct
26 Correct 105 ms 118700 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2786 ms 544068 KB Output is correct
2 Correct 2895 ms 552144 KB Output is correct
3 Correct 2805 ms 550804 KB Output is correct
4 Correct 2975 ms 548972 KB Output is correct
5 Correct 2532 ms 508692 KB Output is correct
6 Execution timed out 3093 ms 555412 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 113016 KB Output is correct
2 Correct 1060 ms 239188 KB Output is correct
3 Execution timed out 3124 ms 552944 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 3083 ms 552364 KB Time limit exceeded
2 Halted 0 ms 0 KB -

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 113116 KB Output is correct
3 Correct 77 ms 113152 KB Output is correct
4 Correct 77 ms 113016 KB Output is correct
5 Correct 76 ms 113144 KB Output is correct
6 Correct 76 ms 113144 KB Output is correct
7 Correct 77 ms 113144 KB Output is correct
8 Correct 77 ms 113144 KB Output is correct
9 Correct 78 ms 113144 KB Output is correct
10 Correct 81 ms 113144 KB Output is correct
11 Correct 76 ms 113272 KB Output is correct
12 Correct 78 ms 113144 KB Output is correct
13 Correct 75 ms 113144 KB Output is correct
14 Correct 76 ms 113144 KB Output is correct
15 Correct 85 ms 113144 KB Output is correct
16 Correct 77 ms 113916 KB Output is correct
17 Correct 77 ms 113912 KB Output is correct
18 Correct 76 ms 113912 KB Output is correct
19 Correct 92 ms 118692 KB Output is correct
20 Correct 90 ms 118692 KB Output is correct
21 Correct 95 ms 118692 KB Output is correct
22 Correct 94 ms 118692 KB Output is correct
23 Correct 103 ms 118820 KB Output is correct
24 Correct 103 ms 118692 KB Output is correct
25 Correct 97 ms 118692 KB Output is correct
26 Correct 105 ms 118700 KB Output is correct
27 Correct 153 ms 124784 KB Output is correct
28 Correct 151 ms 124784 KB Output is correct
29 Correct 149 ms 124784 KB Output is correct
30 Correct 166 ms 124912 KB Output is correct
31 Correct 161 ms 124912 KB Output is correct
32 Correct 160 ms 124784 KB Output is correct
33 Correct 990 ms 236892 KB Output is correct
34 Correct 1050 ms 236800 KB Output is correct
35 Correct 1041 ms 237404 KB Output is correct
36 Correct 922 ms 237760 KB Output is correct
37 Correct 944 ms 237824 KB Output is correct
38 Correct 964 ms 237904 KB Output is correct
39 Correct 400 ms 181852 KB Output is correct
40 Correct 383 ms 181332 KB Output is correct
41 Correct 431 ms 182328 KB Output is correct
42 Correct 424 ms 186460 KB Output is correct
43 Correct 638 ms 236768 KB Output is correct
44 Correct 616 ms 236892 KB Output is correct
45 Correct 626 ms 236892 KB Output is correct
46 Correct 592 ms 237020 KB Output is correct
47 Correct 639 ms 236868 KB Output is correct
48 Correct 654 ms 237148 KB Output is correct
49 Correct 579 ms 236756 KB Output is correct
50 Correct 562 ms 236792 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 113116 KB Output is correct
3 Correct 77 ms 113152 KB Output is correct
4 Correct 77 ms 113016 KB Output is correct
5 Correct 76 ms 113144 KB Output is correct
6 Correct 76 ms 113144 KB Output is correct
7 Correct 77 ms 113144 KB Output is correct
8 Correct 77 ms 113144 KB Output is correct
9 Correct 78 ms 113144 KB Output is correct
10 Correct 81 ms 113144 KB Output is correct
11 Correct 76 ms 113272 KB Output is correct
12 Correct 78 ms 113144 KB Output is correct
13 Correct 75 ms 113144 KB Output is correct
14 Correct 76 ms 113144 KB Output is correct
15 Correct 85 ms 113144 KB Output is correct
16 Correct 77 ms 113916 KB Output is correct
17 Correct 77 ms 113912 KB Output is correct
18 Correct 76 ms 113912 KB Output is correct
19 Correct 92 ms 118692 KB Output is correct
20 Correct 90 ms 118692 KB Output is correct
21 Correct 95 ms 118692 KB Output is correct
22 Correct 94 ms 118692 KB Output is correct
23 Correct 103 ms 118820 KB Output is correct
24 Correct 103 ms 118692 KB Output is correct
25 Correct 97 ms 118692 KB Output is correct
26 Correct 105 ms 118700 KB Output is correct
27 Correct 2786 ms 544068 KB Output is correct
28 Correct 2895 ms 552144 KB Output is correct
29 Correct 2805 ms 550804 KB Output is correct
30 Correct 2975 ms 548972 KB Output is correct
31 Correct 2532 ms 508692 KB Output is correct
32 Execution timed out 3093 ms 555412 KB Time limit exceeded
33 Halted 0 ms 0 KB -