Submission #84373

#	Time	Username	Problem	Language	Result	Execution time	Memory
84373		Bodo171	Matryoshka (JOI16_matryoshka)	C++14	100 / 100	479 ms	89576 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 ans[nmax],norm[nmax];
int n,q,i,j,vv,poz,idx,old;
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;
}  int aib[nmax];
    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);v[0].tip=-1;
    for(i=n+q;i>=1;i--)
    {
        if(v[i].tip==0)
        {
            idx=i;
            while(v[idx].tip==v[i].tip&&v[idx].r==v[i].r)
                idx--;
            idx++;old=idx;
            for(idx=old;idx<=i;idx++)
            {
              vv=compute(cb(v[idx].h));
              poz=find_kth(vv+1);
              update(poz,-1);
            }
            for(idx=old;idx<=i;idx++)
                update(cb(v[idx].h),1);
            i=old;
        }
        else
        {
            ans[v[i].tip]=compute(cb(v[i].h));
        }
    }
    for(i=1;i<=q;i++)
        cout<<ans[i]<<'\n';
    return 0;
}

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