oj.uz

Submission #252532

# Submission time Handle Problem Language Result Execution time Memory
252532 2020-07-25T19:33:28 Z shayan_p Circle selection (APIO18_circle_selection) C++14
64 / 100
 1947 ms 157724 KB 
// And you curse yourself for things you never done
 
#include<bits/stdc++.h>
 
#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)
 
using namespace std;
 
typedef long long ll;
typedef pair<int,int> pii;
 
const int maxn = 3e5 + 10, mod = 1e9 + 7, inf = 1e9 + 10;
const ll INF = 1e18;
 
pair<pii, int> p[maxn];
int arr[maxn], ans[maxn];
 
pii operator - (pii a, pii b){
    return {a.F - b.F, a.S - b.S};
}
pii operator + (pii a, pii b){
    return {a.F + b.F, a.S + b.S};
}
ll operator ^ (pii a, pii b){
    return 1ll * a.F * b.F + 1ll * a.S * b.S;
}
bool ok(int i, int j){
    return 1ll * (p[j].S + p[i].S) * (p[j].S + p[i].S) >= ((p[i].F - p[j].F) ^ (p[i].F - p[j].F));
}
 
vector<int> vx, vy;    
 
vector<int> val, fs;
vector<int> stock;
 
void push(int &lst, int x){
    fs.PB(lst);
    lst = sz(val);
    val.PB(x);
}
 
struct node{
    map<int, int> mp;
    void add(int pos, int x){
	mp[pos] = x;
    }
    void ask(int i){
	int pos = p[i].F.S;
	auto it = mp.lower_bound(pos);
	if(it != mp.end())
	    stock.PB(it->S);
	if(it != mp.begin())
	    stock.PB(prev(it)->S);
    }
};
struct node2{
    node2 *L = 0, *R = 0;
    node* seg = 0;
    void add(int f, int s, int pos, int x, int l = 0, int r = sz(vx)-1){
	if(f <= vx[l] && vx[r] <= s){
	    if(!seg)
		seg = new node();
	    seg->add(pos, x);
	    return;
	}
	if(r-l == 1)
	    return;
	int mid = (l+r) >> 1;	
	if(max(f, vx[l]) < min(s, vx[mid])){
	    if(!L)
		L = new node2();
	    L->add(f, s, pos, x, l, mid);
	}
	if(max(f, vx[mid]) < min(s, vx[r])){
	    if(!R)
		R = new node2();
	    R->add(f, s, pos, x, mid, r);
	}
    }
    void ask(int pos, int pos2, int l = 0, int r = sz(vx)-1){
	if(seg)
	    seg->ask(pos2);
	if(r-l == 1)
	    return;
	int mid = (l+r) >> 1;
	if(pos < vx[mid] && L)
	    L->ask(pos, pos2, l, mid);
	if(vx[mid] <= pos && R)
	    R->ask(pos, pos2, mid, r);	    
    }
};
 
 
int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie();
 
    node2* root = new node2();
    
    int n;
    cin >> n;
 
    for(int i = 0; i < n; i++){
	cin >> p[i].F.F >> p[i].F.S >> p[i].S;
	
	vx.PB(p[i].F.F - p[i].S);
	vx.PB(p[i].F.F + p[i].S + 1);
	
	vy.PB(p[i].F.S - p[i].S);
	vy.PB(p[i].F.S + p[i].S + 1);
	
	arr[i] = i;
    }
    auto cmp = [](int i, int j){
		   return (p[i].S == p[j].S ? i > j : p[i].S < p[j].S);
	       };
    sort(arr, arr + n, cmp);
 
    sort(vx.begin(), vx.end());
    vx.resize( unique(vx.begin(), vx.end()) - vx.begin() );
 
    sort(vy.begin(), vy.end());
    vy.resize( unique(vy.begin(), vy.end()) - vy.begin() );
 
    for(int i = n-1; i >= 0; i--){
	int I = arr[i];
	stock.clear();
	for(int w = -1; w <= 1; w++){
	    if(w != 0)
		root->ask(p[I].F.F + w * p[I].S, I); // kafie?
	}
	for(int id : stock){
	    if(ok(I, id)){
		if(ans[I] == 0 || cmp(ans[I] - 1, id))
		    ans[I] = id + 1;
	    }
	}
	if(ans[I] == 0){
	    ans[I] = I + 1;
	    root->add(p[I].F.F - p[I].S, p[I].F.F + p[I].S + 1, p[I].F.S, I);
	}
    }
    for(int i = 0; i < n; i++){
	cout << ans[i] << " ";
    }
    return cout << endl, 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 0 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 2 ms 384 KB Output is correct
17 Correct 1 ms 384 KB Output is correct
18 Correct 2 ms 384 KB Output is correct
19 Correct 5 ms 640 KB Output is correct
20 Correct 5 ms 640 KB Output is correct
21 Correct 6 ms 696 KB Output is correct
22 Correct 10 ms 2048 KB Output is correct
23 Correct 15 ms 3072 KB Output is correct
24 Correct 10 ms 1920 KB Output is correct
25 Correct 8 ms 1536 KB Output is correct
26 Correct 9 ms 1920 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 335 ms 13412 KB Output is correct
2 Correct 322 ms 13376 KB Output is correct
3 Correct 323 ms 13004 KB Output is correct
4 Correct 329 ms 13256 KB Output is correct
5 Correct 425 ms 17472 KB Output is correct
6 Correct 697 ms 52672 KB Output is correct
7 Correct 551 ms 23372 KB Output is correct
8 Correct 529 ms 32200 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 384 ms 53220 KB Output is correct
3 Correct 1550 ms 156620 KB Output is correct
4 Correct 1344 ms 156096 KB Output is correct
5 Correct 1536 ms 141172 KB Output is correct
6 Correct 656 ms 58072 KB Output is correct
7 Correct 235 ms 28000 KB Output is correct
8 Correct 29 ms 4476 KB Output is correct
9 Correct 1586 ms 157724 KB Output is correct
10 Correct 1947 ms 125008 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1070 ms 145408 KB Output is correct
2 Correct 636 ms 74184 KB Output is correct
3 Incorrect 1151 ms 30796 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 0 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 2 ms 384 KB Output is correct
17 Correct 1 ms 384 KB Output is correct
18 Correct 2 ms 384 KB Output is correct
19 Correct 5 ms 640 KB Output is correct
20 Correct 5 ms 640 KB Output is correct
21 Correct 6 ms 696 KB Output is correct
22 Correct 10 ms 2048 KB Output is correct
23 Correct 15 ms 3072 KB Output is correct
24 Correct 10 ms 1920 KB Output is correct
25 Correct 8 ms 1536 KB Output is correct
26 Correct 9 ms 1920 KB Output is correct
27 Correct 10 ms 768 KB Output is correct
28 Correct 10 ms 896 KB Output is correct
29 Correct 9 ms 896 KB Output is correct
30 Correct 23 ms 5120 KB Output is correct
31 Correct 18 ms 3840 KB Output is correct
32 Correct 19 ms 3712 KB Output is correct
33 Correct 107 ms 4708 KB Output is correct
34 Correct 108 ms 4708 KB Output is correct
35 Correct 111 ms 4704 KB Output is correct
36 Correct 266 ms 39136 KB Output is correct
37 Correct 268 ms 40032 KB Output is correct
38 Correct 330 ms 44000 KB Output is correct
39 Correct 183 ms 7656 KB Output is correct
40 Correct 181 ms 7652 KB Output is correct
41 Correct 196 ms 7648 KB Output is correct
42 Correct 184 ms 7524 KB Output is correct
43 Correct 184 ms 24548 KB Output is correct
44 Correct 191 ms 24544 KB Output is correct
45 Correct 191 ms 24552 KB Output is correct
46 Correct 188 ms 24548 KB Output is correct
47 Correct 179 ms 24548 KB Output is correct
48 Correct 178 ms 24544 KB Output is correct
49 Correct 182 ms 24608 KB Output is correct
50 Correct 180 ms 24548 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 0 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 2 ms 384 KB Output is correct
17 Correct 1 ms 384 KB Output is correct
18 Correct 2 ms 384 KB Output is correct
19 Correct 5 ms 640 KB Output is correct
20 Correct 5 ms 640 KB Output is correct
21 Correct 6 ms 696 KB Output is correct
22 Correct 10 ms 2048 KB Output is correct
23 Correct 15 ms 3072 KB Output is correct
24 Correct 10 ms 1920 KB Output is correct
25 Correct 8 ms 1536 KB Output is correct
26 Correct 9 ms 1920 KB Output is correct
27 Correct 335 ms 13412 KB Output is correct
28 Correct 322 ms 13376 KB Output is correct
29 Correct 323 ms 13004 KB Output is correct
30 Correct 329 ms 13256 KB Output is correct
31 Correct 425 ms 17472 KB Output is correct
32 Correct 697 ms 52672 KB Output is correct
33 Correct 551 ms 23372 KB Output is correct
34 Correct 529 ms 32200 KB Output is correct
35 Correct 1 ms 384 KB Output is correct
36 Correct 384 ms 53220 KB Output is correct
37 Correct 1550 ms 156620 KB Output is correct
38 Correct 1344 ms 156096 KB Output is correct
39 Correct 1536 ms 141172 KB Output is correct
40 Correct 656 ms 58072 KB Output is correct
41 Correct 235 ms 28000 KB Output is correct
42 Correct 29 ms 4476 KB Output is correct
43 Correct 1586 ms 157724 KB Output is correct
44 Correct 1947 ms 125008 KB Output is correct
45 Correct 1070 ms 145408 KB Output is correct
46 Correct 636 ms 74184 KB Output is correct
47 Incorrect 1151 ms 30796 KB Output isn't correct
48 Halted 0 ms 0 KB -