oj.uz

답안 #208692

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
208692 2020-03-12T02:56:04 Z arnold518 Dragon 2 (JOI17_dragon2) C++14
0 / 100
 95 ms 22488 KB 
#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<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();
		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); });

		vector<pii> V;
		for(i=0; i<S; i++)
		{
			int x=VAT[i].second+1, y=VBT[i].second+1;
			//printf("!(%d %d) : %d %d\n", VAT[i].first.x, VAT[i].first.y, x, y);
			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 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;

		//printf("QUERYQUERYNK %d %d %d %d\n", xl, xr, yl, yr);

		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;

		//printf("!\n");

		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, yr, S);
				ret+=query(tree[xl-1], tree[xr], 1, S, 1, yl);
			}
		}
		else
		{
			if(yl<=yr)
			{
				ret+=query(tree[0], tree[xl], 1, S, yl, yr);
				ret+=query(tree[xr-1], tree[S], 1, S, yl, yr);
			}
			else
			{
				ret+=query(tree[0], tree[xl], 1, S, yr, S);
				ret+=query(tree[0], tree[xl], 1, S, 1, yl);
				ret+=query(tree[xr-1], tree[S], 1, S, yr, S);
				ret+=query(tree[xr-1], tree[S], 1, S, 1, yl);
			}
		}
		//printf("QUERY %d %d %d %d : %d\n", xl, xr, yl, yr, ret);
		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();
		//printf("-> %d\n", i);
	}

	scanf("%d", &Q);
	while(Q--)
	{
		int s, e;
		ll ans=0;
		scanf("%d%d", &s, &e);
		if(true)
		{
			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);
				//printf("%lld %lld / %lld %lld / %lld %lld / %lld %lld -> \n", pxl.x, pxl.y, pxr.x, pxr.y, pyl.x, pyl.y, pyr.x, pyr.y);
				int t=D[e].query(pxl, pxr, pyl, pyr);
				//printf("-> %d\n", t);
				ans+=t;
			}
		}
		printf("%lld\n", ans);
	}
}

Compilation message

dragon2.cpp: In function 'void makeTree(Node*, int, int)':
dragon2.cpp:33: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:87:10: warning: unused variable 'j' [-Wunused-variable]
   int i, j;
          ^
dragon2.cpp: In function 'int main()':
dragon2.cpp:164:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^
dragon2.cpp: In function 'bool cmpA(const Point&, const Point&)':
dragon2.cpp:46:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
dragon2.cpp: In function 'bool cmpB(const Point&, const Point&)':
dragon2.cpp:54:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
dragon2.cpp: In function 'int main()':
dragon2.cpp:166: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:170: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:173: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
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 13 ms 4984 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 95 ms 22488 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 13 ms 4984 KB Output isn't correct
2 Halted 0 ms 0 KB -