Submission #779675

#	Time	Username	Problem	Language	Result	Execution time	Memory
779675		myrcella	Dragon 2 (JOI17_dragon2)	C++17	0 / 100	28 ms	10748 KiB

dragon2

// by szh
#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef double DD;

#define int LL
#define F first
#define S second
#define pii pair<LL, LL>
#define pb push_back
#define debug(x) cerr << #x << "=" << x << endl
#define pq priority_queue
#define inf 0x3f
#define rep(i,a,b) for (int i=a; i < (b); i++)
#define MP make_pair
#define SZ(x) (static_cast<int>(x.size()))
#define MOD 1000000007
#define ALL(x) x.begin(), x.end()
void inc(int &a, int b) {a = (a+b)%MOD;}
void dec(int &a, int b) {a = (a-b+MOD)%MOD;}
int prod(int a,int b) {return LL(a)*LL(b)%MOD;}
int lowbit(int x) {return x&(-x);}

const int maxn = 1e5 + 10;
const DD EPS = 1e-9;

struct dragon{
  int t;
  int x, y;
  int id;
} da[maxn];

int xa, xb, ya, yb;
vector <pii> q[maxn];
int _;

int quadb(int x, int y) {
  if (x >= 0 and y > 0) return 3;
  if (x > 0 and y <= 0) return 0;
  if (x <= 0 and y < 0) return 1;
  assert(x < 0 and y >= 0);
  return 2;
}

int quada(int x, int y) {
  return (quadb(x, y) + 2) % 4;
}

bool cmp1(dragon a, dragon b) {
  a.x -= xa; a.y -= ya;
  b.x -= xa; b.y -= ya;
  if (quada(a.x, a.y) != quada(b.x, b.y)) return quada(a.x, a.y) < quada(b.x, b.y);
  else return a.y * b.x > b.y * a.x;
}

bool cmp2(dragon a, dragon b) {
  if (a.t != b.t) return a.t < b.t;
  a.x -= xb; a.y -= yb;
  b.x -= xb; b.y -= yb;
  if (quadb(a.x, a.y) != quadb(b.x, b.y)) return quadb(a.x, a.y) < quadb(b.x, b.y);
  else return a.y * b.x > b.y * a.x;
}

vector <int> tree[maxn];
vector <pii> db[maxn];

int n, m;

void update(int x, int pos, int val) {
  //if (val == 1) debug(x), debug(pos);
  while (pos < SZ(tree[x])) {
	tree[x][pos] += val;
	pos += lowbit(pos);
  }
  return;
}

int query(int x, int pos) {
  int ret = 0;
  while (pos) {
	ret += tree[x][pos];
	pos -= lowbit(pos);
  }
  return ret;
}

int ans[maxn];

signed main() {
  std::ios::sync_with_stdio(false); cin.tie(0);
  cin >> n >> m;
  rep(i, 0, n) {
	cin >> da[i].x >> da[i].y >> da[i].t;
  }
  cin >> xa >> ya >> xb >> yb;
  if (xa > xb) swap(xa, xb), swap(ya, yb);
  sort(da, da + n, cmp2);
  int cur = 0;
  while (cur < n) {
	int tmp = cur;
	while (cur < n and da[cur].t == da[tmp].t) cur++;
	tree[da[tmp].t].pb(0);
	db[da[tmp].t].pb({0, 0});
	rep(i, tmp, cur) {
	  da[i].id = i - tmp + 1;
	  tree[da[i].t].pb(0);
	  db[da[i].t].pb({da[i].x, da[i].y});
    }
  }
  sort(da, da + n, cmp1);
  rep(i, 0, n) da[i + n] = da[i];
  cin >> _;
  rep(i, 0, _) {
	int x, y;
	cin >> x >> y;
	q[x].pb({y, i});
  }
  cur = 0;
  bool flag = false;
  rep(i, 0, n) {
	int x1 = da[i].x - xa, y1 = da[i].y - ya, q1 = quada(x1, y1);
	//debug(x1), debug(y1);
	int x2 = -x1, y2 = -y1, q2 = (q1 + 2) % 4;
	if (y1 <= 0 and flag == false) {
	  rep(j, i, cur) update(da[j].t, da[j].id, -1);
	  rep(j, 0, i) update(da[j].t, da[j].id, 1);
	  cur = 0;
	  flag = true;
    }
	if (q1 > q2) swap(x1, x2), swap(y1, y2), swap(q1, q2);
    if (flag == false) {
	  if (cur > i) update(da[i].t, da[i].id, -1);
	  else cur = i + 1;
	  while (cur < n) {
	    int xx = da[cur].x - xa, yy = da[cur].y - ya, qq = quada(xx, yy);
	    if (qq > q2 or qq < q1 or (qq == q1 and y1 * xx < yy * x1) or (qq == q2 and y2 * xx > yy * x2)) break;
	    //debug(xx), debug(yy);
	    update(da[cur].t, da[cur].id, 1);
	    cur++;
      }
    } else {
	  update(da[i].t, da[i].id, 1);
	  while (cur < i) {
		int xx = da[cur].x - xa, yy = da[cur].y - ya, qq = quada(xx, yy);
	    if (qq > q2 or qq < q1 or (qq == q1 and y1 * xx < yy * x1) or (qq == q2 and y2 * xx > yy * x2)) {
		  //debug(xx), debug(yy);
	      update(da[cur].t, da[cur].id, -1);
	      cur++;
	    }
	    else break;
	  }
	}
	for (auto itt : q[da[i].t]) {
	  int it = itt.F;
      int xx = da[i].x - xb, yy = da[i].y - yb;
      int q = quadb(xx, yy);
      if (q == 0 or q == 1) xx *= -1, yy *= -1, q = (q + 2) % 4;
	  int L, R;
	  int lo = 0, hi = SZ(db[it]);
	  //debug(q), debug(xx), debug(yy);
	  while (lo < hi) {
		int mid = lo + hi + 1 >> 1;
		//cout << lo << " " << hi << " " << mid << endl;
		if (mid == 0) lo = mid;
		else if (mid == SZ(db[it])) hi = mid - 1;
		else {
		  int xxx = db[it][mid].F, yyy = db[it][mid].S;
		  xxx -= xb, yyy -= yb;
		  //if (mid == 2) debug(xxx), debug(yyy), debug(it);
		  int qqq = quadb(xxx, yyy);
		  if (qqq > q or (qqq == q and yyy * xx < yy * xxx)) hi = mid - 1;
		  else lo = mid;
	    }
	  }
	  R = lo;
	  lo = 0, hi = SZ(db[it]);
	  q += 2, q %= 4;
	  xx *= -1, yy *= -1;
	  while (lo < hi) {
		int mid = lo + hi >> 1;
		if (mid == 0) lo = mid + 1;
		else if (mid == SZ(db[it])) hi = mid;
		else {
		  int xxx = db[it][mid].F, yyy = db[it][mid].S;
		  xxx -= xb, yyy -= yb;
		  int qqq = quadb(xxx, yyy);
		  if (qqq < q or (qqq == q and yyy * xx > yy * xxx)) lo = mid + 1;
		  else hi = mid;
	    }
	  }
	  L = lo;
	  //debug(L), debug(R);
	  //cout << ans[itt.S] << " ";
	  if (L <= R) ans[itt.S] += query(it, R) - query(it, L - 1);
	  //debug(ans[itt.S]);
	}
  }
  rep(i, 0, _) cout << ans[i] << "\n";
  return 0;
}

Compilation message (stderr)

dragon2.cpp: In function 'int main()':
dragon2.cpp:164:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  164 |   int mid = lo + hi + 1 >> 1;
      |             ~~~~~~~~^~~
dragon2.cpp:182:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  182 |   int mid = lo + hi >> 1;
      |             ~~~^~~~

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