Submission #987346

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
987346	2024-05-22T15:40:51 Z	flappybird	Dragon 2 (JOI17_dragon2)	C++17	60 / 100	4000 ms	26828 KB

dragon2

#include <bits/stdc++.h>
#include <cassert>
#pragma GCC optimize("O0")
#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 30303
#define MAXQ 101010
#define INF 1000000100
#define bb ' '
#define ln '\n'
#define Ln '\n'
#define MOD 1000000007
pii 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[MAXQ];
int chk[MAX];
inline ll ccw(pii p1, pii p2, pii p3) {
	return (1ll * p1.first * p2.second + 1ll * p2.first * p3.second + 1ll * p3.first * p1.second) - (1ll * p2.first * p1.second + 1ll * p3.first * p2.second + 1ll * p1.first * p3.second);
}
int N, M;
inline 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<int> 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 int get(int i) { int 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] = pii(2 * INF, INF + 1);
	point[++N] = pii(2 * INF, -INF + 1);
	point[++N] = pii(-2 * INF, INF);
	point[++N] = pii(-2 * INF, -INF);
	pii 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	8 ms	5848 KB	Output is correct
2	Correct	15 ms	6516 KB	Output is correct
3	Correct	113 ms	5880 KB	Output is correct
4	Correct	188 ms	8864 KB	Output is correct
5	Correct	81 ms	9296 KB	Output is correct
6	Correct	5 ms	5976 KB	Output is correct
7	Correct	8 ms	4956 KB	Output is correct
8	Correct	6 ms	4952 KB	Output is correct
9	Correct	5 ms	5980 KB	Output is correct
10	Correct	5 ms	5980 KB	Output is correct

Subtask #2

45.0 / 45.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	40 ms	14980 KB	Output is correct
2	Correct	154 ms	19020 KB	Output is correct
3	Correct	45 ms	12560 KB	Output is correct
4	Correct	31 ms	14012 KB	Output is correct
5	Correct	41 ms	15424 KB	Output is correct
6	Correct	42 ms	19564 KB	Output is correct
7	Correct	42 ms	19316 KB	Output is correct
8	Correct	40 ms	15604 KB	Output is correct
9	Correct	38 ms	19908 KB	Output is correct
10	Correct	45 ms	19332 KB	Output is correct

Subtask #3

0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	5848 KB	Output is correct
2	Correct	15 ms	6516 KB	Output is correct
3	Correct	113 ms	5880 KB	Output is correct
4	Correct	188 ms	8864 KB	Output is correct
5	Correct	81 ms	9296 KB	Output is correct
6	Correct	5 ms	5976 KB	Output is correct
7	Correct	8 ms	4956 KB	Output is correct
8	Correct	6 ms	4952 KB	Output is correct
9	Correct	5 ms	5980 KB	Output is correct
10	Correct	5 ms	5980 KB	Output is correct
11	Correct	40 ms	14980 KB	Output is correct
12	Correct	154 ms	19020 KB	Output is correct
13	Correct	45 ms	12560 KB	Output is correct
14	Correct	31 ms	14012 KB	Output is correct
15	Correct	41 ms	15424 KB	Output is correct
16	Correct	42 ms	19564 KB	Output is correct
17	Correct	42 ms	19316 KB	Output is correct
18	Correct	40 ms	15604 KB	Output is correct
19	Correct	38 ms	19908 KB	Output is correct
20	Correct	45 ms	19332 KB	Output is correct
21	Correct	44 ms	16224 KB	Output is correct
22	Correct	155 ms	21632 KB	Output is correct
23	Correct	1260 ms	20376 KB	Output is correct
24	Correct	2258 ms	18624 KB	Output is correct
25	Correct	203 ms	17516 KB	Output is correct
26	Correct	139 ms	18640 KB	Output is correct
27	Correct	45 ms	16888 KB	Output is correct
28	Correct	46 ms	16916 KB	Output is correct
29	Correct	221 ms	24860 KB	Output is correct
30	Correct	84 ms	16524 KB	Output is correct
31	Correct	84 ms	17680 KB	Output is correct
32	Correct	118 ms	25692 KB	Output is correct
33	Correct	1336 ms	21508 KB	Output is correct
34	Correct	85 ms	17968 KB	Output is correct
35	Correct	133 ms	26828 KB	Output is correct
36	Correct	122 ms	18368 KB	Output is correct
37	Correct	115 ms	18780 KB	Output is correct
38	Correct	1288 ms	24468 KB	Output is correct
39	Correct	1395 ms	24120 KB	Output is correct
40	Correct	1270 ms	21152 KB	Output is correct
41	Correct	168 ms	23264 KB	Output is correct
42	Correct	166 ms	24360 KB	Output is correct
43	Correct	226 ms	23916 KB	Output is correct
44	Execution timed out	4037 ms	22036 KB	Time limit exceeded
45	Halted	0 ms	0 KB	-