QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#446199#8525. Mercenariesucup-team3924WA 0ms3792kbC++205.6kb2024-06-17 00:48:302024-06-17 00:48:30

Judging History

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

  • [2024-06-17 00:48:30]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3792kb
  • [2024-06-17 00:48:30]
  • 提交

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

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




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

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

struct SegTree{
	vector<vector<pt>> items; int n;
	vector<vector<pt>> merc;
	SegTree(int n) : merc(2*n, org), items(2 * n, org), n(n){}
	

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

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

	
	vector<pt> sum(int b, int e) {
		vector<pt>r1 = org, r2 = org;
		for(b += n, e += n; b < e; b /= 2, e /= 2){
			if(b%2 == 0) r1 = minkowski(r1, items[b++]);
			if(e%2 == 0) r2 = minkowski(items[--e], r2);
		}
		return minkowski(r1, r2);
	}
	
	int solve(int city, pt shift, Line L, int v, int tl, int tr, int l, int r){
		//cout << v << ' ' << l << ' ' << r << '\n';
		if(l > r)return -1;
		if(l == tl && r == tr){
			if(!check(bestie(merc[v], L) + shift, L)){
				//cout << "current shift is " << shift.x << ' ' << shift.y << '\n';
				//cout << "available mercenaries are: ";
				//for(auto p : merc[v])cout << p.x << ' ' << p.y << '\t';
				//cout << "\nno mercenary in " << l << ' ' << r << " can beat the monster\n";
				return -1;
			}
			if(tl == tr)return tl;
		}
		int tm = (tl + tr)/2;
		int right = solve(city, shift, L, v * 2 + 2, tm+1, tr, max(l, tm+1), r);
		if(right != -1)return right;
		//cout << "there is no mercenary in " << max(l, tm + 1) << ' ' << r << " that can win so i need to remove items: ";
		//cout << "the interval is " << max(l, tm+1) << ' ' << r << '\n';
		//for(auto x : sum(max(l, tm+1), r+1))cout << x.x << ' ' << x.y << '\t';
		//cout << '\n';
		shift = shift + bestie(sum(max(l, tm+1), r+1), L);
		return solve(city, shift, L, v*2+1, tl, tm, l, min(r, tm));
	}
		
	
};

SegTree tree(0);



int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	tree = SegTree(n);
	for(int i = 0; i < n; i++){
		int x, y;
		cin >> x >> y;
		tree.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;
		}
		tree.items[n+i+1]= convexHull(pts);
	}
	tree.build_items();
	tree.build_merc();
	//for(auto p : tree.sum(2,3))cout << p.x << ' ' << p.y << '\t';
	//for(int i = 0; i < 6; i++){
		//cout << "i = " << i << ": ";
		//for(auto p : tree.merc[i])cout << p.x << ' ' << p.y << '\t';
		//cout << '\n';
	//}
	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 = tree.solve(v, pt{0, 0}, L, 0, 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: 0ms
memory: 3528kb

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
Wrong Answer
time: 0ms
memory: 3792kb

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
2
1
-1
1
1

result:

wrong answer 3rd numbers differ - expected: '-1', found: '1'