oj.uz

Submission #819331

# Submission time Handle Problem Language Result Execution time Memory
819331 2023-08-10T09:29:08 Z 박영우(#10135) Dragon 2 (JOI17_dragon2) C++17
60 / 100
 4000 ms 77576 KB 
#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] = 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 tr[i].size() > tr[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 25 ms 48596 KB Output is correct
2 Correct 34 ms 49088 KB Output is correct
3 Correct 136 ms 49904 KB Output is correct
4 Correct 264 ms 58348 KB Output is correct
5 Correct 136 ms 58480 KB Output is correct
6 Correct 25 ms 48844 KB Output is correct
7 Correct 27 ms 48864 KB Output is correct
8 Correct 25 ms 48568 KB Output is correct
9 Correct 24 ms 48716 KB Output is correct
10 Correct 25 ms 48688 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 59312 KB Output is correct
2 Correct 177 ms 63464 KB Output is correct
3 Correct 65 ms 56292 KB Output is correct
4 Correct 50 ms 57724 KB Output is correct
5 Correct 59 ms 59132 KB Output is correct
6 Correct 70 ms 61908 KB Output is correct
7 Correct 62 ms 61868 KB Output is correct
8 Correct 62 ms 59480 KB Output is correct
9 Correct 57 ms 62280 KB Output is correct
10 Correct 61 ms 61756 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 48596 KB Output is correct
2 Correct 34 ms 49088 KB Output is correct
3 Correct 136 ms 49904 KB Output is correct
4 Correct 264 ms 58348 KB Output is correct
5 Correct 136 ms 58480 KB Output is correct
6 Correct 25 ms 48844 KB Output is correct
7 Correct 27 ms 48864 KB Output is correct
8 Correct 25 ms 48568 KB Output is correct
9 Correct 24 ms 48716 KB Output is correct
10 Correct 25 ms 48688 KB Output is correct
11 Correct 58 ms 59312 KB Output is correct
12 Correct 177 ms 63464 KB Output is correct
13 Correct 65 ms 56292 KB Output is correct
14 Correct 50 ms 57724 KB Output is correct
15 Correct 59 ms 59132 KB Output is correct
16 Correct 70 ms 61908 KB Output is correct
17 Correct 62 ms 61868 KB Output is correct
18 Correct 62 ms 59480 KB Output is correct
19 Correct 57 ms 62280 KB Output is correct
20 Correct 61 ms 61756 KB Output is correct
21 Correct 61 ms 59360 KB Output is correct
22 Correct 165 ms 65320 KB Output is correct
23 Correct 1250 ms 64520 KB Output is correct
24 Correct 2297 ms 69248 KB Output is correct
25 Correct 280 ms 68304 KB Output is correct
26 Correct 194 ms 69508 KB Output is correct
27 Correct 79 ms 61632 KB Output is correct
28 Correct 89 ms 61572 KB Output is correct
29 Correct 273 ms 74636 KB Output is correct
30 Correct 177 ms 67456 KB Output is correct
31 Correct 187 ms 67676 KB Output is correct
32 Correct 189 ms 76232 KB Output is correct
33 Correct 1430 ms 71912 KB Output is correct
34 Correct 169 ms 68708 KB Output is correct
35 Correct 206 ms 77576 KB Output is correct
36 Correct 183 ms 69244 KB Output is correct
37 Correct 195 ms 69632 KB Output is correct
38 Correct 1356 ms 75372 KB Output is correct
39 Correct 1442 ms 74856 KB Output is correct
40 Correct 1342 ms 71952 KB Output is correct
41 Correct 228 ms 73856 KB Output is correct
42 Correct 239 ms 75148 KB Output is correct
43 Correct 285 ms 74564 KB Output is correct
44 Execution timed out 4090 ms 65204 KB Time limit exceeded
45 Halted 0 ms 0 KB -