제출 #819642

#제출 시각아이디문제언어결과실행 시간메모리
819642flappybirdDragon 2 (JOI17_dragon2)C++17
60 / 100
4056 ms24992 KiB
#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 30303 #define MAXQ 101010 #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[MAXQ]; 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 'int main()':
dragon2.cpp:99:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |   for (i = 0; i < v.size(); i++) if (!v[i]) break;
      |               ~~^~~~~~~~~~
dragon2.cpp:102:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |   for (i = ind; i < v.size(); i++) nv.push_back(v[i]);
      |                 ~~^~~~~~~~~~
dragon2.cpp:105:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |   for (i = 1; i < v.size(); i++) (c ? pos[v[i]].second : pos[v[i]].first) = i;
      |               ~~^~~~~~~~~~
dragon2.cpp:107:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |   for (i = 1; i < v.size(); i++) {
      |               ~~^~~~~~~~~~
dragon2.cpp:160:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  160 |    while (ptr < ps[v].size() && pos[ps[v][ptr]].first <= x) upd(pos[ps[v][ptr++]].second, 1);
      |           ~~~~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...