제출 #288869

#제출 시각아이디문제언어결과실행 시간메모리
288869rama_pangDragon 2 (JOI17_dragon2)C++14
100 / 100
1004 ms10872 KiB
#include <bits/stdc++.h> using namespace std; using Point = complex<long long>; long long Dot(Point a, Point b) { return real(conj(a) * b); } long long Cross(Point a, Point b) { return imag(conj(a) * b); } bool Clockwise(Point a, Point b, Point c) { return Cross(b - a, c - a) > 0; } bool CounterClockwise(Point a, Point b, Point c) { return Cross(b - a, c - a) < 0; } namespace std { template<class T> istream& operator>>(istream &is, complex<T> &inp) { T a, b; is >> a >> b; inp = complex<T>(a, b); return is; } bool operator<(Point p, Point q) { return Cross(p, q) > 0; } } class Fenwick { public: int sz; vector<int> tree; Fenwick() {} Fenwick(int sz) : sz(sz), tree(sz) {} void Update(int p, int x) { for (int i = p; i < sz; i |= i + 1) { tree[i] += x; } } int Sum(int p) { int res = 0; for (int i = p + 1; i > 0; i &= i - 1) { res += tree[i - 1]; } return res; } int Sum(int l, int r) { return Sum(r) - Sum(l - 1); } }; int main() { ios::sync_with_stdio(0); cin.tie(0), cout.tie(0); int N, M; cin >> N >> M; vector<int> C(N); vector<Point> P(N); for (int i = 0; i < N; i++) { cin >> P[i] >> C[i]; C[i]--; } Point X, Y; cin >> X >> Y; vector<bool> side(N); for (int i = 0; i < N; i++) { side[i] = Clockwise(X, Y, P[i]); } vector<Point> angle_x(N), angle_y(N); vector<pair<Point, int>> sorted_x(N); vector<pair<int, Point>> sorted_y(N); for (int i = 0; i < N; i++) { angle_x[i] = (side[i] ? P[i] - X : X - P[i]); sorted_x[i] = make_pair(angle_x[i], i); angle_y[i] = (side[i] ? P[i] - Y : Y - P[i]); sorted_y[i] = make_pair(C[i], angle_y[i]); } sort(begin(sorted_x), end(sorted_x)); sort(begin(sorted_y), end(sorted_y)); vector<int> pos_in_sorted(N), color_pos(M + 1); for (int i = 0; i < N; i++) { pos_in_sorted[i] = lower_bound(begin(sorted_y), end(sorted_y), make_pair(C[i], angle_y[i])) - begin(sorted_y); } for (int i = 0; i <= M; i++) { color_pos[i] = lower_bound(begin(sorted_y), end(sorted_y), make_pair(i, Y - X)) - begin(sorted_y);; } int Q; cin >> Q; vector<int> A(Q), B(Q); vector<long long> ans(Q); vector<vector<pair<int, int>>> query_a(M); vector<vector<pair<int, int>>> query_b(M); for (int i = 0; i < Q; i++) { cin >> A[i] >> B[i]; A[i]--, B[i]--; query_a[A[i]].emplace_back(B[i], i); } // O(N sqrt Q log N) const int SQRT = round(sqrt(Q)); for (int i = 0; i < M; i++) { if (query_a[i].size() >= SQRT) { for (auto j : query_a[i]) { query_b[j.first].emplace_back(i, j.second); } query_a[i].clear(); } } { // Solve query_a Fenwick f0(N); // side[i] = true Fenwick f1(N); // side[i] = false for (int i = 0; i < N; i++) { if (!side[i]) { f1.Update(pos_in_sorted[i], +1); } } for (int t = 0; t < N; t++) { int i = sorted_x[t].second; int c = C[i]; for (auto q : query_a[c]) { int pos = lower_bound(begin(sorted_y), end(sorted_y), make_pair(q.first, angle_y[i])) - begin(sorted_y); ans[q.second] += f0.Sum(pos, color_pos[q.first + 1] - 1); ans[q.second] += f1.Sum(color_pos[q.first], pos - 1); } if (side[i]) { f0.Update(pos_in_sorted[i], +1); } else { f1.Update(pos_in_sorted[i], -1); } } } { // Solve query_b Fenwick f0(N); // side[i] = true Fenwick f1(N); // side[i] = false for (int i = 0; i < N; i++) { f0.Update(pos_in_sorted[i], +1); } for (int t = 0; t < N; t++) { int i = sorted_x[t].second; int c = C[i]; for (auto q : query_b[c]) { int pos = lower_bound(begin(sorted_y), end(sorted_y), make_pair(q.first, angle_y[i])) - begin(sorted_y); if (side[i]) { ans[q.second] += f0.Sum(color_pos[q.first], pos - 1); } else { ans[q.second] += f1.Sum(pos, color_pos[q.first + 1] - 1); } } f0.Update(pos_in_sorted[i], -1); f1.Update(pos_in_sorted[i], +1); } } for (int i = 0; i < Q; i++) { cout << ans[i] << '\n'; } return 0; }

컴파일 시 표준 에러 (stderr) 메시지

dragon2.cpp: In function 'int main()':
dragon2.cpp:118:27: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'const int' [-Wsign-compare]
  118 |     if (query_a[i].size() >= SQRT) {
      |         ~~~~~~~~~~~~~~~~~~^~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...