oj.uz

Submission #1102830

# Submission time Handle Problem Language Result Execution time Memory
1102830 2024-10-19T04:38:57 Z spycoderyt Index (COCI21_index) C++17
110 / 110
 1716 ms 138672 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 4 ms 852 KB Output is correct
2 Correct 4 ms 1064 KB Output is correct
3 Correct 4 ms 852 KB Output is correct
4 Correct 6 ms 712 KB Output is correct
5 Correct 4 ms 852 KB Output is correct
6 Correct 4 ms 852 KB Output is correct
7 Correct 4 ms 852 KB Output is correct
8 Correct 4 ms 852 KB Output is correct
9 Correct 4 ms 852 KB Output is correct
10 Correct 4 ms 852 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 852 KB Output is correct
2 Correct 4 ms 1064 KB Output is correct
3 Correct 4 ms 852 KB Output is correct
4 Correct 6 ms 712 KB Output is correct
5 Correct 4 ms 852 KB Output is correct
6 Correct 4 ms 852 KB Output is correct
7 Correct 4 ms 852 KB Output is correct
8 Correct 4 ms 852 KB Output is correct
9 Correct 4 ms 852 KB Output is correct
10 Correct 4 ms 852 KB Output is correct
11 Correct 261 ms 33204 KB Output is correct
12 Correct 276 ms 33196 KB Output is correct
13 Correct 272 ms 33356 KB Output is correct
14 Correct 288 ms 33356 KB Output is correct
15 Correct 268 ms 33356 KB Output is correct
16 Correct 275 ms 33356 KB Output is correct
17 Correct 287 ms 33360 KB Output is correct
18 Correct 278 ms 33356 KB Output is correct
19 Correct 270 ms 33308 KB Output is correct
20 Correct 295 ms 33240 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 852 KB Output is correct
2 Correct 4 ms 1064 KB Output is correct
3 Correct 4 ms 852 KB Output is correct
4 Correct 6 ms 712 KB Output is correct
5 Correct 4 ms 852 KB Output is correct
6 Correct 4 ms 852 KB Output is correct
7 Correct 4 ms 852 KB Output is correct
8 Correct 4 ms 852 KB Output is correct
9 Correct 4 ms 852 KB Output is correct
10 Correct 4 ms 852 KB Output is correct
11 Correct 261 ms 33204 KB Output is correct
12 Correct 276 ms 33196 KB Output is correct
13 Correct 272 ms 33356 KB Output is correct
14 Correct 288 ms 33356 KB Output is correct
15 Correct 268 ms 33356 KB Output is correct
16 Correct 275 ms 33356 KB Output is correct
17 Correct 287 ms 33360 KB Output is correct
18 Correct 278 ms 33356 KB Output is correct
19 Correct 270 ms 33308 KB Output is correct
20 Correct 295 ms 33240 KB Output is correct
21 Correct 1557 ms 138496 KB Output is correct
22 Correct 1527 ms 138452 KB Output is correct
23 Correct 1628 ms 138552 KB Output is correct
24 Correct 1625 ms 138520 KB Output is correct
25 Correct 1599 ms 138652 KB Output is correct
26 Correct 1716 ms 138624 KB Output is correct
27 Correct 1687 ms 138464 KB Output is correct
28 Correct 1543 ms 138480 KB Output is correct
29 Correct 1554 ms 138516 KB Output is correct
30 Correct 1611 ms 138672 KB Output is correct