QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#446067#8525. Mercenariesucup-team3924RE 1ms3552kbC++145.1kb2024-06-16 20:53:112024-06-16 20:53:11

Judging History

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

  • [2024-06-16 20:53:11]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:3552kb
  • [2024-06-16 20:53:11]
  • 提交

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

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();
	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++]);
		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;
		//cout << "checking m = " << m << '\t';
		Line M = LineFromPoints(hull[m].x, hull[m].y, hull[m+1].x, hull[m+1].y);
		//cout << (M < L) << '\n';
		if(M < L)r = m - 1;
		else l = m + 1;
	}
	return hull[(l >= (int)hull.size()? l - 1: l)];
}
	

vector<vector<pt>> items;
vector<vector<pt>> merc;
int n;

void build_items(const vector<vector<pt>>&hulls, int v, int tl, int tr){
	if(tl == tr){
		items[v] = hulls[tl];
	} else {
		int tm = (tl + tr)/2;
		build_items(hulls, v*2, tl, tm);
		build_items(hulls, v*2 + 1, tm + 1, tr);
		items[v] = minkowski(items[v*2], items[v*2 + 1]);
	}
}





vector<pt> sum(int v, int tl, int tr, int l, int r) {
    if (l > r){
        return {pt{0,0}};
	}
    if (l == tl && r == tr) {
        return items[v];
    }
    int tm = (tl + tr) / 2;
    return minkowski(sum(v*2, tl, tm, l, min(r, tm)),
		sum(v*2+1, tm+1, tr, max(l, tm+1), r));
	
}

void build_merc(const vector<pt>&mercenaries, int v, int tl, int tr){
	if(tl == tr){
		merc[v] = {mercenaries[tl]};
	} else {
		int tm = (tl + tr)/2;
		build_merc(mercenaries, v*2, tl, tm);
		build_merc(mercenaries, v*2 + 1, tm + 1, tr);
		merc[v] = convexHull(merge(minkowski(merc[v*2], items[v*2 + 1]), merc[v*2+1]));
	}
}


vector<pt>naj(int v, int tl, int tr, int l, int r){
	if(l > r){
		return {pt{0,0}};
	}
	if(l == tl && r == tr){
		return merc[v];
	}
	int tm = (tl + tr)/2;
	return convexHull(merge(minkowski(naj(v*2, tl, tm, l, min(r, tm)), sum(v*2+1, tm+1, tr, max(l, tm+1), r)), naj(v*2 + 1, tm + 1, tr, max(l, tm+1), r)), true);
}

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


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(sum(v*2 + 1, tm + 1, tr, max(l, tm+1), r), 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;
	vector<pt> mercenaries(n);
	vector<vector<pt>>hulls(n, {pt{0,0}});
	for(int i = 0; i < n; i++){
		cin >> mercenaries[i].x >> mercenaries[i].y;
		if(i + 1 == n)break;
		int r;
		cin >> r;
		vector<pt> pts(r);
		for(auto &p : pts){
			cin >> p.x >> p.y;
		}
		hulls[i + 1] = convexHull(pts);
	}
	while(__builtin_popcount(n) == 1)n++;
	items.assign(2 * n, {pt{0, 0}});
	merc.assign(2 * n + 1, {});
	build_items(hulls, 1, 0, n-1);
	build_merc(mercenaries, 1, 0, n-1);
	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: 1ms
memory: 3552kb

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: -100
Runtime Error

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:


result: