Submission #819360

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
819360	2023-08-10T09:42:01 Z	flappybird	Dragon 2 (JOI17_dragon2)	C++17	60 / 100	4000 ms	69260 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
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[MAX];
int chk[MAX];
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;
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	24 ms	48440 KB	Output is correct
2	Correct	34 ms	48972 KB	Output is correct
3	Correct	131 ms	49428 KB	Output is correct
4	Correct	209 ms	51432 KB	Output is correct
5	Correct	97 ms	51404 KB	Output is correct
6	Correct	26 ms	48596 KB	Output is correct
7	Correct	25 ms	48660 KB	Output is correct
8	Correct	24 ms	48476 KB	Output is correct
9	Correct	26 ms	48684 KB	Output is correct
10	Correct	24 ms	48668 KB	Output is correct

Subtask #2

45.0 / 45.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	55 ms	58436 KB	Output is correct
2	Correct	163 ms	62524 KB	Output is correct
3	Correct	63 ms	55388 KB	Output is correct
4	Correct	49 ms	56600 KB	Output is correct
5	Correct	55 ms	58068 KB	Output is correct
6	Correct	59 ms	60976 KB	Output is correct
7	Correct	59 ms	61036 KB	Output is correct
8	Correct	57 ms	58428 KB	Output is correct
9	Correct	55 ms	61580 KB	Output is correct
10	Correct	54 ms	60960 KB	Output is correct

Subtask #3

0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	24 ms	48440 KB	Output is correct
2	Correct	34 ms	48972 KB	Output is correct
3	Correct	131 ms	49428 KB	Output is correct
4	Correct	209 ms	51432 KB	Output is correct
5	Correct	97 ms	51404 KB	Output is correct
6	Correct	26 ms	48596 KB	Output is correct
7	Correct	25 ms	48660 KB	Output is correct
8	Correct	24 ms	48476 KB	Output is correct
9	Correct	26 ms	48684 KB	Output is correct
10	Correct	24 ms	48668 KB	Output is correct
11	Correct	55 ms	58436 KB	Output is correct
12	Correct	163 ms	62524 KB	Output is correct
13	Correct	63 ms	55388 KB	Output is correct
14	Correct	49 ms	56600 KB	Output is correct
15	Correct	55 ms	58068 KB	Output is correct
16	Correct	59 ms	60976 KB	Output is correct
17	Correct	59 ms	61036 KB	Output is correct
18	Correct	57 ms	58428 KB	Output is correct
19	Correct	55 ms	61580 KB	Output is correct
20	Correct	54 ms	60960 KB	Output is correct
21	Correct	62 ms	58488 KB	Output is correct
22	Correct	165 ms	64228 KB	Output is correct
23	Correct	1248 ms	63108 KB	Output is correct
24	Correct	2201 ms	61432 KB	Output is correct
25	Correct	221 ms	59992 KB	Output is correct
26	Correct	126 ms	60984 KB	Output is correct
27	Correct	62 ms	59372 KB	Output is correct
28	Correct	62 ms	59408 KB	Output is correct
29	Correct	258 ms	66352 KB	Output is correct
30	Correct	104 ms	59272 KB	Output is correct
31	Correct	106 ms	59208 KB	Output is correct
32	Correct	128 ms	67960 KB	Output is correct
33	Correct	1309 ms	63832 KB	Output is correct
34	Correct	99 ms	60252 KB	Output is correct
35	Correct	143 ms	69260 KB	Output is correct
36	Correct	134 ms	60944 KB	Output is correct
37	Correct	137 ms	61024 KB	Output is correct
38	Correct	1266 ms	67032 KB	Output is correct
39	Correct	1366 ms	66520 KB	Output is correct
40	Correct	1275 ms	63676 KB	Output is correct
41	Correct	185 ms	65548 KB	Output is correct
42	Correct	182 ms	66992 KB	Output is correct
43	Correct	233 ms	66420 KB	Output is correct
44	Execution timed out	4067 ms	62972 KB	Time limit exceeded
45	Halted	0 ms	0 KB	-