제출 #1219325

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1219325		abczz	Dragon 2 (JOI17_dragon2)	C++20	0 / 100	217 ms	29308 KiB

dragon2

#include <iostream>
#include <vector>
#include <array>
#include <algorithm>
#include <cmath>
#include <map>
#define ll int
#define ld long double

using namespace std;

vector <array<ll, 4>> pt;
vector <ll> G[30000], V;
vector <array<ll, 3>> Z;
array<ll, 2> line[2];
array<ll, 2> R[30000][2];
ll ord[30000][2], F[30000];
ll n, m, q, x, a, b, c, l, r;
ld eps = 0, pi = 3.1415926535;
map <ll, ll> mp[30000];
vector <array<ll, 6>> Q[60001];
ld angle(array<ll, 2> A, array<ll, 2> B) {
  ld cross = A[0] * B[1] - A[1] * B[0], dot = A[0] * A[1] + B[0] * B[1];
  return (ld)atan2(cross, dot);
}
struct Perst_SegTree{
  vector <ll> rt;
  struct Node{
    ll val = 0, chl = -1, chr = -1;
  };
  vector <Node> st;
  ll newNode() {
    st.push_back({0, -1, -1});
    return (ll)st.size() - 1;
  }
  void push_up(ll id) {
    st[id].val = (st[id].chl == -1 ? 0 : st[st[id].chl].val) + (st[id].chr == -1 ? 0 : st[st[id].chr].val);
  }
  void update(ll id, ll nid, ll l, ll r, ll q) {
    if (l == r) {
      st[nid].val = (id == -1 ? 0 : st[id].val) + 1;
      return;
    }
    ll mid = (l+r)/2;
    if (q <= mid) {
      if (st[nid].chl == -1) st[nid].chl = newNode();
      if (st[nid].chr == -1) st[nid].chr = (id == -1 ? -1 : st[id].chr);
      update(id == -1 ? -1 : st[id].chl, st[nid].chl, l, mid, q);
    }
    else {
      if (st[nid].chr == -1) st[nid].chr = newNode();
      if (st[nid].chl == -1) st[nid].chl = (id == -1 ? -1 : st[id].chl);
      update(id == -1 ? -1 : st[id].chr, st[nid].chr, mid+1, r, q);
    }
    push_up(nid);
  }
  ll query(ll id, ll l, ll r, ll ql, ll qr) {
    if (id == -1 || qr < l || r < ql) return 0;
    else if (ql <= l && r <= qr) return st[id].val;
    ll mid = (l+r)/2;
    return query(st[id].chl, l, mid, ql, qr) + query(st[id].chr, mid+1, r, ql, qr);
  }
}PST[30000];
int main() {
  cin.tie(0);
  ios::sync_with_stdio(0);
  cin >> n >> m;
  x = sqrt(n);
  for (int i=0; i<n; ++i) {
    cin >> a >> b >> c;
    --c;
    pt.push_back({a, b, c, i});
    G[c].push_back(i);
  }
  for (int i=0; i<2; ++i) cin >> line[i][0] >> line[i][1];
  for (int i=0; i<2; ++i) {
    sort(pt.begin(), pt.end(), [&i](auto a, auto b) {
      return angle(array<ll, 2>{a[0]-line[i][0], a[1]-line[i][1]}, array<ll, 2>{b[0]-line[i][0], b[1]-line[i][1]})-eps > 0;
    });
    for (int j=0; j<pt.size(); ++j) {
      //cout << pt[j][0] << " " << pt[j][1] << endl;
      ord[pt[j][3]][i] = j;
      R[pt[j][3]][i] = {-1, -1};
      l = j+1, r = j+(ll)pt.size()-1;
      if (angle(array<ll, 2>{pt[j][0]-line[i][0], pt[j][1]-line[i][1]}, array<ll, 2>{line[i^1][0]-line[i][0], line[i^1][1]-line[i][1]})-eps > 0) {
        while (l < r) {
          ll mid = (l+r+1)/2;
          ll id = mid % (ll)pt.size();
          if (angle(array<ll, 2>{pt[j][0]-line[i][0], pt[j][1]-line[i][1]}, array<ll, 2>{pt[id][0]-line[i][0], pt[id][1]-line[i][1]})-eps > 0) l = mid;
          else r = mid-1;
        }
        ll id = l % (ll)pt.size();
        if (angle(array<ll, 2>{pt[j][0]-line[i][0], pt[j][1]-line[i][1]}, array<ll, 2>{pt[id][0]-line[i][0], pt[id][1]-line[i][1]})-eps > 0) {
          R[pt[j][3]][i] = {j+1, l};
          //cout << "anticlockwise " << i << " " << pt[j][3] << " " << j+1 << " " << l << endl;
        }
      }
      else {
        while (l < r) {
          ll mid = (l+r)/2;
          ll id = mid % (ll)pt.size();
          if (angle(array<ll, 2>{pt[j][0]-line[i][0], pt[j][1]-line[i][1]}, array<ll, 2>{pt[id][0]-line[i][0], pt[id][1]-line[i][1]})-eps > 0) l = mid+1;
          else r = mid;
        }
        ll id = l % (ll)pt.size();
        if (angle(array<ll, 2>{pt[id][0]-line[i][0], pt[id][1]-line[i][1]}, array<ll, 2>{pt[j][0]-line[i][0], pt[j][1]-line[i][1]})-eps > 0) {
          R[pt[j][3]][i] = {l, j+(ll)pt.size()-1};
          //cout << "clockwise " << i << " " << pt[j][3] << " " << l << " " << j+(ll)pt.size()-1 << endl;
        }
      }
    }
  }
  sort(pt.begin(), pt.end(), [](auto a, auto b) {
    return ord[a[3]][0] < ord[b[3]][0];
  });
  for (int i=0; i<m; ++i) {
    if (G[i].size() > x) V.push_back(i);
  }
  for (auto u : V) {
    for (auto z : G[u]) {
      if (R[z][0][0] == -1 || R[z][1][0] == -1) continue;
      for (auto v : V) {
        Q[R[z][0][1]+1].push_back({0, u, 1, v, R[z][1][0], R[z][1][1]});
        Q[R[z][0][0]].push_back({0, u, -1, v, R[z][1][0], R[z][1][1]});
      }
    }
  }
  cin >> q;
  for (int i=0; i<q; ++i) {
    cin >> a >> b;
    --a, --b;
    if (G[a].size() <= x) {
      for (auto z : G[a]) {
        if (R[z][0][0] == -1 || R[z][1][0] == -1) continue;
        Q[R[z][0][1]+1].push_back({1, i, 1, b, R[z][1][0], R[z][1][1]});
        Q[R[z][0][0]].push_back({1, i, -1, b, R[z][1][0], R[z][1][1]});
      }
    }
    else if (G[b].size() <= x) {
      for (auto z : G[b]) {
        if (R[z][0][1]-R[z][0][0]+1 == n-1) continue;
        ll l1, r1, l2, r2;
        if (R[z][0][0] == -1) l1 = ord[z][0]+1, r1 = ord[z][0]+n-1;
        else l1 = (R[z][0][1]+1) % n, r1 = (R[z][0][0]+n-1) % n;
        if (R[z][1][0] == -1) l2 = ord[z][1]+1, r2 = ord[z][1]+n-1;
        else l2 = (R[z][1][1]+1) % n, r2 = (R[z][1][0]+n-1) % n;
        if (l1 > r1) r1 += n;
        if (l2 > r2) r2 += n;
        Q[r1+1].push_back({1, i, 1, a, l2, r2});
        Q[l1].push_back({1, i, -1, a, l2, r2});
      }
    }
    else Z.push_back({i, a, b});
  }
  for (int i=0; i<m; ++i) PST[i].rt.push_back(PST[i].newNode());
  int k = 0;
  for (auto u : pt) {
    auto nrt = PST[u[2]].newNode();
    PST[u[2]].update(PST[u[2]].rt.back(), nrt, 0, 2*n-1, ord[u[3]][1]);
    PST[u[2]].update(PST[u[2]].rt.back(), nrt, 0, 2*n-1, ord[u[3]][1]+n);
    PST[u[2]].rt.push_back(nrt);
    ++k;
    for (auto q : Q[k]) {
      if (q[0] == 0) mp[q[1]][q[3]] += PST[q[3]].query(PST[q[3]].rt.back(), 0, 2*n-1, q[4], q[5]) * q[2];
      else {
        F[q[1]] += PST[q[3]].query(PST[q[3]].rt.back(), 0, 2*n-1, q[4], q[5]) * q[2];
        //cout << k << " " << q[2] << " " << q[1] << " " << q[3] << " " << q[4] << " " << q[5] << " " << PST[q[3]].query(PST[q[3]].rt.back(), 0, 2*n-1, q[4], q[5]) << endl;
      }
    }
  }
  for (auto u : pt) {
    auto nrt = PST[u[2]].newNode();
    PST[u[2]].update(PST[u[2]].rt.back(), nrt, 0, 2*n-1, ord[u[3]][1]);
    PST[u[2]].update(PST[u[2]].rt.back(), nrt, 0, 2*n-1, ord[u[3]][1]+n);
    PST[u[2]].rt.push_back(nrt);
    ++k;
    for (auto q : Q[k]) {
      if (q[0] == 0) mp[q[1]][q[3]] += PST[q[3]].query(PST[q[3]].rt.back(), 0, 2*n-1, q[4], q[5]) * q[2];
      else {
        F[q[1]] += PST[q[3]].query(PST[q[3]].rt.back(), 0, 2*n-1, q[4], q[5]) * q[2];
        //cout << k << " " << q[2] << " " << q[1] << " " << q[3] << " " << q[4] << " " << q[5] << " " << PST[q[3]].query(PST[q[3]].rt.back(), 0, 2*n-1, q[4], q[5]) << endl;
      }
    }
  }
  for (auto u : Z) F[u[0]] = mp[u[1]][u[2]];
  for (int i=0; i<q; ++i) cout << F[i] << '\n';
}

• Subtask 1: 0 / 15
• Subtask 2: 0 / 45
• Subtask 3: 0 / 40