Submission #1154088

#	Time	Username	Problem	Language	Result	Execution time	Memory
1154088		salmon	Index (COCI21_index)	C++20	110 / 110	2347 ms	401328 KiB

index

#include <bits/stdc++.h>
using namespace std;

int N,Q;
int lst[200100];
int ans[200100];
vector<int> pos[200100];
int l, r;

struct node{

    int s, e, m;
    node *l, *r;
    int v = 0;;

    node(int S, int E){
        s = S;
        e = E;
        m = (s + e)/2;

        if(s != e){
            l = new node(s,m);
            r = new node(m + 1,e);
        }
    }

    void update(int i){
        v++;

        if(s != e){
            if(i <= m) l -> update(i);
            else r -> update(i);
        }
    }

    int query(int S, int E){
        if(S <= s && e <= E) return v;

        long long int V = 0;

        if(S <= m) V += l -> query(S,E);
        if(m < E) V += r -> query(S,E);

        return V;
    }


}*root;

int main(){

    scanf(" %d",&N);
    scanf(" %d",&Q);

    vector<vector<int>> q;

    for(int i = 1; i <= N; i++){
        scanf(" %d",&lst[i]);
        pos[lst[i]].push_back(i);
    }

    for(int i = 0; i < Q; i++){
        scanf(" %d",&l);
        scanf(" %d",&r);

        q.push_back({(N + 1)/2,0,N,l,r,i});
    }


    sort(q.begin(),q.end());
    vector<vector<int>> q1;

    root = new node(1,N);

    int it = 200050;

    while(!q.empty()){

            root = new node(1,N);
            int it = 200050;
    while(!q.empty()){
        vector<int> v = q.back();
        q.pop_back();

        while(it >= v[0]){
            for(int j : pos[it]){
                root -> update(j);
            }
            it--;
        }


        if(v[1] == v[2]){
            ans[v[5]] = v[1];
        }
        else{
            if(root -> query(v[3],v[4]) >= v[0]){
                v[1] = v[0];
                v[0] = (v[1] + v[2] + 1) /2;
            }
            else{
                v[2] = v[0] - 1;
                v[0] = (v[2] + v[1] + 1)/2;
            }
            q1.push_back(v);
        }
    }
    sort(q1.begin(),q1.end());
    q = q1;
    q1.clear();
    }

    for(int i = 0; i < Q; i++) printf("%d\n",ans[i]);

}

Compilation message (stderr)

index.cpp: In function 'int main()':
index.cpp:52:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |     scanf(" %d",&N);
      |     ~~~~~^~~~~~~~~~
index.cpp:53:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |     scanf(" %d",&Q);
      |     ~~~~~^~~~~~~~~~
index.cpp:58:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |         scanf(" %d",&lst[i]);
      |         ~~~~~^~~~~~~~~~~~~~~
index.cpp:63:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |         scanf(" %d",&l);
      |         ~~~~~^~~~~~~~~~
index.cpp:64:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |         scanf(" %d",&r);
      |         ~~~~~^~~~~~~~~~

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