Submission #819627

#	Time	Username	Problem	Language	Result	Execution time	Memory
819627		flappybird	Dragon 2 (JOI17_dragon2)	C++17	60 / 100	4069 ms	70928 KiB

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")
#include <sys/stat.h>
#include <sys/mman.h>
#include <unistd.h>
using namespace std;

/////////////////////////////////////////////////////////////////////////////////////////////
/*
 * Author : jinhan814
 * Date : 2021-05-06
 * Source : https://blog.naver.com/jinhan814/222266396476
 * Description : FastIO implementation for cin, cout. (mmap ver.)
 */
constexpr int SZ = 1 << 20;

class INPUT {
private:
	char* p;
	bool __END_FLAG__, __GETLINE_FLAG__;
public:
	explicit operator bool() { return !__END_FLAG__; }
	INPUT() {
		struct stat st; fstat(0, &st);
		p = (char*)mmap(0, st.st_size, PROT_READ, MAP_SHARED, 0, 0);
	}
	bool IsBlank(char c) { return c == ' ' || c == '\n'; }
	bool IsEnd(char c) { return c == '\0'; }
	char _ReadChar() { return *p++; }
	char ReadChar() {
		char ret = _ReadChar();
		for (; IsBlank(ret); ret = _ReadChar());
		return ret;
	}
	template<typename T> T ReadInt() {
		T ret = 0; char cur = _ReadChar(); bool flag = 0;
		for (; IsBlank(cur); cur = _ReadChar());
		if (cur == '-') flag = 1, cur = _ReadChar();
		for (; !IsBlank(cur) && !IsEnd(cur); cur = _ReadChar()) ret = 10 * ret + (cur & 15);
		if (IsEnd(cur)) __END_FLAG__ = 1;
		return flag ? -ret : ret;
	}
	string ReadString() {
		string ret; char cur = _ReadChar();
		for (; IsBlank(cur); cur = _ReadChar());
		for (; !IsBlank(cur) && !IsEnd(cur); cur = _ReadChar()) ret.push_back(cur);
		if (IsEnd(cur)) __END_FLAG__ = 1;
		return ret;
	}
	double ReadDouble() {
		string ret = ReadString();
		return stod(ret);
	}
	string getline() {
		string ret; char cur = _ReadChar();
		for (; cur != '\n' && !IsEnd(cur); cur = _ReadChar()) ret.push_back(cur);
		if (__GETLINE_FLAG__) __END_FLAG__ = 1;
		if (IsEnd(cur)) __GETLINE_FLAG__ = 1;
		return ret;
	}
	friend INPUT& getline(INPUT& in, string& s) { s = in.getline(); return in; }
} _in;

class OUTPUT {
private:
	char write_buf[SZ];
	int write_idx;
public:
	~OUTPUT() { Flush(); }
	explicit operator bool() { return 1; }
	void Flush() {
		write(1, write_buf, write_idx);
		write_idx = 0;
	}
	void WriteChar(char c) {
		if (write_idx == SZ) Flush();
		write_buf[write_idx++] = c;
	}
	template<typename T> int GetSize(T n) {
		int ret = 1;
		for (n = n >= 0 ? n : -n; n >= 10; n /= 10) ret++;
		return ret;
	}
	template<typename T> void WriteInt(T n) {
		int sz = GetSize(n);
		if (write_idx + sz >= SZ) Flush();
		if (n < 0) write_buf[write_idx++] = '-', n = -n;
		for (int i = sz; i-- > 0; n /= 10) write_buf[write_idx + i] = n % 10 | 48;
		write_idx += sz;
	}
	void WriteString(string s) { for (auto& c : s) WriteChar(c); }
	void WriteDouble(double d) { WriteString(to_string(d)); }
} _out;

/* operators */
INPUT& operator>> (INPUT& in, char& i) { i = in.ReadChar(); return in; }
INPUT& operator>> (INPUT& in, string& i) { i = in.ReadString(); return in; }
template<typename T, typename std::enable_if_t<is_arithmetic_v<T>>* = nullptr>
INPUT& operator>> (INPUT& in, T& i) {
	if constexpr (is_floating_point_v<T>) i = in.ReadDouble();
	else if constexpr (is_integral_v<T>) i = in.ReadInt<T>(); return in;
}

OUTPUT& operator<< (OUTPUT& out, char i) { out.WriteChar(i); return out; }
OUTPUT& operator<< (OUTPUT& out, string i) { out.WriteString(i); return out; }
template<typename T, typename std::enable_if_t<is_arithmetic_v<T>>* = nullptr>
OUTPUT& operator<< (OUTPUT& out, T i) {
	if constexpr (is_floating_point_v<T>) out.WriteDouble(i);
	else if constexpr (is_integral_v<T>) out.WriteInt<T>(i); return out;
}

/* macros */
#define fastio 1
#define cin _in
#define cout _out
#define istream INPUT
#define ostream OUTPUT
/////////////////////////////////////////////////////////////////////////////////////////////
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];
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 (stderr)

dragon2.cpp: In function 'INPUT& operator>>(INPUT&, T&)':
dragon2.cpp:105:2: warning: this 'else' clause does not guard... [-Wmisleading-indentation]
  105 |  else if constexpr (is_integral_v<T>) i = in.ReadInt<T>(); return in;
      |  ^~~~
dragon2.cpp:105:60: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'else'
  105 |  else if constexpr (is_integral_v<T>) i = in.ReadInt<T>(); return in;
      |                                                            ^~~~~~
dragon2.cpp: In function 'OUTPUT& operator<<(OUTPUT&, T)':
dragon2.cpp:113:2: warning: this 'else' clause does not guard... [-Wmisleading-indentation]
  113 |  else if constexpr (is_integral_v<T>) out.WriteInt<T>(i); return out;
      |  ^~~~
dragon2.cpp:113:59: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'else'
  113 |  else if constexpr (is_integral_v<T>) out.WriteInt<T>(i); return out;
      |                                                           ^~~~~~
dragon2.cpp: In function 'int main()':
dragon2.cpp:215:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  215 |   for (i = 0; i < v.size(); i++) if (!v[i]) break;
      |               ~~^~~~~~~~~~
dragon2.cpp:218:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  218 |   for (i = ind; i < v.size(); i++) nv.push_back(v[i]);
      |                 ~~^~~~~~~~~~
dragon2.cpp:221:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  221 |   for (i = 1; i < v.size(); i++) (c ? pos[v[i]].second : pos[v[i]].first) = i;
      |               ~~^~~~~~~~~~
dragon2.cpp:223:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  223 |   for (i = 1; i < v.size(); i++) {
      |               ~~^~~~~~~~~~
dragon2.cpp:276:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  276 |    while (ptr < ps[v].size() && pos[ps[v][ptr]].first <= x) upd(pos[ps[v][ptr++]].second, 1);
      |           ~~~~^~~~~~~~~~~~~~
dragon2.cpp: In member function 'void OUTPUT::Flush()':
dragon2.cpp:76:8: warning: ignoring return value of 'ssize_t write(int, const void*, size_t)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |   write(1, write_buf, write_idx);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 45 / 45
• Subtask 3: 0 / 40