QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#446260#8525. Mercenariesucup-team3924RE 151ms18760kbC++204.4kb2024-06-17 04:21:212024-06-17 04:21:22

Judging History

你现在查看的是最新测评结果

  • [2024-06-17 04:21:22]
  • 评测
  • 测评结果:RE
  • 用时:151ms
  • 内存:18760kb
  • [2024-06-17 04:21:21]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;


struct pt{
    long long x, y;
    bool operator<(const pt & p) const {
		return tie(x, y) < tie(p.x, p.y);
	}
	bool operator==(const pt & p) const {
		return tie(x,y) == tie(p.x, p.y);
	}
    pt operator + (const pt & p) const {
        return pt{x + p.x, y + p.y};
    }
    pt operator - (const pt & p) const {
        return pt{x - p.x, y - p.y};
    }
    long long cross(const pt & p) const {
        return x * p.y - y * p.x;
    }
    long long cross(const pt & a, const pt & b) const{
		return (a-*this).cross(b-*this);
	}
};

long long det(const pt &a, const pt &b, const pt &c){
	return a.cross(b, c);
}

int sgn(long long d){
	return (d > 0) - (d < 0);
}


struct Line {
	int a, b; long long c;
};

bool half(Line m){return m.a < 0 || (m.a == 0 && m.b < 0);};

void normalize(Line& m) {
	long long g = __gcd((long long)__gcd(abs(m.a), abs(m.b)), abs(m.c));
	if (half(m)) g *= -1;
	m.a /= g, m.b /= g, m.c /= g;
}

bool operator<(Line m, Line n){
	return make_pair(half(m), (long long)m.b * n.a) <
		   make_pair(half(n), (long long)m.a * n.b);
}



Line LineFromPoints(int x1, int y1, int x2, int y2) {
	int a = y1 - y2, b = x2 - x1;
	long long c = (long long)a * x1 + (long long)b * y1;
	return {a, b, c}; // halfplane points to the l e f t of vec .
}



vector<pt>minkowski(const vector<pt> &P, const vector<pt> &Q){
	int n = P.size(), m = Q.size();
	if(n == 0 || m == 0)return {};
	vector<pt>res = {P[0] + Q[0]};
	for(int i = 1, j = 1; i < n || j < m; ){
		if(i < n && (j == m ||
			(P[i] - P[i-1]).cross(Q[j] - Q[j-1]) < 0)){
			res.push_back(res.back() + P[i] - P[i-1]);
			++i;
		} else {
			res.push_back(res.back() + Q[j] - Q[j-1]);
			++j;
		}
	}
	return res;
}

vector<pt> merge(const vector<pt> &a, const vector<pt> &b){
	vector<pt> res;
	int n = a.size(), m = b.size();
	int j = 0;
	for(int i = 0; i < n; i++){
		while(j < m && b[j] < a[i])res.push_back(b[j++]);
		if(j < m && b[j] == a[i])continue;
		res.push_back(a[i]);
	}
	while(j < m)res.push_back(b[j++]);
	return res;
}

vector<pt>convexHull(vector<pt> P, bool sorted=false){
	if(!sorted){
		sort(P.begin(), P.end());
		P.erase(unique(P.begin(), P.end()), P.end());
	}
	if(P.size() <= 1)return P;
	vector<pt>ret;
	for(auto p : P){
		while(ret.size() > 0 && p.y >= ret.back().y)ret.pop_back();
		while(ret.size() >= 2 && sgn(det(ret.end()[-2], ret.end()[-1], p)) > 0)ret.pop_back();
		ret.push_back(p);
	}
	return ret;
}
	
pt bestie(const vector<pt> &hull, Line L){
	int l = 0, r = hull.size()-1;
	while(l <= r){
		int m = (l + r)/2;
		Line M = LineFromPoints(hull[m].x, hull[m].y, hull[m+1].x, hull[m+1].y);
		if(M < L)r = m - 1;
		else l = m + 1;
	}
	return hull[(l >= (int)hull.size()? l - 1: l)];
}

bool check(pt p, Line L){
	return ((long long)p.x * L.a + (long long)p.y * L.b) >= L.c;
}

const int MAXN = 1 + 200000;
int n;

vector<pt>items[2 * MAXN];
vector<pt>merc[2 * MAXN];

const vector<pt>org = {pt{0, 0}};

void build_items() {
	for(int i = n - 1; i > 0; --i)
		items[i] = minkowski(items[2 * i], items[2 * i + 1]);
}

void build_merc(){
	for(int i = n - 1; i > 0; --i)merc[i] = convexHull(merge(minkowski(merc[2*i], items[2*i+1]), merc[2*i+1]));
}

vector<pt>query(int l, int r){
	vector<pt>res = org;
	for(l += n, r += n; l < r; l >>= 1, r >>= 1){
		if(l&1)res = minkowski(res, items[l++]);
		if(r&1)res = minkowski(res, items[--r]);
	}
	return res;
}

int solve(int city, pt shift, Line L, int v, int tl, int tr, int l, int r){
	if(l > r)return -1;
	if(l == tl && r == tr){
		if(!check(bestie(merc[v], L) + shift, L)){
			return -1;
		}
		if(tl == tr)return tl;
	}
	int tm = (tl + tr)/2;
	int right = solve(city, shift, L, v * 2 +1, tm+1, tr, max(l, tm+1), r);
	if(right != -1)return right;
	shift = shift + bestie(query(max(l, tm+1), r + 1), L);
	return solve(city, shift, L, v*2, tl, tm, l, min(r, tm));
}


int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	int N = n;
	while(__builtin_popcount(N)!=1)N++;
	items[N] = org;
	for(int i = 0; i < n; i++){
		int x, y;
		cin >> x >> y;
		merc[N + i] = {pt{x, y}};
		if(i + 1 == n)break;
		int r;
		cin >> r;
		vector<pt>pts(r);
		for(auto &p : pts)cin >> p.x >> p.y;
		items[N+i+1] = convexHull(pts);
	}
	for(int i = n; i < N; i++)items[N + i] = org;
	

	n = N;
	build_items();
	build_merc();
	
	
	int q;
	cin >> q;
	while(q--){
		int v; int a, b;
		long long c;
		cin >> v >> a >> b >> c;
		Line L{a, b, c};
		int ans = solve(v, pt{0, 0}, L, 1, 0, n-1, 0, v-1);
		cout << (ans == -1? -1 : ans + 1) << '\n';
		
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3828kb

input:

3
1 1
2 1 2 1 2
3 2
5 1 5 4 3 3 4 5 1 1 2
4 5
12
1 1 1 1
2 1 1 1
3 1 1 1
3 1 1 9
3 2 2 20
3 1 2 18
3 1 2 19
3 1 2 20
3 0 1 8
2 1 0 4
2 1 0 3
2 1 0 2

output:

1
2
3
3
2
2
1
-1
1
-1
2
2

result:

ok 12 numbers

Test #2:

score: 0
Accepted
time: 1ms
memory: 3568kb

input:

2
47 11
1 98 25
9 90
10
1 32 28 1811
2 17 44 4114
1 36 88 2661
2 79 33 3681
1 53 26 2778
2 59 20 2332
2 63 45 4616
2 72 11 10835
1 13 28 919
2 16 59 4445

output:

1
-1
-1
2
-1
1
2
1
1
2

result:

ok 10 numbers

Test #3:

score: 0
Accepted
time: 1ms
memory: 3632kb

input:

3
87 42
5 69 12 82 79 10 88 45 51 40 3
18 6
5 73 100 58 41 40 88 54 5 40 98
31 63
100
3 32 13 1811
1 51 21 5318
1 32 5 2994
2 77 51 19184
2 78 60 1763
1 10 1 913
1 22 51 4057
1 2 5 385
2 50 15 989
2 65 53 1488
1 49 82 7708
2 33 90 1133
1 23 33 3388
1 92 36 9516
3 39 61 10014
2 43 55 1103
2 48 38 127...

output:

3
1
1
1
2
-1
-1
-1
2
2
-1
2
-1
1
2
2
-1
3
2
2
3
1
1
1
-1
1
1
1
3
1
-1
1
-1
1
2
1
2
1
1
1
1
1
-1
1
-1
-1
1
1
-1
-1
1
1
2
1
1
-1
2
-1
1
1
1
1
3
1
2
3
2
2
1
1
-1
1
1
3
1
1
1
3
2
1
1
2
1
2
1
2
1
-1
-1
-1
1
2
1
1
-1
-1
1
3
2
2

result:

ok 100 numbers

Test #4:

score: 0
Accepted
time: 151ms
memory: 18760kb

input:

2
309248041 338995438
500000 1235 4866 1931 3652 1921 258 545 587 3001 542 3074 1694 4944 206 3217 3135 2388 4791 1890 3281 3840 4614 4491 1339 4660 1708 2225 3199 736 1306 4175 4652 906 3509 2571 1578 50 981 402 4975 2730 2198 4546 3120 40 815 2492 518 2102 2651 1018 3996 1764 808 3934 4312 1981 40...

output:

2
1
-1
2
2
2
1
1
2
-1
2
2
1
1
2
1
2
2
1
2
2
1
-1
-1
1
-1
2
-1
1
2
1
1
1
1
-1
1
-1
-1
-1
1
2
2
1
1
1
2
-1
-1
1
-1
1
2
-1
1
2
1
2
2
-1
2
1
2
2
-1
2
2
-1
2
1
2
1
-1
-1
1
1
-1
2
1
2
2
1
1
1
1
2
2
-1
-1
1
2
2
-1
2
-1
-1
-1
1
2
1
1
2
2
1
-1
-1
2
2
2
1
-1
1
2
2
-1
1
-1
-1
-1
1
2
1
2
1
-1
-1
1
2
2
-1
2
2
2
...

result:

ok 200000 numbers

Test #5:

score: -100
Runtime Error

input:

200000
999999511 993051669
2 5000 5000 5000 5000
1000000000 1000000000
3 5000 5000 5000 5000 5000 5000
995868520 999999999
2 5000 5000 5000 5000
660478427 999992996
3 5000 5000 5000 5000 5000 5000
999999979 999999998
2 5000 5000 5000 5000
861450412 989532141
3 5000 5000 5000 5000 5000 5000
949861679...

output:


result: