Submission #210526

#	Time	Username	Problem	Language	Result	Execution time	Memory
210526		arnold518	Dragon 2 (JOI17_dragon2)	C++14	100 / 100	1439 ms	22920 KiB

dragon2

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 3e4;

struct Point { ll x, y; };
Point operator + (const Point &p, const Point &q) { return {p.x+q.x, p.y+q.y}; }
Point operator - (const Point &p, const Point &q) { return {p.x-q.x, p.y-q.y}; }

ll ccw(Point p, Point q) { return p.x*q.y-p.y*q.x; }
ll ccw(Point p, Point q1, Point q2) { return ccw(q1-p, q2-p); }

int N, M, Q;
vector<Point> P[MAXN+10];
Point A, B;
map<pii, ll> memo;

struct Node
{
	int val;
	Node *lc, *rc;
	Node() : val(0), lc(NULL), rc(NULL) {}
};

void makeTree(Node *node, int tl, int tr)
{
	if(tl==tr) return;
	int mid=tl+tr>>1;
	node->lc=new Node();
	node->rc=new Node();
	makeTree(node->lc, tl, mid);
	makeTree(node->rc, mid+1, tr);
}

bool cmpA(const Point &p, const Point &q)
{
	if((A.x<p.x || (A.x==p.x && A.y>p.y)) && (A.x<q.x || (A.x==q.x && A.y>q.y))) return ccw(A, p, q)>0;
	if((A.x>p.x || (A.x==p.x && A.y<p.y)) && (A.x>q.x || (A.x==q.x && A.y<q.y))) return ccw(A, p, q)>0;
	if((A.x<p.x || (A.x==p.x && A.y>p.y)) && (A.x>q.x || (A.x==q.x && A.y<q.y))) return true;
	if((A.x>p.x || (A.x==p.x && A.y<p.y)) && (A.x<q.x || (A.x==q.x && A.y>q.y))) return false;
}

bool cmpB(const Point &p, const Point &q)
{
	if((B.x<p.x || (B.x==p.x && B.y>p.y)) && (B.x<q.x || (B.x==q.x && B.y>q.y))) return ccw(B, p, q)>0;
	if((B.x>p.x || (B.x==p.x && B.y<p.y)) && (B.x>q.x || (B.x==q.x && B.y<q.y))) return ccw(B, p, q)>0;
	if((B.x<p.x || (B.x==p.x && B.y>p.y)) && (B.x>q.x || (B.x==q.x && B.y<q.y))) return true;
	if((B.x>p.x || (B.x==p.x && B.y<p.y)) && (B.x<q.x || (B.x==q.x && B.y>q.y))) return false;
}

struct Data
{
	int S;
	vector<Point> VA, VB;
	vector<pii> V;
	vector<Node*> tree;

	Node *addTree(Node *node, int tl, int tr, int pos)
	{
		if(pos<tl || tr<pos) return node;
		Node *ret=new Node();
		if(tl==tr)
		{
			ret->val=node->val+1;
			return ret;
		}
		int mid=tl+tr>>1;
		ret->lc=addTree(node->lc, tl, mid, pos);
		ret->rc=addTree(node->rc, mid+1, tr, pos);
		ret->val=(ret->lc->val)+(ret->rc->val);
		return ret;
	}

	int query(Node *nodel, Node *noder, int tl, int tr, int l, int r)
	{
		if(tr<l || r<tl) return 0;
		if(l<=tl && tr<=r) return (noder->val)-(nodel->val);
		int mid=tl+tr>>1;
		return query(nodel->lc, noder->lc, tl, mid, l, r)+query(nodel->rc, noder->rc, mid+1, tr, l, r);
	}

	void init()
	{
		int i, j;
		S=VA.size();
		if(S==0) return;
		sort(VA.begin(), VA.end(), cmpA);
		sort(VB.begin(), VB.end(), cmpB);

		vector<pair<Point, int>> VAT, VBT;
		for(i=0; i<S; i++) VAT.push_back({VA[i], i});
		for(i=0; i<S; i++) VBT.push_back({VB[i], i});
		sort(VAT.begin(), VAT.end(), [&](const pair<Point, int> &p, const pair<Point, int> &q) { return pll(p.first.x, p.first.y)<pll(q.first.x, q.first.y); });
		sort(VBT.begin(), VBT.end(), [&](const pair<Point, int> &p, const pair<Point, int> &q) { return pll(p.first.x, p.first.y)<pll(q.first.x, q.first.y); });

		for(i=0; i<S; i++)
		{
			int x=VAT[i].second+1, y=VBT[i].second+1;
			V.push_back({x, y});
		}
		sort(V.begin(), V.end());

		tree.push_back(new Node());
		makeTree(tree[0], 1, S);
		for(i=0; i<S; i++)
		{
			tree.push_back(addTree(tree.back(), 1, S, V[i].second));
		}
	}

	int query(Point pxl, Point pxr, Point pyl, Point pyr)
	{
		int i, j;
		if(S==0) return 0;
		int xl=(lower_bound(VA.begin(), VA.end(), pxl, cmpA)-VA.begin())%S+1;
		int xr=(upper_bound(VA.begin(), VA.end(), pxr, cmpA)-VA.begin()-1+S)%S+1;
		int yl=(lower_bound(VB.begin(), VB.end(), pyl, cmpB)-VB.begin())%S+1;
		int yr=(upper_bound(VB.begin(), VB.end(), pyr, cmpB)-VB.begin()-1+S)%S+1;

		if(!(ccw(A, pxl, VA[xl-1])>=0 && ccw(A, VA[xl-1], pxr)>=0)) return 0;
		if(!(ccw(A, pxl, VA[xr-1])>=0 && ccw(A, VA[xr-1], pxr)>=0)) return 0;
		if(!(ccw(B, pyl, VB[yl-1])>=0 && ccw(B, VB[yl-1], pyr)>=0)) return 0;
		if(!(ccw(B, pyl, VB[yr-1])>=0 && ccw(B, VB[yr-1], pyr)>=0)) return 0;

		int ret=0;

		if(xl<=xr)
		{
			if(yl<=yr)
			{
				ret+=query(tree[xl-1], tree[xr], 1, S, yl, yr);
			}
			else
			{
				ret+=query(tree[xl-1], tree[xr], 1, S, yl, S);
				ret+=query(tree[xl-1], tree[xr], 1, S, 1, yr);
			}
		}
		else
		{
			if(yl<=yr)
			{
				ret+=query(tree[0], tree[xr], 1, S, yl, yr);
				ret+=query(tree[xl-1], tree[S], 1, S, yl, yr);
			}
			else
			{
				ret+=query(tree[0], tree[xr], 1, S, yl, S);
				ret+=query(tree[0], tree[xr], 1, S, 1, yr);
				ret+=query(tree[xl-1], tree[S], 1, S, yl, S);
				ret+=query(tree[xl-1], tree[S], 1, S, 1, yr);
			}
		}
		return ret;
	}
};
Data D[MAXN+10];

int main()
{
	int i, j;

	scanf("%d%d", &N, &M);
	for(i=1; i<=N; i++)
	{
		int x, y, w;
		scanf("%d%d%d", &x, &y, &w);
		P[w].push_back({x, y});
	}
	scanf("%lld%lld%lld%lld", &A.x, &A.y, &B.x, &B.y);

	for(i=1; i<=M; i++)
	{
		for(auto it : P[i])
		{
			D[i].VA.push_back(it);
			D[i].VB.push_back(it);
		}
		D[i].init();
	}

	scanf("%d", &Q);
	while(Q--)
	{
		int s, e;
		ll ans=0;
		scanf("%d%d", &s, &e);
		if(P[s].size()<=P[e].size())
		{
			for(auto it : P[s])
			{
				Point pxl, pxr, pyl, pyr;
				pxl=it, pxr={2*A.x-it.x, 2*A.y-it.y};
				pyl=it, pyr={2*B.x-it.x, 2*B.y-it.y};
				if(ccw(A, it, B)<0) swap(pxl, pxr);
				if(ccw(B, it, A)<0) swap(pyl, pyr);
				ans+=D[e].query(pxl, pxr, pyl, pyr);
			}
		}
		else
		{
			for(auto it : P[e])
			{
				Point pxl, pxr, pyl, pyr;
				pxl=B, pxr={2*A.x-it.x, 2*A.y-it.y};
				pyl={2*B.x-it.x, 2*B.y-it.y}, pyr=A;
				if(ccw(A, pxl, pxr)<0) swap(pxl, pxr);
				if(ccw(B, pyl, pyr)<0) swap(pyl, pyr);
				ans+=D[s].query(pxl, pxr, pyl, pyr);

				pxl=it, pxr={2*A.x-it.x, 2*A.y-it.y};
				pyl=it, pyr={2*B.x-it.x, 2*B.y-it.y};
				if(ccw(A, it, B)>0) swap(pxl, pxr);
				if(ccw(B, it, A)>0) swap(pyl, pyr);
				ans+=D[s].query(pxl, pxr, pyl, pyr);
			}
		}
		printf("%lld\n", ans);
	}
}

Compilation message (stderr)

dragon2.cpp: In function 'void makeTree(Node*, int, int)':
dragon2.cpp:32:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=tl+tr>>1;
          ~~^~~
dragon2.cpp: In member function 'Node* Data::addTree(Node*, int, int, int)':
dragon2.cpp:71:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid=tl+tr>>1;
           ~~^~~
dragon2.cpp: In member function 'int Data::query(Node*, Node*, int, int, int, int)':
dragon2.cpp:82:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid=tl+tr>>1;
           ~~^~~
dragon2.cpp: In member function 'void Data::init()':
dragon2.cpp:88:10: warning: unused variable 'j' [-Wunused-variable]
   int i, j;
          ^
dragon2.cpp: In member function 'int Data::query(Point, Point, Point, Point)':
dragon2.cpp:117:7: warning: unused variable 'i' [-Wunused-variable]
   int i, j;
       ^
dragon2.cpp:117:10: warning: unused variable 'j' [-Wunused-variable]
   int i, j;
          ^
dragon2.cpp: In function 'int main()':
dragon2.cpp:165:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^
dragon2.cpp: In function 'bool cmpA(const Point&, const Point&)':
dragon2.cpp:45:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
dragon2.cpp: In function 'bool cmpB(const Point&, const Point&)':
dragon2.cpp:53:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
dragon2.cpp: In function 'int main()':
dragon2.cpp:167: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:171:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &x, &y, &w);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
dragon2.cpp:174:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld%lld%lld", &A.x, &A.y, &B.x, &B.y);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dragon2.cpp:186:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &Q);
  ~~~~~^~~~~~~~~~
dragon2.cpp:191:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &s, &e);
   ~~~~~^~~~~~~~~~~~~~~~

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