Submission #1174166

#	Time	Username	Problem	Language	Result	Execution time	Memory
1174166		ivaziva	Index (COCI21_index)	C++20	60 / 110	2599 ms	132540 KiB

index

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>

using namespace std;

struct Node{
    Node *l,*r;int sum;
    Node(int val):l(nullptr),r(nullptr),sum(val){}
    Node(Node *l,Node *r):l(l),r(r),sum(0){
        if (l!=nullptr) sum+=l->sum;
        if (r!=nullptr) sum+=r->sum;
    }
    Node(Node *cp):l(cp->l),r(cp->r),sum(cp->sum){}
};

#define MAXN 200001

int n,q;
Node* root[MAXN];

Node* build(int l,int r)
{
    if (l==r) return new Node(0);
    int mid=(l+r)/2;return new Node(build(l,mid),build(mid+1,r));
}

Node* update(Node* node,int l,int r,int pos,int val)
{
    if (l==r) return new Node(node->sum+val);
    int mid=(l+r)/2;
    if (pos<=mid) return new Node(update(node->l,l,mid,pos,val),node->r);
    else return new Node(node->l,update(node->r,mid+1,r,pos,val));
}

int query(Node* node,int l,int r,int a,int b)
{
    if (a>b) return 0;
    if (l==a and r==b) return node->sum;
    int mid=(l+r)/2;
    return query(node->l,l,mid,a,min(b,mid))+query(node->r,mid+1,r,max(a,mid+1),b);
}

int main()
{
    ios_base::sync_with_stdio(false);ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);cin>>n>>q;root[0]=build(1,200000);int maks=0;
    for (int i=1;i<=n;i++) {int x;cin>>x;root[i]=update(root[i-1],1,n,x,1);maks=max(maks,x);}
    for (int i=1;i<=q;i++)
    {
        int levo,desno;cin>>levo>>desno;
        int l=2,r=desno-levo+1,rez=1;
        while (l<=r)
        {
            int mid=(l+r)/2;
            if (query(root[desno],1,n,mid,maks)-query(root[levo-1],1,n,mid,maks)>=mid) {rez=mid;l=mid+1;}
            else r=mid-1;
        }
        cout<<rez<<endl;
    }
}

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