Submission #819353

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
819353	2023-08-10T09:38:04 Z	flappybird	Dragon 2 (JOI17_dragon2)	C++17	60 / 100	4000 ms	75872 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);
}
struct fenwick {
	int N;
	vector<ll> tree;
	vector<int> updv;
	fenwick(int N = 0) :N(N) { tree.resize(N + 1); }
	void upd(int i, int x) {
		updv.push_back(i); while (i <= N) { tree[i] += x, i += i & -i; }
	}
	ll get(int i) { ll ans = 0; while (i) { ans += tree[i], i -= i & -i; } return ans; }
	void clear() {
		for (auto v : updv) {
			while (v <= N && tree[v]) {
				tree[v] = 0;
				v += v & -v;
			}
		}
		updv.clear();
	}
};
int nxv(int x) { return x % N + 1; }
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;
	map<pii, int> mp;
	for (i = 1; i <= Q; i++) {
		cin >> a >> b;
		int res = mp[pii(a, b)];
		if (res) {
			chk[i] = res;
			continue;
		}
		if (ord[a] < ord[b]) qv[a].emplace_back(b, 1, i);
		else qv[b].emplace_back(a, 0, i);
		mp[pii(a, b)] = i;
	}
	fenwick fen(N);
	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());
		fen.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) fen.upd(pos[ps[v][ptr++]].second, 1);
			ans[q] += mul * fen.get(y);
		}
	}
	for (i = 1; i <= Q; i++) cout << ans[i] << ln;
}

Compilation message

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

Subtask #1

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	30 ms	48468 KB	Output is correct
2	Correct	34 ms	49084 KB	Output is correct
3	Correct	131 ms	49700 KB	Output is correct
4	Correct	256 ms	57512 KB	Output is correct
5	Correct	152 ms	57556 KB	Output is correct
6	Correct	26 ms	48780 KB	Output is correct
7	Correct	25 ms	48668 KB	Output is correct
8	Correct	28 ms	48468 KB	Output is correct
9	Correct	24 ms	48680 KB	Output is correct
10	Correct	26 ms	48724 KB	Output is correct

Subtask #2

45.0 / 45.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	56 ms	58608 KB	Output is correct
2	Correct	166 ms	62852 KB	Output is correct
3	Correct	64 ms	55656 KB	Output is correct
4	Correct	50 ms	57012 KB	Output is correct
5	Correct	57 ms	58424 KB	Output is correct
6	Correct	59 ms	61200 KB	Output is correct
7	Correct	60 ms	61216 KB	Output is correct
8	Correct	60 ms	58764 KB	Output is correct
9	Correct	55 ms	61744 KB	Output is correct
10	Correct	67 ms	61204 KB	Output is correct

Subtask #3

0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	30 ms	48468 KB	Output is correct
2	Correct	34 ms	49084 KB	Output is correct
3	Correct	131 ms	49700 KB	Output is correct
4	Correct	256 ms	57512 KB	Output is correct
5	Correct	152 ms	57556 KB	Output is correct
6	Correct	26 ms	48780 KB	Output is correct
7	Correct	25 ms	48668 KB	Output is correct
8	Correct	28 ms	48468 KB	Output is correct
9	Correct	24 ms	48680 KB	Output is correct
10	Correct	26 ms	48724 KB	Output is correct
11	Correct	56 ms	58608 KB	Output is correct
12	Correct	166 ms	62852 KB	Output is correct
13	Correct	64 ms	55656 KB	Output is correct
14	Correct	50 ms	57012 KB	Output is correct
15	Correct	57 ms	58424 KB	Output is correct
16	Correct	59 ms	61200 KB	Output is correct
17	Correct	60 ms	61216 KB	Output is correct
18	Correct	60 ms	58764 KB	Output is correct
19	Correct	55 ms	61744 KB	Output is correct
20	Correct	67 ms	61204 KB	Output is correct
21	Correct	62 ms	58816 KB	Output is correct
22	Correct	168 ms	64664 KB	Output is correct
23	Correct	1241 ms	63740 KB	Output is correct
24	Correct	2225 ms	67684 KB	Output is correct
25	Correct	269 ms	66512 KB	Output is correct
26	Correct	188 ms	67604 KB	Output is correct
27	Correct	65 ms	60640 KB	Output is correct
28	Correct	64 ms	60656 KB	Output is correct
29	Correct	256 ms	72996 KB	Output is correct
30	Correct	186 ms	65892 KB	Output is correct
31	Correct	149 ms	65828 KB	Output is correct
32	Correct	178 ms	74588 KB	Output is correct
33	Correct	1379 ms	70328 KB	Output is correct
34	Correct	149 ms	66812 KB	Output is correct
35	Correct	187 ms	75872 KB	Output is correct
36	Correct	178 ms	67568 KB	Output is correct
37	Correct	178 ms	67640 KB	Output is correct
38	Correct	1302 ms	73712 KB	Output is correct
39	Correct	1481 ms	73076 KB	Output is correct
40	Correct	1314 ms	70268 KB	Output is correct
41	Correct	232 ms	72188 KB	Output is correct
42	Correct	233 ms	73512 KB	Output is correct
43	Correct	290 ms	72972 KB	Output is correct
44	Execution timed out	4070 ms	64068 KB	Time limit exceeded
45	Halted	0 ms	0 KB	-