Submission #712120

#	Time	Username	Problem	Language	Result	Execution time	Memory
712120		Thienu	Index (COCI21_index)	C++17	110 / 110	2132 ms	260280 KiB

index

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
int a,n,t,x,y,st,md,ed;
vector<int> v[200005];
struct node
{
    int val;
    node *l,*r;
};
typedef node* pnode;
void build(pnode tree,int st,int ed)
{
    int md=(st+ed)/2;
    if(st==ed)
    {
        tree->val=1;
        return;
    }
    tree->l=new node(),tree->r=new node();
    build(tree->l,st,md);
    build(tree->r,md+1,ed);
    tree->val=tree->l->val+tree->r->val;
}
void update(pnode tree,pnode pre,int st,int ed,int idx,int val)
{
    int md=(st+ed)/2;
    if(st==ed)
    {
        tree->val=pre->val+val;
        return;
    }
    if(idx<=md)
    {
        // if(!tree->l)
        // {
            tree->l=new node();
        // }else
        // {
        //     tree->l=pre->l;
        // }
        tree->r=pre->r;
        update(tree->l,pre->l,st,md,idx,val);
    }else
    {
        tree->l=pre->l;
        // if(!tree->r)
        // {
            tree->r=new node();
        // }else
        // {
        //     tree->r=pre->r;
        // }
        update(tree->r,pre->r,md+1,ed,idx,val);
    }
    tree->val=tree->l->val+tree->r->val;
}
int query(pnode tree,int st,int ed,int l,int r)
{
    int md=(st+ed)/2;
    if(st>r||ed<l)return 0;
    if(st>=l&&ed<=r)return tree->val;
    return query(tree->l,st,md,l,r)+query(tree->r,md+1,ed,l,r);
}
void debug(pnode tree,int st,int ed)
{
    int md=(st+ed)/2;
    if(st==ed)
    {
        printf("%d %d %d\n",st,ed,tree->val);
        return;
    }
    debug(tree->l,st,md);
    debug(tree->r,md+1,ed);
    printf("%d %d %d\n",st,ed,tree->val);
}
node root[400005];
int checkpt[200005];
int main()
{
    ios_base::sync_with_stdio(0),cin.tie(0);
    cin >> n >> t;
    build(&root[1],1,n);
    /*debug(&root[1],1,n);
    printf("query\n");
    for(int i=1;i<=n;i++)
    {
        for(int j=i;j<=n;j++)
        {
            printf("%d %d %d\n",i,j,query(&root[1],1,n,i,j));
        }
    }*/
    checkpt[1] = 1;
    for(int i=1;i<=n;i++)
    {
        cin >> a;
        v[a].pb(i);
    }
    int upd_num = 1;
    for(int i=2;i<=200000;i++)
    {
        update(&root[upd_num+1],&root[upd_num],1,n,1,0); upd_num++;
        for(int j=0;j<(int)v[i-1].size();j++)
        {
            int num=v[i-1][j];
            update(&root[upd_num+1],&root[upd_num],1,n,num,-1); upd_num++;
            // if(i==2)
            // {
            //     printf("%d\n",j);
            //     debug(&root[1],1,n);
            // }
        }
        checkpt[i] = upd_num;
    }
    /*for(int i=1;i<=8;i++)
    {
        printf("%d\n",i);
        for(int j=1;j<=n;j++)
        {
            for(int k=j;k<=n;k++)
            {
                printf("%d %d %d\n",j,k,query(&root[i],1,n,j,k));
            }
        }
    }*/
    while(t--)
    {
        cin >> x >> y;
        st=1,ed=200000;
        while(ed>=st)
        {
            md=(st+ed)/2;
            if(query(&root[checkpt[md]],1,n,x,y)>=md)
            {
                st=md+1;
            }else
            {
                ed=md-1;
            }
        }
        printf("%d\n", st-1);
        /*for(int i=1;i<=8;i++)
        {
            printf("%d ",query(&root[i],1,n,x,y));
        }
        printf("\n");*/
        //printf("%d %d %d\n",st,md,ed);
    }
}

• Subtask 1: 20 / 20
• Subtask 2: 40 / 40
• Subtask 3: 50 / 50