Submission #819355

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
819355	2023-08-10T09:39:59 Z	flappybird	Dragon 2 (JOI17_dragon2)	C++17	60 / 100	4000 ms	69644 KB

dragon2

#include <bits/stdc++.h>
#include <cassert>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 501010
#define MAXS 20
#define INF 1000000100
#define bb ' '
#define ln '\n'
#define Ln '\n'
#define MOD 1000000007
pll point[MAX];
vector<int> ps[MAX];
pii pos[MAX];
int op[2][MAX];
int ord[MAX];
vector<tuple<int, int, int>> qv[MAX];
vector<tuple<int, int, int>> tr[MAX * 2]; //tribe range, x, y, mul
int rev[2][MAX];
ll ans[MAX];
int chk[MAX];
ll ccw(pll p1, pll p2, pll p3) {
	return (p1.first * p2.second + p2.first * p3.second + p3.first * p1.second) - (p2.first * p1.second + p3.first * p2.second + p1.first * p3.second);
}
int N, M;
void add(int i, pii rx, pii ry) {
	if (rx == pii(0, 0)) return;
	if (ry == pii(0, 0)) return;
	if (rx.second == 0) rx.second = N;
	if (ry.second == 0) ry.second = N;
	if (rx.first == 0) rx.first = 1;
	if (ry.first == 0) ry.first = 1;
	if (rx.first > rx.second) {
		add(i, pii(rx.first, N), ry);
		add(i, pii(1, rx.second), ry);
		return;
	}
	if (ry.first > ry.second) {
		add(i, rx, pii(ry.first, N));
		add(i, rx, pii(1, ry.second));
		return;
	}
	tr[i].emplace_back(rx.second, ry.second, 1);
	if (rx.first > 1) tr[i].emplace_back(rx.first - 1, ry.second, -1);
	if (ry.first > 1) tr[i].emplace_back(rx.second, ry.first - 1, -1);
	if (rx.first > 1 && ry.first > 1) tr[i].emplace_back(rx.first - 1, ry.first - 1, 1);
}
vector<ll> tree;
vector<int> updv;
inline void upd(int i, int x) {
	updv.push_back(i); while (i <= N) { tree[i] += x, i += i & -i; }
}
inline ll get(int i) { ll ans = 0; while (i) { ans += tree[i], i -= i & -i; } return ans; }
inline void clear() {
	for (auto v : updv) {
		while (v <= N && tree[v]) {
			tree[v] = 0;
			v += v & -v;
		}
	}
	updv.clear();
}
inline int nxv(int x) { return x % N + 1; }
inline int pvv(int x) { return (x + N - 2) % N + 1; }
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	cin >> N >> M;
	int i, t;
	for (i = 1; i <= N; i++) {
		cin >> point[i].first >> point[i].second >> t;
		ps[t].push_back(i);
	}
	point[++N] = pll(2 * INF, INF + 1);
	point[++N] = pll(2 * INF, -INF + 1);
	point[++N] = pll(-2 * INF, INF);
	point[++N] = pll(-2 * INF, -INF);
	pll X[2];
	cin >> X[0].first >> X[0].second;
	cin >> X[1].first >> X[1].second;
	for (auto c : { 0, 1 }) {
		vector<int> v1, v2;
		point[0] = X[c ^ 1];
		for (i = 0; i <= N; i++) ((point[i].second > X[c].second) ? v1 : v2).push_back(i);
		sort(v1.begin(), v1.end(), [&](int i, int j) {
			return ccw(X[c], point[i], point[j]) > 0;
			});
		sort(v2.begin(), v2.end(), [&](int i, int j) {
			return ccw(X[c], point[i], point[j]) > 0;
			});
		vector<int> v = v1;
		for (auto x : v2) v.push_back(x);
		int ind;
		for (i = 0; i < v.size(); i++) if (!v[i]) break;
		ind = i;
		vector<int> nv;
		for (i = ind; i < v.size(); i++) nv.push_back(v[i]);
		for (i = 0; i < ind; i++) nv.push_back(v[i]);
		swap(nv, v);
		for (i = 1; i < v.size(); i++) (c ? pos[v[i]].second : pos[v[i]].first) = i;
		int j = 1;
		for (i = 1; i < v.size(); i++) {
			while (ccw(point[v[i]], X[c], point[v[j]]) <= 0) {
				j = (j + 1) % (N + 1);
				if (i == j) break;
			}
			op[c][i] = j;
			if (j < i && j) op[c][i] = (op[c][i] + N) % (N + 1), rev[c][v[i]] = 1;
			if (i == j) j = (j + 1) % (N + 1);
		}
	}
	for (i = 1; i <= M; i++) {
		for (auto p : ps[i]) {
			pii rx = pii(op[0][pos[p].first], pos[p].first);
			pii ry = pii(op[1][pos[p].second], pos[p].second);
			if (rev[0][p]) swap(rx.first, rx.second);
			if (rev[1][p]) swap(ry.first, ry.second);
			add(i, rx, ry);
			rx = pii(op[0][pos[p].first], 0);
			ry = pii(op[1][pos[p].second], 0);
			if (rev[0][p]) swap(rx.first, rx.second);
			if (rev[1][p]) swap(ry.first, ry.second);
			add(i + M, rx, ry);
			if (rev[0][p]) rx = pii(nxv(op[0][pos[p].first]), pos[p].first);
			else rx = pii(pos[p].first, pvv(op[0][pos[p].first]));
			if (rev[1][p]) ry = pii(nxv(op[1][pos[p].second]), pos[p].second);
			else ry = pii(pos[p].second, pvv(op[1][pos[p].second]));
			add(i + M, rx, ry);
		}
	}
	for (i = 1; i <= M; i++) ord[i] = i;
	sort(ord + 1, ord + N + 1, [&](int i, int j) {return ps[i].size() > ps[j].size(); });
	int a, b;
	int Q;
	cin >> Q;
	for (i = 1; i <= Q; i++) {
		cin >> a >> b;
		if (ord[a] < ord[b]) qv[a].emplace_back(b, 1, i);
		else qv[b].emplace_back(a, 0, i);
	}
	tree.resize(N + 1);
	for (i = 1; i <= M; i++) {
		int v = ord[i];
		vector<pair<tuple<int, int, int>, int>> rv;
		for (auto& [p, m, q] : qv[v]) {
			m *= M;
			for (auto& t : tr[p + m]) rv.emplace_back(t, q);
		}
		sort(rv.begin(), rv.end());
		clear();
		int ptr = 0;
		sort(ps[v].begin(), ps[v].end(), [&](int i, int j) {return pos[i].first < pos[j].first; });
		for (auto& [t, q] : rv) {
			auto& [x, y, mul] = t;
			while (ptr < ps[v].size() && pos[ps[v][ptr]].first <= x) upd(pos[ps[v][ptr++]].second, 1);
			ans[q] += mul * get(y);
		}
	}
	for (i = 1; i <= Q; i++) cout << ans[i] << ln;
}

Compilation message

dragon2.cpp: In function 'int main()':
dragon2.cpp:99:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |   for (i = 0; i < v.size(); i++) if (!v[i]) break;
      |               ~~^~~~~~~~~~
dragon2.cpp:102:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |   for (i = ind; i < v.size(); i++) nv.push_back(v[i]);
      |                 ~~^~~~~~~~~~
dragon2.cpp:105:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |   for (i = 1; i < v.size(); i++) (c ? pos[v[i]].second : pos[v[i]].first) = i;
      |               ~~^~~~~~~~~~
dragon2.cpp:107:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |   for (i = 1; i < v.size(); i++) {
      |               ~~^~~~~~~~~~
dragon2.cpp:160:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  160 |    while (ptr < ps[v].size() && pos[ps[v][ptr]].first <= x) upd(pos[ps[v][ptr++]].second, 1);
      |           ~~~~^~~~~~~~~~~~~~

Subtask #1

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	25 ms	48464 KB	Output is correct
2	Correct	34 ms	49032 KB	Output is correct
3	Correct	130 ms	49408 KB	Output is correct
4	Correct	220 ms	51464 KB	Output is correct
5	Correct	95 ms	51464 KB	Output is correct
6	Correct	25 ms	48588 KB	Output is correct
7	Correct	24 ms	48656 KB	Output is correct
8	Correct	25 ms	48472 KB	Output is correct
9	Correct	24 ms	48724 KB	Output is correct
10	Correct	29 ms	48724 KB	Output is correct

Subtask #2

45.0 / 45.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	59 ms	58608 KB	Output is correct
2	Correct	177 ms	62884 KB	Output is correct
3	Correct	66 ms	55656 KB	Output is correct
4	Correct	51 ms	56924 KB	Output is correct
5	Correct	59 ms	58404 KB	Output is correct
6	Correct	60 ms	61204 KB	Output is correct
7	Correct	61 ms	61240 KB	Output is correct
8	Correct	59 ms	58808 KB	Output is correct
9	Correct	62 ms	61796 KB	Output is correct
10	Correct	68 ms	61192 KB	Output is correct

Subtask #3

0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	25 ms	48464 KB	Output is correct
2	Correct	34 ms	49032 KB	Output is correct
3	Correct	130 ms	49408 KB	Output is correct
4	Correct	220 ms	51464 KB	Output is correct
5	Correct	95 ms	51464 KB	Output is correct
6	Correct	25 ms	48588 KB	Output is correct
7	Correct	24 ms	48656 KB	Output is correct
8	Correct	25 ms	48472 KB	Output is correct
9	Correct	24 ms	48724 KB	Output is correct
10	Correct	29 ms	48724 KB	Output is correct
11	Correct	59 ms	58608 KB	Output is correct
12	Correct	177 ms	62884 KB	Output is correct
13	Correct	66 ms	55656 KB	Output is correct
14	Correct	51 ms	56924 KB	Output is correct
15	Correct	59 ms	58404 KB	Output is correct
16	Correct	60 ms	61204 KB	Output is correct
17	Correct	61 ms	61240 KB	Output is correct
18	Correct	59 ms	58808 KB	Output is correct
19	Correct	62 ms	61796 KB	Output is correct
20	Correct	68 ms	61192 KB	Output is correct
21	Correct	58 ms	58684 KB	Output is correct
22	Correct	168 ms	64668 KB	Output is correct
23	Correct	1218 ms	63424 KB	Output is correct
24	Correct	2163 ms	61688 KB	Output is correct
25	Correct	228 ms	60412 KB	Output is correct
26	Correct	131 ms	61348 KB	Output is correct
27	Correct	63 ms	59768 KB	Output is correct
28	Correct	65 ms	59680 KB	Output is correct
29	Correct	206 ms	66712 KB	Output is correct
30	Correct	103 ms	59560 KB	Output is correct
31	Correct	125 ms	59584 KB	Output is correct
32	Correct	129 ms	68340 KB	Output is correct
33	Correct	1292 ms	64056 KB	Output is correct
34	Correct	102 ms	60544 KB	Output is correct
35	Correct	138 ms	69644 KB	Output is correct
36	Correct	136 ms	61304 KB	Output is correct
37	Correct	142 ms	61372 KB	Output is correct
38	Correct	1293 ms	67368 KB	Output is correct
39	Correct	1355 ms	66956 KB	Output is correct
40	Correct	1269 ms	64060 KB	Output is correct
41	Correct	199 ms	65904 KB	Output is correct
42	Correct	195 ms	67368 KB	Output is correct
43	Correct	230 ms	66732 KB	Output is correct
44	Execution timed out	4062 ms	63192 KB	Time limit exceeded
45	Halted	0 ms	0 KB	-