답안 #84373 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
84373	2018-11-14T16:58:49 Z	Bodo171	Matryoshka (JOI16_matryoshka)	C++14	100 / 100	479 ms	89576 KB

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.0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	380 KB	Output is correct
3	Correct	2 ms	456 KB	Output is correct
4	Correct	2 ms	628 KB	Output is correct
5	Correct	2 ms	628 KB	Output is correct
6	Correct	2 ms	628 KB	Output is correct
7	Correct	2 ms	628 KB	Output is correct
8	Correct	2 ms	628 KB	Output is correct
9	Correct	2 ms	628 KB	Output is correct
10	Correct	2 ms	628 KB	Output is correct

Subtask #2
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	380 KB	Output is correct
3	Correct	2 ms	456 KB	Output is correct
4	Correct	2 ms	628 KB	Output is correct
5	Correct	2 ms	628 KB	Output is correct
6	Correct	2 ms	628 KB	Output is correct
7	Correct	2 ms	628 KB	Output is correct
8	Correct	2 ms	628 KB	Output is correct
9	Correct	2 ms	628 KB	Output is correct
10	Correct	2 ms	628 KB	Output is correct
11	Correct	2 ms	628 KB	Output is correct
12	Correct	2 ms	628 KB	Output is correct
13	Correct	2 ms	664 KB	Output is correct
14	Correct	2 ms	796 KB	Output is correct
15	Correct	2 ms	796 KB	Output is correct
16	Correct	2 ms	820 KB	Output is correct
17	Correct	2 ms	820 KB	Output is correct
18	Correct	2 ms	872 KB	Output is correct
19	Correct	2 ms	872 KB	Output is correct
20	Correct	2 ms	872 KB	Output is correct

Subtask #3
25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	380 KB	Output is correct
3	Correct	2 ms	456 KB	Output is correct
4	Correct	2 ms	628 KB	Output is correct
5	Correct	2 ms	628 KB	Output is correct
6	Correct	2 ms	628 KB	Output is correct
7	Correct	2 ms	628 KB	Output is correct
8	Correct	2 ms	628 KB	Output is correct
9	Correct	2 ms	628 KB	Output is correct
10	Correct	2 ms	628 KB	Output is correct
11	Correct	2 ms	628 KB	Output is correct
12	Correct	2 ms	628 KB	Output is correct
13	Correct	2 ms	664 KB	Output is correct
14	Correct	2 ms	796 KB	Output is correct
15	Correct	2 ms	796 KB	Output is correct
16	Correct	2 ms	820 KB	Output is correct
17	Correct	2 ms	820 KB	Output is correct
18	Correct	2 ms	872 KB	Output is correct
19	Correct	2 ms	872 KB	Output is correct
20	Correct	2 ms	872 KB	Output is correct
21	Correct	2 ms	872 KB	Output is correct
22	Correct	4 ms	872 KB	Output is correct
23	Correct	10 ms	936 KB	Output is correct
24	Correct	5 ms	1032 KB	Output is correct
25	Correct	6 ms	1128 KB	Output is correct
26	Correct	5 ms	1208 KB	Output is correct
27	Correct	5 ms	1276 KB	Output is correct
28	Correct	5 ms	1356 KB	Output is correct
29	Correct	5 ms	1436 KB	Output is correct
30	Correct	4 ms	1492 KB	Output is correct
31	Correct	5 ms	1516 KB	Output is correct
32	Correct	5 ms	1596 KB	Output is correct
33	Correct	6 ms	1676 KB	Output is correct
34	Correct	5 ms	1884 KB	Output is correct
35	Correct	5 ms	1884 KB	Output is correct

Subtask #4
49.0 / 49.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	380 KB	Output is correct
3	Correct	2 ms	456 KB	Output is correct
4	Correct	2 ms	628 KB	Output is correct
5	Correct	2 ms	628 KB	Output is correct
6	Correct	2 ms	628 KB	Output is correct
7	Correct	2 ms	628 KB	Output is correct
8	Correct	2 ms	628 KB	Output is correct
9	Correct	2 ms	628 KB	Output is correct
10	Correct	2 ms	628 KB	Output is correct
11	Correct	2 ms	628 KB	Output is correct
12	Correct	2 ms	628 KB	Output is correct
13	Correct	2 ms	664 KB	Output is correct
14	Correct	2 ms	796 KB	Output is correct
15	Correct	2 ms	796 KB	Output is correct
16	Correct	2 ms	820 KB	Output is correct
17	Correct	2 ms	820 KB	Output is correct
18	Correct	2 ms	872 KB	Output is correct
19	Correct	2 ms	872 KB	Output is correct
20	Correct	2 ms	872 KB	Output is correct
21	Correct	2 ms	872 KB	Output is correct
22	Correct	4 ms	872 KB	Output is correct
23	Correct	10 ms	936 KB	Output is correct
24	Correct	5 ms	1032 KB	Output is correct
25	Correct	6 ms	1128 KB	Output is correct
26	Correct	5 ms	1208 KB	Output is correct
27	Correct	5 ms	1276 KB	Output is correct
28	Correct	5 ms	1356 KB	Output is correct
29	Correct	5 ms	1436 KB	Output is correct
30	Correct	4 ms	1492 KB	Output is correct
31	Correct	5 ms	1516 KB	Output is correct
32	Correct	5 ms	1596 KB	Output is correct
33	Correct	6 ms	1676 KB	Output is correct
34	Correct	5 ms	1884 KB	Output is correct
35	Correct	5 ms	1884 KB	Output is correct
36	Correct	479 ms	14716 KB	Output is correct
37	Correct	329 ms	19044 KB	Output is correct
38	Correct	124 ms	19044 KB	Output is correct
39	Correct	289 ms	24176 KB	Output is correct
40	Correct	283 ms	27772 KB	Output is correct
41	Correct	372 ms	31988 KB	Output is correct
42	Correct	243 ms	33288 KB	Output is correct
43	Correct	125 ms	34928 KB	Output is correct
44	Correct	404 ms	42932 KB	Output is correct
45	Correct	401 ms	50624 KB	Output is correct
46	Correct	416 ms	58268 KB	Output is correct
47	Correct	338 ms	65764 KB	Output is correct
48	Correct	350 ms	74104 KB	Output is correct
49	Correct	358 ms	81148 KB	Output is correct
50	Correct	426 ms	89576 KB	Output is correct

답안 #84373

Compilation message

Subtask #1 11.0 / 11.0

Subtask #2 15.0 / 15.0

Subtask #3 25.0 / 25.0

Subtask #4 49.0 / 49.0

Subtask #1
11.0 / 11.0

Subtask #2
15.0 / 15.0

Subtask #3
25.0 / 25.0

Subtask #4
49.0 / 49.0