Submission #134137

#TimeUsernameProblemLanguageResultExecution timeMemory
134137AngusRitossaDragon 2 (JOI17_dragon2)C++14
60 / 100
4014 ms12488 KiB
#include <bits/stdc++.h> using namespace std; #ifdef DEBUG #define D(x...) printf(x) #else #define D(x...) #endif typedef long long ll; int n, m, g[30010], isbelow[30010], num1[30010], num2[30010]; vector<int> group[30010], ag[30010], bg[30010]; ll x[30010], y[30010]; pair<ll, ll> s, e; ll cross(pair<ll, ll> a, pair<ll, ll> b, pair<ll, ll> c) { a.first -= c.first, b.first -= c.first; a.second -= c.second, b.second -= c.second; return a.first*b.second - a.second*b.first; } void findids(bool rev, pair<ll, ll> s, pair<ll, ll> e, int* num) { // separate into left and right vector<pair<pair<ll, ll>, int> > below; for (int i = 0; i < n; i++) { pair<ll, ll> other = { x[i] + 2ll*(s.first-x[i]), y[i] + 2ll*(s.second-y[i]) }; // D("%lld %lld\n", other.first, other.second); if (cross(s, {x[i], y[i]}, e) < 0) { if (rev) below.push_back({other, i}); else isbelow[i] = 1, below.push_back({{ x[i], y[i] }, i }); } else { if (!rev) below.push_back({other, i}); else isbelow[i] = 1, below.push_back({{ x[i], y[i] }, i }); } // D("%d: isbelow %d\n", i, isbelow[i]); } sort(below.begin(), below.end(), [s](const pair<pair<ll, ll>, int> &a, const pair<pair<ll, ll>, int> &b) { return cross(a.first, b.first, s) < 0; }); if (rev) reverse(below.begin(), below.end()); // for (auto b : below) D("%d ", b.second); // D(" -- below\n"); for (int i = 0; i < (int)below.size(); i++) num[below[i].second] = i; } struct Node { int val, left, right; }; int upto; Node rangetree[30010*40]; void update(int node, int curr, int oldcurr, int cstart = 0, int cend = 30010) { rangetree[curr].val = rangetree[oldcurr].val; if (cstart == cend) { rangetree[curr].val++; return; } int mid = (cstart+cend)/2; if (node <= mid) { rangetree[curr].left = ++upto; rangetree[curr].right = rangetree[oldcurr].right; update(node, rangetree[curr].left, rangetree[oldcurr].left, cstart, mid); } else { rangetree[curr].right = ++upto; rangetree[curr].left = rangetree[oldcurr].left; update(node, rangetree[curr].right, rangetree[oldcurr].right, mid+1, cend); } rangetree[curr].val = rangetree[rangetree[curr].left].val + rangetree[rangetree[curr].right].val; } int query(int s, int e, int curr, int cstart = 0, int cend = 30010) { if (s <= cstart && cend <= e) return rangetree[curr].val; int mid = (cstart+cend)/2; if (e <= mid) return query(s, e, rangetree[curr].left, cstart, mid); else if (s > mid) return query(s, e, rangetree[curr].right, mid+1, cend); else return query(s, e, rangetree[curr].left, cstart, mid) + query(s, e, rangetree[curr].right, mid+1, cend); } int root[30010]; int aminlower(vector<int>&v, int x, int y, int l = 0) { if (v.empty()) return 0; if (x < num1[v[0]]) return 0; int s = 0; int e = v.size()-1; while (s < e) { int m = (s+e+1)/2; if (num1[v[m]] > x) e = m-1; else s = m; } return query(l, y, root[v[s]]); } int aminupper(vector<int> &v, int x, int y) { return aminlower(v, 1e9, 30010, y) - aminlower(v, x-1, 30010, y); } int main() { scanf("%d%d", &n, &m); for (int i = 0; i < n; i++) { scanf("%lld%lld%d", &x[i], &y[i], &g[i]); group[g[i]].push_back(i); } scanf("%lld%lld%lld%lld", &s.first, &s.second, &e.first, &e.second); findids(0, e, s, num1); findids(1, s, e, num2); for (int i = 1; i <= m; i++) { for (auto a : group[i]) { if (isbelow[a]) bg[i].push_back(a); else ag[i].push_back(a); } sort(bg[i].begin(), bg[i].end(), [](const int &a, const int &b) { return num1[a] < num1[b]; }); sort(ag[i].begin(), ag[i].end(), [](const int &a, const int &b) { return num1[a] < num1[b]; }); int r = 0; for (auto a : ag[i]) { root[a] = ++upto; update(num2[a], root[a], r); r = root[a]; } r = 0; for (auto a : bg[i]) { root[a] = ++upto; update(num2[a], root[a], r); r = root[a]; } } int q; scanf("%d", &q); for (int query = 0; query < q; query++) { int i, j; scanf("%d%d", &i, &j); ll ans = 0; for (auto a : group[i]) { D("checking %d\n", a); ll am = 0; if (isbelow[a]) { am += aminupper(bg[j], num1[a], num2[a]); am += aminlower(ag[j], num1[a], num2[a]); } else { am += aminupper(bg[j], num1[a], num2[a]); am += aminlower(ag[j], num1[a], num2[a]); } ans += am; } printf("%lld\n", ans); } }

Compilation message (stderr)

dragon2.cpp: In function 'int main()':
dragon2.cpp:106:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~
dragon2.cpp:109:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld%d", &x[i], &y[i], &g[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dragon2.cpp:112:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld%lld%lld", &s.first, &s.second, &e.first, &e.second);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dragon2.cpp:140:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
  ~~~~~^~~~~~~~~~
dragon2.cpp:144:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &i, &j);
   ~~~~~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...