Submission #776505

#	Time	Username	Problem	Language	Result	Execution time	Memory
776505		maomao90	Dragon 2 (JOI17_dragon2)	C++17	100 / 100	3649 ms	9988 KiB

dragon2

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

#define REP(i, j, k) for (int i = (j); i < (k); i++)
#define RREP(i, j, k) for (int i = (j); i >= (k); i--)

template <class T>
inline bool mnto(T &a, const T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T &a, const T b) {return a < b ? a = b, 1 : 0;}

typedef long long ll;
typedef long double ld;
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
#define ALL(x) x.begin(), x.end()
#define SZ(x) (int) x.size()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
typedef tuple<int, int, int> iii;
typedef vector<iii> viii;

#ifndef DEBUG
#define cerr if (0) cerr
#endif

const int INF = 1000000005;
const ll LINF = 1000000000000000005;
const int MAXN = 60005;

struct Point {
	int x, y;
	friend Point& operator+=(Point &l, const Point &r) {
		l.x += r.x;
		l.y += r.y;
		return l;
	}
	friend Point& operator-=(Point &l, const Point &r) {
		l.x -= r.x;
		l.y -= r.y;
		return l;
	}
	Point operator+(const Point &o) const {
		Point res = *this;
		return res += o;
	}
	Point operator-(const Point &o) const {
		Point res = *this;
		return res -= o;
	}
	friend istream& operator>>(istream &is, Point &o) {
		return is >> o.x >> o.y;
	}
	friend ostream& operator<<(ostream &os, const Point &o) {
		return os << "(" << o.x << ", " << o.y << ")";
	}
};
ll cross(const Point &l, const Point &r) {
	return (ll) l.x * r.y - (ll) l.y * r.x;
}
ll dot(const Point &l, const Point &r) {
	return (ll) l.x * r.x + (ll) l.y * r.y;
}
int side(const Point &p) {
	if (p.y > 0 || (p.y == 0 && p.x >= 0)) {
		return 0;
	}
	return 1;
}

int n, m;
Point pt[MAXN];
vi grp[MAXN];
Point p[2];
int ord[2][MAXN];
int pos[MAXN][2];
vii rg[MAXN][2];
int q;

auto cmp(const Point &p) {
	return [&] (int l, int r) {
		Point lp = pt[l] - p, rp = pt[r] - p;
		if (side(lp) != side(rp)) {
			return side(lp) < side(rp);
		}
		return cross(lp, rp) > 0;
	};
}

int main() {
#ifndef DEBUG
	ios::sync_with_stdio(0), cin.tie(0);
#endif
	cin >> n >> m;
	REP (i, 0, n) {
		int c; cin >> pt[i] >> c;
		grp[c].pb(i);
	}
	cin >> p[0] >> p[1];
	REP (z, 0, 2) {
		iota(ord[z], ord[z] + n, 0);
		sort(ord[z], ord[z] + n, cmp(p[z]));
		REP (i, 0, n) {
			ord[z][i + n] = ord[z][i];
		}
	}
	REP (z, 0, 2) {
		REP (i, 0, n) {
			pos[ord[z][i]][z] = i;
		}
	}
	REP (z, 0, 2) {
		vi top, btm;
		int r = 0;
		REP (i, 0, n) {
			Point cp = pt[ord[z][i]];
			if (cross(cp - p[z], p[z ^ 1] - p[z]) > 0) {
				mxto(r, i);
				while (r + 1 < i + n && cross(cp - p[z], pt[ord[z][r + 1]] - p[z]) > 0) {
					r++;
				}
				if (r < n) {
					rg[ord[z][i]][z].pb({i, r});
				} else {
					rg[ord[z][i]][z].pb({i, n - 1});
					rg[ord[z][i]][z].pb({0, r - n});
				}
			}
		}
		int l = 2 * n;
		RREP (i, n - 1, 0) {
			Point cp = pt[ord[z][i]];
			if (cross(cp - p[z], p[z ^ 1] - p[z]) < 0) {
				mnto(l, i + n);
				while (l - 1 > i && cross(cp - p[z], pt[ord[z][l - 1]] - p[z]) < 0) {
					l--;
				}
				if (l >= n) {
					rg[ord[z][i]][z].pb({l - n, i});
				} else {
					rg[ord[z][i]][z].pb({l, n - 1});
					rg[ord[z][i]][z].pb({0, i});
				}
			}
		}
		cerr << z << '\n';
		REP (i, 0, n) {
			cerr << ' ' << i << '\n';
			for (auto [l, r] : rg[i][z]) {
				cerr << "  " << l << ' ' << r << '\n';
			}
		}
	}
	cin >> q;
	while (q--) {
		int f, g; cin >> f >> g;
		int ans = 0;
		for (int i : grp[f]) {
			for (int j : grp[g]) {
				bool bad = 0;
				REP (z, 0, 2) {
					bool gd = 0;
					for (auto [l, r] : rg[i][z]) {
						if (l <= pos[j][z] && pos[j][z] <= r) {
							gd = 1;
							break;
						}
					}
					if (!gd) {
						bad = 1;
						break;
					}
				}
				ans += !bad;
			}
		}
		cout << ans << '\n';
	}
	return 0;
}

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