제출 #1177782

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1177782		Sofiatpc	Index (COCI21_index)	C++20	110 / 110	280 ms	20644 KiB

index

#include <bits/stdc++.h>

using namespace std;

#define fi first
#define sc second
#define sz(v) (int)v.size()
const int MAXN = 2*1e5+5;
pair<int,int> v[MAXN];
vector< vector< int> > que[2];
vector< int > l[2],r[2];
int bit[MAXN], a[MAXN], b[MAXN], ans[MAXN], n;

void update(int i){
    for(; i <= n; i+= i&(-i))
        bit[i]++;
}

int query(int i){
    int ans = 0;
    for(; i > 0; i-= i&(-i))
        ans += bit[i];
    return ans;
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int q; cin>>n>>q;
    for(int i = 1; i <= n; i++){
        cin>>v[i].fi;
        v[i].sc = i;
    }
    sort(v+1,v+1+n);

    que[0].push_back({});
    for(int i = 1;i <= q; i++){
        cin>>a[i]>>b[i];
        que[0][0].push_back(i);
    }
    l[0].push_back(1); r[0].push_back(n);

    int niv = 0;
    while(sz(l[niv]) != n){
        for(int i = 1; i <= n; i++)bit[i] = 0;

        int cur = n, nxt = niv^1;

        for(int j = 0; j < sz(l[niv]); j++){
            int mid = ( l[niv][j] + r[niv][j] +1) /2;

            while(cur > 0 && v[cur].fi >= mid){
                update(v[cur].sc);
                cur--;
            }


            vector< int > menor = {}, maior = {};
            for(int k = 0; k < sz(que[niv][j]); k++){
                int temp = query( b[ que[niv][j][k] ] ) - query( a[ que[niv][j][k] ] -1);

                if(temp >= mid) maior.push_back( que[niv][j][k] );
                else menor.push_back( que[niv][j][k] );
            }

            
                l[nxt].push_back(mid); r[nxt].push_back(r[niv][j]); que[nxt].push_back(maior);
                if(mid-1 >= l[niv][j]){ l[nxt].push_back(l[niv][j]); r[nxt].push_back(mid-1);  que[nxt].push_back(menor); }
            
        }

        l[niv].clear(); r[niv].clear(); que[niv].clear();
        niv = nxt;
    }

    for(int i = 0; i < sz(l[niv]); i++)
        for(int j = 0; j < sz(que[niv][i]); j++) ans[ que[niv][i][j] ] = l[niv][i];
    
    for(int i = 1; i <= q; i ++)cout<<ans[i]<<"\n";
}

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