Submission #314181

#TimeUsernameProblemLanguageResultExecution timeMemory
314181MetBDragon 2 (JOI17_dragon2)C++14
0 / 100
128 ms37336 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; #define N 200001 using namespace std; typedef unsigned long long ull; typedef long long ll; typedef long double ld; const ll INF = 1e18, MOD = 1e9 + 7, MOD2 = 1e6 + 3; struct Pt { ll x, y; Pt (int x, int y) : x (x), y (y) {} Pt () : x (0), y (0) {} ll cross (const Pt& b) const { return x * b.y - b.x * y; } bool up () const { return y > 0 or (y == 0 and x >= 0); } bool operator < (const Pt& b) const { return up() == b.up() ? cross (b) < 0 : up() > b.up(); } Pt operator - (const Pt& b) const { return Pt (x - b.x, y - b.y); } Pt operator - () const { return Pt (-x, -y); } } s, e; vector <int> vs[N], ve[N], v[N]; Pt p[N], pe[N], ps[N]; vector < pair <Pt, int> > ords, orde; map <int, ll> ans[N]; ll big[N], sz[N]; int n, m, q, bl = 400; struct BIT { int t[N]; void update (int x, int d) { for (; x < N; x = (x | (x + 1))) t[x] += d; } int get (int r) { int sum = 0; for (; r >= 0; r = (r & (r + 1)) - 1) sum += t[r]; return sum; } int get (int l, int r) { return get (r) - get (l - 1); } } t; int find (vector <pair <Pt, int>>& ord, Pt x) { return lower_bound (ord.begin(), ord.end(), make_pair (x,-1)) - ord.begin (); } int find_small (int i, int j) { int sum = 0, len = 0; //for (auto&& a : vs[j]) // cout << "(" << p[a].x << ", " << p[a].y << ")\n"; auto l = vs[j].begin (), r = vs[j].begin (); bool full = false; vector < pair <Pt, int> > vp; for (int x : v[i]) { if (ps[x].cross (e - s) > 0) vp.push_back ({-ps[x], x}); else vp.push_back ({ps[x], x}); //printf ("Points are (%lld,%lld)\n", vp.back ().first.x, vp.back ().first.y); } sort (vp.begin(), vp.end()); for (auto [p, x] : vp) { //printf ("Coming up point %d as (%lld, %lld)\n", x, p.x, p.y); while (len != vs[j].size () && (ps[*r] < -p || !p.up ())) { //cout << "Adding " << ps[*r].x << ' ' << ps[*r].y << endl; int x = find (orde, pe[*r]); len++; //cout << "As " << pe[*r].x << ' ' << pe[*r].y << ' ' << x << endl; t.update (x, 1); r++; if (r == vs[j].end ()) r = vs[j].begin (); if (l == r) full = true; } while (len && ps[*l] < p) { //cout << "Deleting " << ps[*l].x << ' ' << ps[*l].y << endl; int x = find (orde, pe[*l]); len--; //cout << "As " << pe[*r].x << ' ' << pe[*r].y << ' ' << x << endl; t.update (x, -1); l++; if (l == vs[j].end ()) l = vs[j].begin (); } auto ptr = l; //if (full) cout << "All of them" << endl; //{ // for (auto ptr = l; ptr != r; ptr++) { // printf ("Having vector %d in it as (%lld,%lld)\n", *ptr, pe[*ptr].x, pe[*ptr].y); // if (ptr == vs[j].end ()) ptr = vs[j].begin (); // } //} //cout << "Try by " << pe[x].x << ' ' << pe[x].y << endl; int l1 = find (orde, pe[x]), r1 = find (orde, -pe[x]); if (pe[x].cross (s - e) > 0) swap (l1, r1); //cout << l1 << ' ' << r1 << endl; if (l1 <= r1) sum += t.get (l1, r1); else sum += len - t.get (r1, l1); //cout << "New sum is " << sum << endl; } while (len) { //cout << "Deleting " << ps[*l].x << ' ' << ps[*l].y << endl; int x = find (orde, pe[*l]); t.update (x, -1); l++; len--; if (l == vs[j].end ()) l = vs[j].begin (); if (l == r) full = false; } return sum; } int main () { cin >> n >> m; for (int i = 0; i < n; i++) { int a, b, c; cin >> a >> b >> c; p[i] = Pt (a, b); v[c-1].push_back (i); } int x, y; cin >> x >> y; s = Pt (x, y); cin >> x >> y; e = Pt (x, y); for (int i = 0; i < n; i++) { ps[i] = p[i] - s; pe[i] = p[i] - e; ords.push_back ({ps[i], i}); ords.push_back ({-ps[i], i}); orde.push_back ({pe[i], i}); orde.push_back ({-pe[i], i}); } sort (ords.begin(), ords.end()); sort (orde.begin(), orde.end()); for (int i = 0; i < m; i++) { vs[i] = v[i]; ve[i] = v[i]; sz[i] = v[i].size (); sort (vs[i].begin(), vs[i].end(), [&](int a, int b) { return ps[a] < ps[b]; }); sort (ve[i].begin(), ve[i].end(), [&](int a, int b) { return pe[a] < pe[b]; }); } cin >> q; for (int i = 0; i < q; i++) { int a, b; cin >> a >> b; a--, b--; cout << find_small (a, b) << endl; } }

Compilation message (stderr)

dragon2.cpp: In function 'int find_small(int, int)':
dragon2.cpp:99:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   99 |  for (auto [p, x] : vp) {
      |            ^
dragon2.cpp:102:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |   while (len != vs[j].size () && (ps[*r] < -p || !p.up ())) {
      |          ~~~~^~~~~~~~~~~~~~~~
dragon2.cpp:125:8: warning: variable 'ptr' set but not used [-Wunused-but-set-variable]
  125 |   auto ptr = l;
      |        ^~~
dragon2.cpp:87:7: warning: variable 'full' set but not used [-Wunused-but-set-variable]
   87 |  bool full = false;
      |       ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...