absi2011's Blog & Daily Life.

全新的开始       我要省选翻盘       I wanna AK in 高考\化学       自此,生无可恋
[破碎的状态] Codeforces Round #467 补题记录
[破碎的状态] 101630K

[破碎的状态] cf 101630A

absi2011 posted @ Feb 26, 2018 10:20:51 PM in 刷题记录 with tags 线段树 小高考 CF Gym 瞎搞 , 132 阅读

题意:

给你n个操作

1,放个靶子上去,保证靶子不重叠

2,丢个飞镖,如果扎中靶子,输出什么时候放的这个靶子;然后移除这个靶子

算法:

离散化

然后直接线段树维护vector(或者set)就过了...........

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<math.h>
#include<time.h>
#include<vector>
#include<bitset>
#include<memory>
#include<utility>
#include<fstream>
#include<stdio.h>
#include<sstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
int oper[200005],x[200005],y[200005];
int z[400005];
vector<int> v[1<<21];
void change(int num,int l,int r,int l0,int r0,int val,int k)
{
    if ((l0<=l)&&(r<=r0))
    {
        if (k==1)
        {
            v[num].push_back(val);
        }
        else
        {
            int i;
            for (i=0;i<v[num].size()-1;i++)
            {
                if (v[num][i]==val)
                {
                    swap(v[num][i],v[num][i+1]);
                }
            }
            v[num].pop_back();
        }
        return;
    }
    int mid=(l+r)/2;
    if (l0<mid) change(num*2+1,l,mid,l0,r0,val,k);
    if (mid<r0) change(num*2+2,mid,r,l0,r0,val,k);
}
inline bool in_circle(int a,int b)
{
    long long t=(long long)(x[a]-x[b])*(x[a]-x[b])+(long long)(y[a]-y[b])*(y[a]-y[b]);
    long long t2=(long long)y[a]*y[a];
    return t<t2;
}
int query(int num,int l,int r,int k,int id)
{
    int i;
    for (i=0;i<v[num].size();i++)
    {
        if (in_circle(v[num][i],id)) return v[num][i];
    }
    if (l==r-1)
    {
        return -1;
    }
    int mid=(l+r)/2;
    if (k<mid)
    {
        return query(num*2+1,l,mid,k,id);
    }
    else
    {
        return query(num*2+2,mid,r,k,id);
    }
}
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    int n;
    scanf("%d",&n);
    int i;
    int cnt=0;
    for (i=0;i<n;i++)
    {
        scanf("%d%d%d",&oper[i],&x[i],&y[i]);
        if (oper[i]==1)
        {
            z[cnt++]=x[i]-y[i]+1;
            z[cnt++]=x[i]+y[i]-1;
        }
        else
        {
            z[cnt++]=x[i];
        }
    }
    sort(z,z+cnt);
    cnt=unique(z,z+cnt)-z;
    for (i=0;i<n;i++)
    {
        if (oper[i]==1)
        {
            change(0,0,cnt,lower_bound(z,z+cnt,x[i]-y[i]+1)-z,lower_bound(z,z+cnt,x[i]+y[i]-1)-z+1,i,1);
        }
        else
        {
            int ans=query(0,0,cnt,lower_bound(z,z+cnt,x[i])-z,i);
            if (ans!=-1)
            {
                change(0,0,cnt,lower_bound(z,z+cnt,x[ans]-y[ans]+1)-z,lower_bound(z,z+cnt,x[ans]+y[ans]-1)-z+1,ans,-1);
            }
            if (ans>=0) ans++;
            printf("%d\n",ans);
        }
    }
    return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter