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 瞎搞 , 591 阅读

题意:

给你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;
}
njmcdirect 说:
Aug 20, 2022 02:05:11 AM

The NJMCDirect online portal has eventually replaced the old queuing system. Whenever once violates the traffic or parking rules. The traffic officers provide a traffic ticket stating your offenses and fine to pay. These compel you to pay the fines within the stated time frame. Violators need to visit the court and queue for long hours. njmcdirect However, the New Jersey Meadowlands Commission (N.J.M.C.) has digitalized their traffic ticket system. They have implemented a new online portal, NJMCDirect. Here traffic law offenders can pay their fines online using their devices such as mobile phones, laptops, etc.


登录 *


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