oj.uz

Submission #84372

# Submission time Handle Problem Language Result Execution time Memory
84372 2018-11-14T16:53:16 Z Bodo171 None (JOI16_matryoshka) C++14
0 / 100
 2 ms 440 KB 
#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;
}
struct AIB

{
    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;
    }
}cl,nu_exista;
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=cl.compute(cb(v[idx].h));
              poz=cl.find_kth(vv+1);
              cl.update(poz,-1);
              if(poz<=n)
              {
                 nu_exista.update(cb(v[idx].h),1);
                 nu_exista.update(poz,-1);
              }
            }
            for(idx=old;idx<=i;idx++)
                cl.update(cb(v[idx].h),1);
            i=old;
        }
        else
        {
            ans[v[i].tip]=cl.compute(cb(v[i].h))+nu_exista.compute(cb(v[i].h));
        }
    }
    for(i=1;i<=q;i++)
        cout<<ans[i]<<'\n';
    return 0;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 440 KB Output is correct
3 Incorrect 2 ms 440 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 440 KB Output is correct
3 Incorrect 2 ms 440 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 440 KB Output is correct
3 Incorrect 2 ms 440 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 440 KB Output is correct
3 Incorrect 2 ms 440 KB Output isn't correct
4 Halted 0 ms 0 KB -