Submission #705637

#TimeUsernameProblemLanguageResultExecution timeMemory
705637GusterGoose27Dragon 2 (JOI17_dragon2)C++11
0 / 100
5 ms1492 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef pair<int, int> pii; typedef pair<long double, int> pdi; pii operator+(pii a, pii b) { return pii(a.first+b.first, a.second+b.second); } pii operator-(pii a, pii b) { return pii(a.first-b.first, a.second-b.second); } ll operator*(pii a, pii b) { return (ll)a.first*b.second-(ll)a.second*b.first; } ll dot(pii a, pii b) { return (ll)a.first*b.first+(ll)a.second*b.second; } ld mag(pii a) { return sqrt(dot(a, a)); } ld getang(pii a, pii b) { // returns cos theta*mag(b) return dot(a, b)/mag(a)/mag(b); } const int MAXN = 3000; // should be 3e4 const int BLOCK = 1; // should be 100 const int MAXBLOCKS = MAXN/BLOCK; int n, m, q; vector<int> big_groups; int big_inv[MAXN]; ll num[MAXBLOCKS][MAXN]; pii points[MAXN]; vector<int> in_group[MAXN]; int id[MAXN]; pii p1, p2; vector<int> points_sorted[2][2]; // up or down, sorted by costheta of p1 or p2 int points_sorted_inv[2][MAXN]; // no reason to consider top or bottom, we are already going to know the side vector<int> group_sort[MAXN][2][2]; int bit[MAXN]; void ins(int p, int v) { for (; p < n; p |= (p+1)) bit[p] += v; } int sum(int p) { int s = 0; for (p++; p > 0; p &= (p-1)) s += bit[p-1]; return s; } pii base, comp_vec; struct comp { bool operator()(int a, int b) { return getang(comp_vec, points[a]-base) < getang(comp_vec, points[b]-base); } } comp; void make_num(int p, ll ans[]) { for (int j = 0; j < 2; j++) { if (j == 0) { base = p1; comp_vec = p2-p1; } else { base = p2; comp_vec = p1-p2; } vector<ld> updates; int num = group_sort[p][j^1][j].size(); for (int v: group_sort[p][j^1][j]) { // iterating over points of type p on the other side sorted by the first point sweeping left to righ updates.push_back(getang(comp_vec, base-points[v])); // negative } int m = points_sorted[j][j].size(); int k = 0; for (int i = 0; i < m; i++) { // iterating over all points not of type p on this side sorted by the left point angle left to right int cur = points_sorted[j][j][i]; if (id[cur] == p) continue; while (k < updates.size() && updates[k] < getang(comp_vec, points[cur]-base)) k++; ans[id[cur]] += k-num; } updates.clear(); base = p1+p2-base; for (int v: group_sort[p][j^1][j^1]) { // type p, opposite side, right point, sweeping left to right updates.push_back(getang(comp_vec, base-points[v])); // positive } k = 0; for (int i = 0; i < m; i++) { // not of type p, this side, right point, sweeping left to right int cur = points_sorted[j][j^1][i]; if (id[cur] == p) continue; while (k < updates.size() && updates[k] < getang(comp_vec, points[cur]-base)) k++; ans[id[cur]] += num-k; } fill(bit, bit+n, 0); m = points_sorted[j][j].size(); k = 0; updates.clear(); base = p1+p2-base; for (int v: group_sort[p][j][j]) updates.push_back(getang(comp_vec, points[v]-base)); // updates is full of things sweeping from left to right on top with respect to left point for (int i = 0; i < m; i++) { // sweep left to right from bottom pov, second point, on the bottom int cur = points_sorted[j][j][i]; if (id[cur] == p) continue; while (k < updates.size() && updates[k] < getang(comp_vec, points[cur]-base)) { int mn = -1; int mx = m; // which points have we passed int v = group_sort[p][j][j][k]; ld comp_ang = getang(comp_vec, points[v]-(p1+p2-base)); while (mx > mn+1) { int mid = (mn+mx)/2; int mpoint = points_sorted[j][j^1][mid]; if (getang(comp_vec, points[mpoint]-(p1+p2-base)) < comp_ang) mn = mid; else mx = mid; } ins(0, 1); ins(mx, -1); k++; } ans[id[cur]] += sum(points_sorted_inv[j^1][cur]); } } } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> n >> m; for (int i = 0; i < n; i++) { cin >> points[i].first >> points[i].second >> id[i]; id[i]--; in_group[id[i]].push_back(i); } cin >> p1.first >> p1.second >> p2.first >> p2.second; for (int i = 0; i < m; i++) { if (in_group[i].size() >= BLOCK) { big_groups.push_back(i); } for (int v: in_group[i]) { bool b = (p2-p1)*(points[v]-p1) < 0; for (int j = 0; j < 2; j++) { group_sort[i][b][j].push_back(v); points_sorted[b][j].push_back(v); } } base = p1; comp_vec = p2-p1; sort(group_sort[i][0][0].begin(), group_sort[i][0][0].end()); base = p2; sort(group_sort[i][0][1].begin(), group_sort[i][0][1].end()); comp_vec = p1-p2; sort(group_sort[i][1][1].begin(), group_sort[i][1][1].end()); base = p1; sort(group_sort[i][1][0].begin(), group_sort[i][1][0].end()); } base = p1; comp_vec = p2-p1; sort(points_sorted[0][0].begin(), points_sorted[0][0].end()); base = p2; sort(points_sorted[0][1].begin(), points_sorted[0][1].end()); comp_vec = p1-p2; sort(points_sorted[1][1].begin(), points_sorted[1][1].end()); base = p1; sort(points_sorted[1][0].begin(), points_sorted[1][0].end()); for (int j = 0; j < 2; j++) { for (int k = 0; k < 2; k++) { for (int i = 0; i < points_sorted[j][k].size(); i++) points_sorted_inv[k][points_sorted[j][k][i]] = i; } } for (int i = 0; i < big_groups.size(); i++) { make_num(big_groups[i], num[i]); big_inv[big_groups[i]] = i; } cin >> q; for (int i = 0; i < q; i++) { int x, y; cin >> x >> y; x--; y--; if (in_group[x].size() >= BLOCK) { cout << num[big_inv[x]][y] << "\n"; } else { // deal with this later } } }

Compilation message (stderr)

dragon2.cpp: In function 'void make_num(int, ll*)':
dragon2.cpp:88:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long double>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |    while (k < updates.size() && updates[k] < getang(comp_vec, points[cur]-base)) k++;
      |           ~~^~~~~~~~~~~~~~~~
dragon2.cpp:100:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long double>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |    while (k < updates.size() && updates[k] < getang(comp_vec, points[cur]-base)) k++;
      |           ~~^~~~~~~~~~~~~~~~
dragon2.cpp:113:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long double>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |    while (k < updates.size() && updates[k] < getang(comp_vec, points[cur]-base)) {
      |           ~~^~~~~~~~~~~~~~~~
dragon2.cpp: In function 'int main()':
dragon2.cpp:174:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  174 |    for (int i = 0; i < points_sorted[j][k].size(); i++) points_sorted_inv[k][points_sorted[j][k][i]] = i;
      |                    ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
dragon2.cpp:177:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  177 |  for (int i = 0; i < big_groups.size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...