Submission #84362

#	Time	Username	Problem	Language	Result	Execution time	Memory
84362		Bodo171	Matryoshka (JOI16_matryoshka)	C++14	0 / 100	2 ms	812 KiB

matryoshka

#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
const int nmax=200005;
struct ev
{
    int r,h;
    int tip;
}v[2*nmax];
int aib[nmax],ans[nmax],norm[nmax];
int n,q,i,j,vv,poz;
bool comp(ev unu,ev doi)
{
    if(unu.r==doi.r) return unu.tip>doi.tip;
    return unu.r<doi.r;
}
int cb(int x)
{
    int ret=0;
    for(int p=17;p>=0;p--)
        if(ret+(1<<p)<=n&&norm[ret+(1<<p)]<=x)
         ret+=(1<<p);
    return ret;
}
inline int lbit(int x)
{
    return ((x^(x-1))&x);
}
int compute(int poz)
{
    int ret=0;
    for(int idx=poz;idx>0;idx-=lbit(idx))
        ret+=aib[idx];
    return ret;
}
void update(int poz,int val)
{
    for(int idx=poz;idx<=n;idx+=lbit(idx))
        aib[idx]+=val;
}
int find_kth(int val)
{
    int ret=0,cat=0;
    for(int p=17;p>=0;p--)
        if(ret+(1<<p)<=n&&cat+aib[ret+(1<<p)]<val)
    {
        ret+=(1<<p);
        cat+=aib[ret];
    }
    ret++;
    return ret;
}
int main()
{
   // freopen("data.in","r",stdin);
    ios_base::sync_with_stdio(false);
    cin>>n>>q;
    for(i=1;i<=n;i++)
    {
        cin>>v[i].r>>v[i].h;
        norm[i]=v[i].h;
    }
    sort(norm+1,norm+n+1);
    for(i=1;i<=q;i++)
    {
        cin>>v[n+i].r>>v[n+i].h;
        v[n+i].tip=i;
    }
    sort(v+1,v+n+q+1,comp);
    for(i=n+q;i>=1;i--)
    {
        if(v[i].tip==0)
        {
            vv=compute(cb(v[i].h));
            poz=find_kth(vv+1);
            update(poz,-1);
            update(cb(v[i].h),1);
        }
        else
        {
            ans[v[i].tip]=compute(cb(v[i].h));
        }
    }
    for(i=1;i<=q;i++)
        cout<<ans[i]<<'\n';
    return 0;
}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 15
• Subtask 3: 0 / 25
• Subtask 4: 0 / 49