Submission #379809

#	Time	Username	Problem	Language	Result	Execution time	Memory
379809		pit4h	Dragon 2 (JOI17_dragon2)	C++14	100 / 100	858 ms	36044 KiB

dragon2

#include<bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int MAXN = 3e4+1, MAXQ = 1e5+1;
int n, m, t[MAXN], q, ans[MAXQ];

int sgn(ll x) {
	return (x>=0)?x? 1: 0: -1;
}
struct Point {
	ll x, y;
	int id;
	Point() {}
	Point(ll _x, ll _y): x(_x), y(_y) {}
	void read() { cin>>x>>y; }
	Point operator-(const Point& o) const { return Point(x-o.x, y-o.y); }
	
	bool operator<(const Point& o) const { return make_pair(x, y) < make_pair(o.x, o.y); }
	ll cross(const Point& o) {
		return (ll)x*o.y - (ll)y*o.x;
	}
	ll cross(const Point& o1, const Point& o2) {
		return (o1 - *this).cross(o2 - *this);
	}
};
Point O1, O2;
bool cmp(Point p1, Point p2) { // clockwise
	if(sgn(O1.cross(O2, p1)) != sgn(O1.cross(O2, p2))) {
		return (O1.cross(O2, p1) < 0LL)? true : false;
	}
	return O1.cross(p1, p2) < 0LL;
}
Point p[MAXN], pp[MAXN], s[MAXN];
vector<int> tribe[MAXN];
vector<pair<int, int>> queries[MAXN];

int bit[MAXN];
void add(int idx, int delta) {
	assert(idx >= 0);
	for(; idx < n; idx = idx | (idx+1)) {
		bit[idx] += delta;
	}
}
int sum(int r) {
	assert(r >= 0);
	int res = 0;
	for(; r>=0; r = (r & (r+1)) - 1) {
		res += bit[r];
	}
	return res;
}
int sum(int l, int r) { 
	return sum(r) - ((l>0)?sum(l-1): 0);
}

void solve(vector<Point> pts, vector<pair<Point, int>> qs) {
	sort(pts.begin(), pts.end());
	sort(qs.begin(), qs.end());
	int j = 0;
	for(int i=0; i<(int)pts.size(); ++i) {
		while(j < (int)qs.size() && qs[j].st < pts[i]) {
			ans[qs[j].nd] += sum(0, qs[j].st.y-1);
			j++;
		}
		add(pts[i].y-1, 1);
	}
	while(j < (int)qs.size()) {
		ans[qs[j].nd] += sum(0, qs[j].st.y-1);
		j++;
	}
	for(int i=0; i<(int)pts.size(); ++i) {
		add(pts[i].y-1, -1);
	}
}

Point reflect(Point pt, Point o) {
	ll dx = o.x - pt.x, dy = o.y - pt.y;
	pt.x += 2LL*dx, pt.y += 2LL*dy;
	return pt;
}
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin>>n>>m;
	for(int i=1; i<=n; ++i) {
		p[i].read();	
		p[i].id = i;
		cin>>t[i];
		tribe[t[i]].push_back(i);
	}
	Point P1, P2;
	P1.read(), P2.read();
	if(P2 < P1) swap(P1, P2);

	for(int i=1; i<=n; ++i) {
		if(P1.cross(P2, p[i]) > 0LL) {
			pp[i] = reflect(p[i], P1);	
		}
		else {
			pp[i] = p[i];
		}
	}
	O1 = P1, O2 = P2;
	sort(pp+1, pp+n+1, cmp);
	for(int i=1; i<=n; ++i) {
		s[pp[i].id].x = i;
	}
	
	for(int i=1; i<=n; ++i) { 
		if(P2.cross(P1, p[i]) < 0LL) {
			pp[i] = reflect(p[i], P2);	
		}
		else {
			pp[i] = p[i];
		}
	}
	O1 = P2, O2 = P1;
	sort(pp+1, pp+n+1, cmp);
	for(int i=1; i<=n; ++i) {
		s[pp[i].id].y = i;
	}

	cin>>q;
	for(int i=1; i<=q; ++i) {
		int a, b; cin>>a>>b;
		if(tribe[a].size() > tribe[b].size()) {
			for(auto j: tribe[b]) {
				queries[a].push_back(mp(j, -i));
			}
		}
		else {
			for(auto j: tribe[a]) {
				queries[b].push_back(mp(j, i));
			}
		}
	}
	
	for(int i=1; i<=m; ++i) {
		vector<Point> up, down, up_r, down_r;
		vector<pair<Point, int>> upq, downq, upq_r, downq_r;
		for(auto j: tribe[i]) {
			if(P1.cross(P2, p[j]) < 0LL) {
				down.push_back(Point(s[j].x, n-s[j].y+1));
				down_r.push_back(Point(n-s[j].x+1, s[j].y));
			}
			else {
				up.push_back(Point(n-s[j].x+1, s[j].y));
				up_r.push_back(Point(s[j].x, n-s[j].y+1));
			}
		}
		for(auto j: queries[i]) {
			if(j.nd > 0) {
				upq.push_back(mp(Point(n-s[j.st].x+1, s[j.st].y), j.nd));
				downq.push_back(mp(Point(s[j.st].x, n-s[j.st].y+1), j.nd));
			}
			else {
				if(P1.cross(P2, p[j.st]) > 0LL) {
					upq_r.push_back(mp(Point(s[j.st].x, n-s[j.st].y+1), -j.nd));
					downq.push_back(mp(Point(s[j.st].x, n-s[j.st].y+1), -j.nd));
				}
				else {
					upq.push_back(mp(Point(n-s[j.st].x+1, s[j.st].y), -j.nd));
					downq_r.push_back(mp(Point(n-s[j.st].x+1, s[j.st].y), -j.nd));
				}
			}
		}
		solve(up, upq);
		solve(down, downq);
		solve(up_r, upq_r);
		solve(down_r, downq_r);
	}

	for(int i=1; i<=q; ++i) {
		cout<<ans[i]<<'\n';
	}
}

• Subtask 1: 15 / 15
• Subtask 2: 45 / 45
• Subtask 3: 40 / 40