Submission #45351

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
45351	2018-04-13T03:30:33 Z	ssnsarang2023	Dragon 2 (JOI17_dragon2)	C++17	100 / 100	386 ms	56856 KB

dragon2

//#define debug

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> ii;
typedef long double ld;

#define SZ(x) ((int)x.size())

const int SQ = 316;
const int N = (int)3e4+5;

struct point {
	ll x, y;
	int t, idx;
	point(ll _x, ll _y, int _t, int _idx) : x(_x), y(_y), t(_t), idx(_idx) {}
	point() { x = y = 0, t = idx = 0; }
	inline bool operator<(const point &other) const;
} origin;

inline bool ccw(const point &a, const point &b, const point &c) {
	return a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y) > 0;
}

struct TData {
	int lo, hi, id;
	TData(int _lo, int _hi, int _id) : lo(_lo), hi(_hi), id(_id) {}
	TData() {}
	inline bool operator<(const TData &other) const {
		return hi < other.hi;
	}
};

int n, m, q;
vector<ii> b[N], c[N];
ll res[N*10], cnt[N];
vector<point> dragon, dragon2;
point human1, mid, human2;
vector<TData> g[178];
vector<int> pos_t[N];

inline bool point::operator <(const point &other) const {
	if (ccw(human2, *this, human1) && !ccw(human2, other, human1)) {
		return true;
	} else if (!ccw(human2, *this, human1) && ccw(human2, other, human1)) {
		return false;
	}
	return ccw(origin, *this, other);
}

struct fenwick {
private:
	vector<int> tree;
	int _n;
public:
	void init(int _sz) {
		tree.resize(_sz + 2);
		_n = _sz;
	}
	void update(int idx, int val) {
		for (; idx <= _n; idx += idx & -idx)
			tree[idx] += val;
	}
	int read(int idx) {
		int ans = 0;
		for (; idx; idx -= idx & -idx)
			ans += tree[idx];
		return ans;
	}
	void clear() {
		if (!SZ(tree)) return;
		tree.clear();
	}
} tr[N];

const int SQN = 173;

void solve(ll mul, ll mul2) {
	sort(dragon.begin(), dragon.end());
	for (int i = 0; i <= SQN+1; ++i) g[i].clear();
	for (int i = 0; i < n; ++i) {
		point tmp = point(mul2 * dragon[i].x, mul2 * dragon[i].y, 0, 0);
		int lo = upper_bound(dragon.begin(), dragon.end(), tmp) - dragon.begin();
		int hi = upper_bound(dragon.begin(), dragon.end(), human1) - dragon.begin();
		lo -= (mul2 == 1 && !ccw(human2, dragon[i], human1));
		if (hi < lo) swap(lo, hi);
		--hi;
		if (lo <= hi) {
			g[lo / SQN].push_back(TData(lo, hi, dragon[i].t));
		}
	}
	for (int i = 0; i <= SQN+1; ++i) {
		sort(g[i].begin(), g[i].end());
	}
	for (int i = 0; i <= SQN+1; ++i) {
		if (!SZ(g[i])) continue;
		memset(cnt, 0, sizeof(cnt));
		int Lmax = -1;
		for (const TData &v : g[i]) {
			Lmax = max(Lmax, v.lo);
		}
		int curL = Lmax - 1;
		for (const TData &v : g[i]) {
			int L = v.lo, R = v.hi, t = v.id;
			if (R < Lmax) {
				for (int j = L; j <= R; ++j) {
					++cnt[dragon[j].t];
				}
			} else {
				while (curL < R) {
					++curL;
					++cnt[dragon[curL].t];
				}
				for (int j = L; j < Lmax; ++j) {
					++cnt[dragon[j].t];
				}
			}
			for (int j = 0; j < SZ(b[t]); ++j) {
				res[b[t][j].second] += mul * cnt[b[t][j].first];
			}
			if (mul2 == -1) {
				for (int j = 0; j < SZ(c[t]); ++j) {
					res[c[t][j].second] += mul * cnt[c[t][j].first];
				}
			}
			if (R < Lmax) {
				for (int j = L; j <= R; ++j) {
					--cnt[dragon[j].t];
				}
			} else {
				for (int j = L; j < Lmax; ++j) {
					--cnt[dragon[j].t];
				}
			}
		}
	}
}

int pos[N];

void solve2(vector<point> &a1, vector<point> &a2) {
	memset(pos, 0, sizeof(pos));
	for (int i = 1; i <= m; ++i) {
		pos_t[i].clear();
		tr[i].clear();
	}
	for (int i = 0; i < SZ(a2); ++i) {
		pos[a2[i].idx] = i;
		pos_t[a2[i].t].push_back(i);
	}
	for (int i = 1; i <= m; ++i) {
		if (!SZ(pos_t[i])) continue;
		tr[i].init(SZ(pos_t[i]));
	}
	for (int i = 0; i < SZ(a1); ++i) {
		const point &v = a1[i];
		int pvidx = pos[v.idx];
		int idx = lower_bound(pos_t[v.t].begin(), pos_t[v.t].end(), pvidx) - pos_t[v.t].begin() + 1;
		tr[v.t].update(idx, 1);
		for (int j = 0; j < SZ(b[v.t]); ++j) {
			int idx2 = upper_bound(pos_t[b[v.t][j].first].begin(), pos_t[b[v.t][j].first].end(), pvidx) - pos_t[b[v.t][j].first].begin();
			int val = tr[b[v.t][j].first].read(idx2);
			res[b[v.t][j].second] += (ll)(idx2 - val);
		}
		for (int j = 0; j < SZ(c[v.t]); ++j) {
			int idx2 = upper_bound(pos_t[c[v.t][j].first].begin(), pos_t[c[v.t][j].first].end(), pvidx) - pos_t[c[v.t][j].first].begin();
			int val = tr[c[v.t][j].first].read(idx2);
			res[c[v.t][j].second] += (ll)(idx2 - val);
		}
	}
}

vector<point> upper1, upper2;
vector<point> lower1, lower2;

int main() {
#ifdef debug
	clock_t tStart = clock();
	//freopen("inp.txt", "rt", stdin);
#endif
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n >> m;
	dragon.resize(n), dragon2.resize(n);
	for (int i = 0; i < n; ++i) {
		cin >> dragon[i].x >> dragon[i].y >> dragon[i].t;
		dragon[i].idx = i;
	}
	cin >> human1.x >> human1.y >> human2.x >> human2.y;
	//move the coordinates
	if (human1.y > human2.y) swap(human1, human2);
	mid = human1;
	human2.x -= mid.x, human2.y -= mid.y;
	human1 = point(-human2.x, -human2.y, 0, 0);
	for (int i = 0; i < n; ++i) {
		dragon[i].x -= mid.x;
		dragon[i].y -= mid.y;
	}
	mid = point(0, 0, 0, 0);

	cin >> q;
	for (int i = 0, x, y; i < q; ++i) {
		cin >> x >> y;
		b[x].push_back(ii(y, i));
	}

	for (int i = 1; i <= m; ++i) {
		if (SZ(b[i]) > SQ) {
			for (int j = 0; j < SZ(b[i]); ++j) {
				c[b[i][j].first].push_back(ii(i, b[i][j].second));
			}
			b[i].clear();
		}
	}

	solve(-1, -1);
	solve(-1, 1);
	for (int i = 0; i < n; ++i) {
		dragon2[i].x = dragon[i].x - human2.x;
		dragon2[i].y = dragon[i].y - human2.y;
		dragon2[i].idx = dragon[i].idx;
		dragon2[i].t = dragon[i].t;
	}
	point pt_tmp1 = human1, pt_tmp2 = human2;
	human1 = point(mid.x - human2.x, mid.y - human2.y, 0, 0);
	human2 = point(-human1.x, -human1.y, 0, 0);
	dragon.swap(dragon2);
	solve(1, -1);
	solve(1, 1);
	dragon.swap(dragon2);

	point pt_tmp3 = human1, pt_tmp4 = human2;
	auto something = [] (vector<point> &re, const vector<point> &src, bool mode) {
		for (int i = 0; i < SZ(src); ++i) {
			const point &v = src[i];
			if (ccw(human2, v, human1) == mode) {
				re.push_back(v);
			}
		}
	};
	human1 = pt_tmp1, human2 = pt_tmp2;
	something(upper1, dragon, 1);
	something(lower2, dragon, 0);

	human1 = pt_tmp3, human2 = pt_tmp4;
	something(upper2, dragon2, 1);
	something(lower1, dragon2, 0);

	solve2(upper1, upper2);
	solve2(lower1, lower2);

	for (int i = 0; i < q; ++i) {
		cout << res[i] << "\n";
	}
#ifdef debug
	cout << "Total time: " << (int)(1000.0 * (double)(clock() - tStart) / CLOCKS_PER_SEC) << "ms\n";
#endif
	return 0;
}

Subtask #1

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	29 ms	4216 KB	Output is correct
2	Correct	26 ms	4324 KB	Output is correct
3	Correct	19 ms	4556 KB	Output is correct
4	Correct	59 ms	7512 KB	Output is correct
5	Correct	73 ms	8860 KB	Output is correct
6	Correct	10 ms	8860 KB	Output is correct
7	Correct	12 ms	8860 KB	Output is correct
8	Correct	12 ms	8860 KB	Output is correct
9	Correct	14 ms	8860 KB	Output is correct
10	Correct	14 ms	8860 KB	Output is correct

Subtask #2

45.0 / 45.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	100 ms	10700 KB	Output is correct
2	Correct	107 ms	11480 KB	Output is correct
3	Correct	96 ms	11964 KB	Output is correct
4	Correct	109 ms	12764 KB	Output is correct
5	Correct	110 ms	14184 KB	Output is correct
6	Correct	86 ms	14184 KB	Output is correct
7	Correct	70 ms	14396 KB	Output is correct
8	Correct	83 ms	15240 KB	Output is correct
9	Correct	107 ms	15492 KB	Output is correct
10	Correct	77 ms	16132 KB	Output is correct

Subtask #3

40.0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	29 ms	4216 KB	Output is correct
2	Correct	26 ms	4324 KB	Output is correct
3	Correct	19 ms	4556 KB	Output is correct
4	Correct	59 ms	7512 KB	Output is correct
5	Correct	73 ms	8860 KB	Output is correct
6	Correct	10 ms	8860 KB	Output is correct
7	Correct	12 ms	8860 KB	Output is correct
8	Correct	12 ms	8860 KB	Output is correct
9	Correct	14 ms	8860 KB	Output is correct
10	Correct	14 ms	8860 KB	Output is correct
11	Correct	100 ms	10700 KB	Output is correct
12	Correct	107 ms	11480 KB	Output is correct
13	Correct	96 ms	11964 KB	Output is correct
14	Correct	109 ms	12764 KB	Output is correct
15	Correct	110 ms	14184 KB	Output is correct
16	Correct	86 ms	14184 KB	Output is correct
17	Correct	70 ms	14396 KB	Output is correct
18	Correct	83 ms	15240 KB	Output is correct
19	Correct	107 ms	15492 KB	Output is correct
20	Correct	77 ms	16132 KB	Output is correct
21	Correct	97 ms	17392 KB	Output is correct
22	Correct	110 ms	18192 KB	Output is correct
23	Correct	241 ms	18704 KB	Output is correct
24	Correct	302 ms	22372 KB	Output is correct
25	Correct	159 ms	24260 KB	Output is correct
26	Correct	199 ms	26940 KB	Output is correct
27	Correct	73 ms	26940 KB	Output is correct
28	Correct	106 ms	27384 KB	Output is correct
29	Correct	156 ms	30776 KB	Output is correct
30	Correct	212 ms	31600 KB	Output is correct
31	Correct	192 ms	33300 KB	Output is correct
32	Correct	163 ms	35908 KB	Output is correct
33	Correct	363 ms	37116 KB	Output is correct
34	Correct	210 ms	38760 KB	Output is correct
35	Correct	181 ms	41572 KB	Output is correct
36	Correct	194 ms	42520 KB	Output is correct
37	Correct	171 ms	44372 KB	Output is correct
38	Correct	253 ms	46428 KB	Output is correct
39	Correct	386 ms	47476 KB	Output is correct
40	Correct	377 ms	48812 KB	Output is correct
41	Correct	181 ms	51256 KB	Output is correct
42	Correct	192 ms	53228 KB	Output is correct
43	Correct	184 ms	54536 KB	Output is correct
44	Correct	103 ms	54536 KB	Output is correct
45	Correct	98 ms	54536 KB	Output is correct
46	Correct	116 ms	54536 KB	Output is correct
47	Correct	141 ms	55428 KB	Output is correct
48	Correct	110 ms	55972 KB	Output is correct
49	Correct	122 ms	56856 KB	Output is correct