oj.uz

답안 #819353

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
819353 2023-08-10T09:38:04 Z flappybird Dragon 2 (JOI17_dragon2) C++17
60 / 100
 4000 ms 75872 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]) {
				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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -