列表

详情

NC54379. Archery Tournament

描述

You were invited to the annual archery tournament. You are going to compete against the best archers from all of the Northern Eurasia. This year, a new type of competition is introduced, where a shooting range is dynamic and new targets might appear at any second.
As the shooting range is far enough from you, it can be represented as a 2D plane, where y = 0 is the ground level. There are some targets in a shape of a circle, and all the targets are standing on the ground. That means, if a target’s center is (x, y) (y > 0), then its radius is equal to y, so that it touches the line y = 0. No two targets simultaneously present at the range at any given time intersect (but they may touch).
Initially, the shooting range is empty. Your participation in this competition can be described as n events: either a new target appears at the range, or you shoot an arrow at some point at the range. To hit a target, you must shoot strictly inside the circle (hitting the border does not count). If you shoot and hit some target, then the target is removed from the range and you are awarded one point.

输入描述

The first line of the input contains integer n (1 ≤ n ≤ 2·105). Next n lines describe the events happening at the tournament. The i-th line contains three integers ti, xi, and yi (ti = 1, 2; −109 ≤ xi, yi ≤ 109; yi > 0).
• If ti = 1, then a new target with center (xi, yi) and radius yi appears at the range.
• If ti = 2, then you perform a shot, which hits the range at (xi, yi).

输出描述

For each of your shots, output a separate line with the single integer. If the shot did not hit any target, print “-1”. If the shot hit a target, print the number of event when that target was added to the range. Events are numbered starting from 1.

示例1

输入: 

8
1 0 12
2 -11 22
1 24 10
1 12 3
2 12 12
2 16 14
1 28 15
2 3 6

输出: 

-1
-1
3
1

说明:

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++14(g++5.4) 解法, 执行用时: 499ms, 内存消耗: 158456K, 提交时间: 2020-10-06 16:59:55 

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

int tot;
vector<int> v[200005*20];
int ls[200005*20],rs[200005*20];
int x[200005],y[200005];
int ans;

int check(int x1,int y1,int x2,int y2)
{
    if(1ll*(x1-x2)*(x1-x2)+1ll*(y1-y2)*(y1-y2)<1ll*y1*y1) return 1;
    return 0;
}

void insert(int &now,int l,int r,int L,int R,int id)
{
    if(!now) 
    now=++tot;
    if(L<=l&&R>=r)
    {
        v[now].push_back(id);
        return ;
    }
    int mid=(l+r)>>1;
    if(L<=mid) insert(ls[now],l,mid,L,R,id);
    if(R>mid) insert(rs[now],mid+1,r,L,R,id);
}

void ask(int now,int l,int r,int xx,int yy)
{
    if(!now) return ;
    for(int i=0;i<v[now].size();i++)
        if(check(x[v[now][i]],y[v[now][i]],xx,yy))
        {
            ans=v[now][i];
            return ;
        }
    if(l==r) return ;
    int mid=(l+r)>>1;
    if(xx<=mid) ask(ls[now],l,mid,xx,yy);
    else ask(rs[now],mid+1,r,xx,yy);
}

void del(int now,int l,int r,int L,int R)
{
    if(L<=l&&R>=r)
    {
        vector<int> y;
        for(int i=0;i<v[now].size();i++)
            if(v[now][i]!=ans) y.push_back(v[now][i]);
        v[now]=y;
        return ;
    }
    int mid=(l+r)>>1;
    if(L<=mid) del(ls[now],l,mid,L,R);
    if(R>mid) del(rs[now],mid+1,r,L,R);
}

int main()
{
    int n;
    scanf("%d",&n);
    int rt=0;
    tot=0;
    for(int i=1;i<=n;i++){
        int t,xx,yy;
        scanf("%d%d%d",&t,&xx,&yy);
        if(t==1)
            x[i]=xx,y[i]=yy,insert(rt,-1e9,1e9,xx-yy,xx+yy,i);
        else
        {
            ans=-1;
            ask(rt,-1e9,1e9,xx,yy);
            printf("%d\n",ans );
            if(ans!=-1) del(rt,-1e9,1e9,x[ans]-y[ans],x[ans]+y[ans]);
        }
    }
}

C++(clang++11) 解法, 执行用时: 552ms, 内存消耗: 210000K, 提交时间: 2020-10-27 20:29:51 

#include<bits/stdc++.h>

#define ll long long

using namespace std;

const int N=2e5+10;
const int inf=1e9;

int n,cnt,rt,ans;
ll lx[N],ly[N];
int lc[N*30],rc[N*30];
vector<int>s[N*30];

inline void add(int &rt,int l,int r,int id,int x,int y)
{
	if(!rt) rt=++cnt;

	if(l>=x&&r<=y)
	{
		s[rt].push_back(id);
		return ;
	}

	int mid=(l+r)>>1;
	if(x<=mid) add(lc[rt],l,mid,id,x,y);
	if(mid<y) add(rc[rt],mid+1,r,id,x,y);
}

inline void upd(int rt,int l,int r,ll x,ll y)
{
	if(l>=x&&r<=y)
	{
		vector<int>tmp;int len=s[rt].size();
		for (int i=0;i<len;i++)
			if(s[rt][i]!=ans) tmp.push_back(s[rt][i]);
		s[rt]=tmp;
		return ;
	}
	
	int mid=(l+r)>>1;
	if(x<=mid) upd(lc[rt],l,mid,x,y);
	if(mid<y) upd(rc[rt],mid+1,r,x,y);
}

inline bool check(ll u,ll v,ll x,ll y)
{
	if((x-u)*(x-u)+(y-v)*(y-v)<v*v) return 1;
	return 0;
}

inline void find(int rt,int l,int r,ll x,ll y)
{
	if(!rt) return ;

	int len=s[rt].size();
	for (int i=0;i<len;i++)
		if(check(lx[s[rt][i]],ly[s[rt][i]],x,y))
			{ans=s[rt][i];break;}
	
	int mid=(l+r)>>1;
	if(x<=mid) find(lc[rt],l,mid,x,y);
	else find(rc[rt],mid+1,r,x,y);
}

int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
	{
		int id;ll x,y;
		scanf("%d%lld%lld",&id,&x,&y);
		if(id==1)
		{
			lx[i]=x;ly[i]=y;
			add(rt,-inf,inf,i,x-y,x+y);
		}
		else
		{
			ans=-1;
			find(rt,-inf,inf,x,y);
			//抽象为单点查询
			printf("%d\n",ans);
			
			if(ans!=-1)
				upd(rt,-inf,inf,lx[ans]-ly[ans],lx[ans]+ly[ans]);
		}
	}
	
	return 0;
}

上一题

© 2025 nowcoder.com