이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
}
컴파일 시 표준 에러 (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);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |