Submission #1219750

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219750		abczz	Dragon 2 (JOI17_dragon2)	C++20	60 / 100	1123 ms	327680 KiB

dragon2

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

using namespace std;

vector <array<ll, 4>> pt;
vector <int> G[30000], V;
vector <array<int, 3>> Z;
array<ll, 2> line[2];
array<int, 2> R[30000][2], X[30000][2];
int ord[30000][2];
ll F[100000];
ll n, m, q, x, a, b, c, l, r;
map <int, int> mp[30000];
vector <array<int, 6>> Q[60001];
ld angle(array<ll, 2> A, array<ll, 2> B) {
  return (ld)atan2(A[0] * B[1] - A[1] * B[0], A[0] * A[1] + B[0] * B[1]);
}
struct Node{
  int val, chl, chr;
};
Node st[2000000];
ll stsz = 0;
struct Perst_SegTree{
  vector <int> rt;
  int newNode() {
    st[stsz++] = {0, -1, -1};
    return stsz - 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;
    }
    int 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]}) > 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] = X[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]}) > 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]}) > 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]}) > 0) {
          R[pt[j][3]][i] = {j+1, l};
          //cout << "anticlockwise " << i << " " << pt[j][3] << " " << j+1 << " " << l << endl;
        }
        else continue;
        l = j+1, r = R[pt[j][3]][i][1];
        while (l < r) {
          ll mid = (l+r)/2;
          ll id = mid % (ll)pt.size();
          if (angle(array<ll, 2>{pt[id][0]-line[i][0], pt[id][1]-line[i][1]}, array<ll, 2>{line[i^1][0]-line[i][0], line[i^1][1]-line[i][1]}) > 0) l = mid+1;
          else r = mid;
        }
        id = l % (ll)pt.size();
        if (!(bool)(angle(array<ll, 2>{pt[id][0]-line[i][0], pt[id][1]-line[i][1]}, array<ll, 2>{line[i^1][0]-line[i][0], line[i^1][1]-line[i][1]}) > 0)) {
          X[pt[j][3]][i] = {l, R[pt[j][3]][i][1]};
        }
      }
      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]}) > 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]}) > 0) {
          R[pt[j][3]][i] = {l, j+(ll)pt.size()-1};
        }
        else continue;
        l = R[pt[j][3]][i][0], r = j+(ll)pt.size()-1;
        while (l < r) {
          ll mid = (l+r+1)/2;
          ll id = mid % (ll)pt.size();
          if (angle(array<ll, 2>{line[i^1][0]-line[i][0], line[i^1][1]-line[i][1]}, array<ll, 2>{pt[id][0]-line[i][0], pt[id][1]-line[i][1]}) > 0) r = mid-1;
          else l = mid;
        }
        id = l % (ll)pt.size();
        if (!(bool)(angle(array<ll, 2>{line[i^1][0]-line[i][0], line[i^1][1]-line[i][1]}, array<ll, 2>{pt[id][0]-line[i][0], pt[id][1]-line[i][1]}) > 0)) {
          X[pt[j][3]][i] = {R[pt[j][3]][i][0], l};
        }
      }
    }
  }
  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);
  }
  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});
        if (X[z][0][0] == -1 || X[z][1][0] == -1) continue;
        Q[X[z][0][1]+1].push_back({1, i, 1, a, X[z][1][0], X[z][1][1]});
        Q[X[z][0][0]].push_back({1, i, -1, a, X[z][1][0], X[z][1][1]});
      }
    }
    else {
      ++mp[a][b];
      Z.push_back({i, a, b});
    }
  }
  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) {
        if (!mp[u].count(v)) continue;
        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]});
      }
    }
  }
  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];
      }
    }
  }
  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];
      }
    }
  }
  for (auto u : Z) F[u[0]] = mp[u[1]][u[2]]-1;
  for (int i=0; i<q; ++i) cout << F[i] << '\n';
}

Compilation message (stderr)

dragon2.cpp: In function 'int main()':
dragon2.cpp:94:34: warning: narrowing conversion of 'l' from 'long long int' to 'int' [-Wnarrowing]
   94 |           R[pt[j][3]][i] = {j+1, l};
      |                                  ^
dragon2.cpp:107:29: warning: narrowing conversion of 'l' from 'long long int' to 'int' [-Wnarrowing]
  107 |           X[pt[j][3]][i] = {l, R[pt[j][3]][i][1]};
      |                             ^
dragon2.cpp:119:29: warning: narrowing conversion of 'l' from 'long long int' to 'int' [-Wnarrowing]
  119 |           R[pt[j][3]][i] = {l, j+(ll)pt.size()-1};
      |                             ^
dragon2.cpp:119:47: warning: narrowing conversion of '((((long long int)j) + ((long long int)pt.std::vector<std::array<long long int, 4> >::size())) - 1)' from 'long long int' to 'int' [-Wnarrowing]
  119 |           R[pt[j][3]][i] = {l, j+(ll)pt.size()-1};
      |                                ~~~~~~~~~~~~~~~^~
dragon2.cpp:131:48: warning: narrowing conversion of 'l' from 'long long int' to 'int' [-Wnarrowing]
  131 |           X[pt[j][3]][i] = {R[pt[j][3]][i][0], l};
      |                                                ^
dragon2.cpp:149:45: warning: narrowing conversion of 'b' from 'long long int' to 'int' [-Wnarrowing]
  149 |         Q[R[z][0][1]+1].push_back({1, i, 1, b, R[z][1][0], R[z][1][1]});
      |                                             ^
dragon2.cpp:150:44: warning: narrowing conversion of 'b' from 'long long int' to 'int' [-Wnarrowing]
  150 |         Q[R[z][0][0]].push_back({1, i, -1, b, R[z][1][0], R[z][1][1]});
      |                                            ^
dragon2.cpp:163:37: warning: narrowing conversion of 'a' from 'long long int' to 'int' [-Wnarrowing]
  163 |         Q[r1+1].push_back({1, i, 1, a, l2, r2});
      |                                     ^
dragon2.cpp:163:40: warning: narrowing conversion of 'l2' from 'long long int' to 'int' [-Wnarrowing]
  163 |         Q[r1+1].push_back({1, i, 1, a, l2, r2});
      |                                        ^~
dragon2.cpp:163:44: warning: narrowing conversion of 'r2' from 'long long int' to 'int' [-Wnarrowing]
  163 |         Q[r1+1].push_back({1, i, 1, a, l2, r2});
      |                                            ^~
dragon2.cpp:164:36: warning: narrowing conversion of 'a' from 'long long int' to 'int' [-Wnarrowing]
  164 |         Q[l1].push_back({1, i, -1, a, l2, r2});
      |                                    ^
dragon2.cpp:164:39: warning: narrowing conversion of 'l2' from 'long long int' to 'int' [-Wnarrowing]
  164 |         Q[l1].push_back({1, i, -1, a, l2, r2});
      |                                       ^~
dragon2.cpp:164:43: warning: narrowing conversion of 'r2' from 'long long int' to 'int' [-Wnarrowing]
  164 |         Q[l1].push_back({1, i, -1, a, l2, r2});
      |                                           ^~
dragon2.cpp:166:45: warning: narrowing conversion of 'a' from 'long long int' to 'int' [-Wnarrowing]
  166 |         Q[X[z][0][1]+1].push_back({1, i, 1, a, X[z][1][0], X[z][1][1]});
      |                                             ^
dragon2.cpp:167:44: warning: narrowing conversion of 'a' from 'long long int' to 'int' [-Wnarrowing]
  167 |         Q[X[z][0][0]].push_back({1, i, -1, a, X[z][1][0], X[z][1][1]});
      |                                            ^
dragon2.cpp:172:23: warning: narrowing conversion of 'a' from 'long long int' to 'int' [-Wnarrowing]
  172 |       Z.push_back({i, a, b});
      |                       ^
dragon2.cpp:172:26: warning: narrowing conversion of 'b' from 'long long int' to 'int' [-Wnarrowing]
  172 |       Z.push_back({i, a, b});
      |                          ^

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