Submission #1102830

#	Time	Username	Problem	Language	Result	Execution time	Memory
1102830		spycoderyt	Index (COCI21_index)	C++17	110 / 110	1716 ms	138672 KiB

index

#include <bits/stdc++.h>
using namespace std;
const int N = 3e5+5;
struct tree{
    struct node{
        node *l,*r;
        int sum;
        node(int k) : sum(k),l(nullptr),r(nullptr) {}
        node(node* l,node* r) : l(l),r(r) {
            sum = (l?l->sum:0) + (r?r->sum:0);
        }
        node() : sum(0),l(nullptr),r(nullptr) {}
    };
    public:
    typedef node* pnode;
    pnode roots[N];
    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* upd(node* cur,int l,int r,int tar,int val) {
        if(l>r)return 0;
        if(l==r) return new node(val);
        assert(cur);
        int mid = (l+r)/2;
        if(tar > mid) return new node(cur->l,upd(cur->r,mid+1,r,tar,val));
        else return new node(upd(cur->l,l,mid,tar,val),cur->r);
    }
    int qry(node*cur,int l,int r,int ll,int rr) {
        if(!cur)return 0;
        if(l>r||r<ll|l>rr)return 0;
        if(l>=ll&&r<=rr)return cur->sum;
        int mid = (l+r)/2;
        return qry(cur->l,l,mid,ll,rr) + qry(cur->r,mid+1,r,ll,rr);
    }
}t;
int n,q,a,b;
int main() {
    cin>>n>>q;
    vector<int> v(n+1);
    vector<int> freq(n+1);
    for(int i = 1;i<=n;i++)cin>>v[i];
    t.roots[0] = t.build(1,n);
    for(int i = 1;i<=n;i++) {
        freq[v[i]]++;
        t.roots[i] = t.upd(t.roots[i-1],1,n,v[i],freq[v[i]]);
    }
    for(int i = 0;i<q;i++) {
        cin>>a>>b;
        // cout << a << " " << b << "\n";
        int l = 1, r = n, ans;
        while(l<=r) {
            int mid = (l+r)/2;
            int frq = t.qry(t.roots[b],1,n,mid,n) - t.qry(t.roots[a-1],1,n,mid,n);
            // cout << frq << "\n";
            if(frq >= mid) ans = mid, l = mid+1;
            else r = mid - 1;
        }
        cout<<ans<<"\n";
    }
}

/*

7 6
3 2 3 1 1 4 7
3 4
1 7
1 6
4 5
1 2
5 7

*/

Compilation message (stderr)

index.cpp: In constructor 'tree::node::node(int)':
index.cpp:7:13: warning: 'tree::node::sum' will be initialized after [-Wreorder]
    7 |         int sum;
      |             ^~~
index.cpp:6:15: warning:   'tree::node* tree::node::l' [-Wreorder]
    6 |         node *l,*r;
      |               ^
index.cpp:8:9: warning:   when initialized here [-Wreorder]
    8 |         node(int k) : sum(k),l(nullptr),r(nullptr) {}
      |         ^~~~
index.cpp: In constructor 'tree::node::node()':
index.cpp:7:13: warning: 'tree::node::sum' will be initialized after [-Wreorder]
    7 |         int sum;
      |             ^~~
index.cpp:6:15: warning:   'tree::node* tree::node::l' [-Wreorder]
    6 |         node *l,*r;
      |               ^
index.cpp:12:9: warning:   when initialized here [-Wreorder]
   12 |         node() : sum(0),l(nullptr),r(nullptr) {}
      |         ^~~~
index.cpp: In member function 'int tree::qry(tree::node*, int, int, int, int)':
index.cpp:32:18: warning: suggest parentheses around comparison in operand of '|' [-Wparentheses]
   32 |         if(l>r||r<ll|l>rr)return 0;
      |                 ~^~~
index.cpp: In function 'int main()':
index.cpp:60:20: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   60 |         cout<<ans<<"\n";
      |                    ^~~~

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