제출 #1270521

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1270521		repmann	Dragon 2 (JOI17_dragon2)	C++20	60 / 100	4097 ms	186352 KiB

dragon2

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int N, M, Q;
struct Point
{
  int x, y, m, i;
}P[60001], A, B;
bitset <30001> D[30001], T[30001];
vector <int> V[30001];
inline int Orientation(ll x1, ll y1, ll x2, ll y2, ll x, ll y)
{
  ll temp = (x - x1) * (y2 - y1) - (y - y1) * (x2 - x1);
  if(temp > 0) return +1;
  if(temp < 0) return -1;
  return 0;
}
inline bool cmp(const Point &a, const Point &b)
{
  int qa, qb;
  if(a.y > A.y) qa = 2 - (a.x > A.x);
  else qa = 3 + (a.x > A.x);
  if(b.y > A.y) qb = 2 - (b.x > A.x);
  else qb = 3 + (b.x > A.x);
  if(qa != qb) return qa < qb;
  return Orientation(A.x, A.y, a.x, a.y, b.x, b.y) < 0;
}
int main()
{
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> N >> M;
  for(int i = 1; i <= N; i++)
  {
    cin >> P[i].x >> P[i].y >> P[i].m;
    P[i].i = i;
    T[P[i].m][i] = 1;
    V[P[i].m].push_back(i);
  }
  cin >> A.x >> A.y >> B.x >> B.y;
  sort(P + 1, P + N + 1, cmp);
//  cout << "A sort:\n";
//  for(int i = 1; i <= N; i++) cout << P[i].x << ' ' << P[i].y << '\n';
  for(int i = 1; i <= N; i++) P[i + N] = P[i];
  bitset <30001> mask;
//  cout << "A pointers:\n";
  for(int i = 1, j = 2; i <= N; i++)
  {
    mask[P[i].i] = 0;
    while((j < (i + N)) && (Orientation(A.x, A.y, P[i].x, P[i].y, P[j].x, P[j].y) <= 0))
    {
      mask[P[j].i] = 1;
      j++;
    }
//    cout << i << ' ' << j << '\n';
//    for(int k = 1; k <= N; k++) cout << mask[k];
//    cout << '\n';
//    cout << Orientation(A.x, A.y, B.x, B.y, P[i].x, P[i].y) << '\n';
    if(Orientation(A.x, A.y, B.x, B.y, P[i].x, P[i].y) < 0) D[P[i].i] = ~mask;
    else D[P[i].i] = mask;
  }
  swap(A, B);
  sort(P + 1, P + N + 1, cmp);
  swap(A, B);
//  cout << "B sort:\n";
//  for(int i = 1; i <= N; i++) cout << P[i].x << ' ' << P[i].y << '\n';
  for(int i = 1; i <= N; i++) P[i + N] = P[i];
  mask = bitset<30001>(0);
//  cout << "B pointers:\n";
  for(int i = 1, j = 2; i <= N; i++)
  {
    mask[P[i].i] = 0;
    while((j < (i + N)) && (Orientation(B.x, B.y, P[i].x, P[i].y, P[j].x, P[j].y) <= 0))
    {
      mask[P[j].i] = 1;
      j++;
    }
//    cout << i << ' ' << j << '\n';
//    for(int k = 1; k <= N; k++) cout << mask[k];
//    cout << '\n';
//    cout << Orientation(A.x, A.y, B.x, B.y, P[i].x, P[i].y) << '\n';
    if(Orientation(A.x, A.y, B.x, B.y, P[i].x, P[i].y) > 0) D[P[i].i] &= ~mask;
    else D[P[i].i] &= mask;
  }
//  for(int i = 1; i <= N; i++)
//  {
//    for(int k = 1; k <= N; k++) cout << D[i][k];
//    cout << '\n';
//  }
  int a, b;
  cin >> Q;
  while(Q--)
  {
    cin >> a >> b;
    ll sol = 0;
    for(int x : V[a]) sol += (D[x] & T[b]).count();
    cout << sol << '\n';
  }

  return 0;
}

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