oj.uz

Submission #84363

# Submission time Handle Problem Language Result Execution time Memory
84363 2018-11-14T14:47:33 Z Bodo171 None (JOI16_matryoshka) C++14
0 / 100
 2 ms 672 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 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.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 452 KB Output is correct
3 Correct 2 ms 452 KB Output is correct
4 Correct 2 ms 492 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 2 ms 672 KB Output is correct
7 Correct 2 ms 672 KB Output is correct
8 Correct 2 ms 672 KB Output is correct
9 Correct 2 ms 672 KB Output is correct
10 Incorrect 2 ms 672 KB Output isn't correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 452 KB Output is correct
3 Correct 2 ms 452 KB Output is correct
4 Correct 2 ms 492 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 2 ms 672 KB Output is correct
7 Correct 2 ms 672 KB Output is correct
8 Correct 2 ms 672 KB Output is correct
9 Correct 2 ms 672 KB Output is correct
10 Incorrect 2 ms 672 KB Output isn't correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 452 KB Output is correct
3 Correct 2 ms 452 KB Output is correct
4 Correct 2 ms 492 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 2 ms 672 KB Output is correct
7 Correct 2 ms 672 KB Output is correct
8 Correct 2 ms 672 KB Output is correct
9 Correct 2 ms 672 KB Output is correct
10 Incorrect 2 ms 672 KB Output isn't correct

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 452 KB Output is correct
3 Correct 2 ms 452 KB Output is correct
4 Correct 2 ms 492 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 2 ms 672 KB Output is correct
7 Correct 2 ms 672 KB Output is correct
8 Correct 2 ms 672 KB Output is correct
9 Correct 2 ms 672 KB Output is correct
10 Incorrect 2 ms 672 KB Output isn't correct