Submission #1189143

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189143		Ludissey	Index (COCI21_index)	C++20	110 / 110	784 ms	33924 KiB

index

#include <bits/stdc++.h>
#define int long long
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()

using namespace std;
vector<int> t;
int n;

void update(int p, int val){
    for (t[p+=n] += val; p > 1; p/=2) t[p/2] = t[p] + t[p^1];
}

int query(int l, int r) { 
    r++;
    int res = 0;
    for (l += n, r += n; l < r; l/=2, r/=2) {
      if (l&1) res += t[l++];
      if (r&1) res += t[--r];
    }
    return res;
}


signed main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int q; cin >> n >> q;
    vector<int> h(n);
    t.resize(2*n+4);
    vector<pair<int,int>> sh;
    for (int i = 0; i < n; i++) cin >> h[i];
    for (int i = 0; i < n; i++) sh.push_back({h[i],i});
    sort(rall(sh));
    vector<pair<int,int>> que(q);
    vector<int> ans(q);
    for (int i = 0; i < q; i++) { cin >> que[i].first >> que[i].second; que[i].first--;  que[i].second--; }
    for (int i = 0; i < q; i++) cin >> que[i].first >> que[i].second;
    vector<pair<pair<int,pair<int,int>>,int>> v;
    for (int i = 0; i < q; i++) v.push_back({{(n+1)/2,{1,n}},i});
    while(sz(v)>0){
        vector<pair<pair<int,pair<int,int>>,int>> v2;
        sort(rall(v));
        for (int i = 0; i < sz(t); i++) t[i]=0;
        int j=0;
        for (int i = 0; i < sz(v); i++)
        {
            int l=v[i].first.second.first;
            int r=v[i].first.second.second;
            int mid=(l+r)/2;
            while(j<sz(sh)&&sh[j].first>=v[i].first.first){
                update(sh[j].second,1);
                j++;
            }
            int qr=query(que[v[i].second].first,que[v[i].second].second);
            if(qr<mid){
                r=mid-1;
            }else{
                ans[v[i].second]=mid;
                l=mid+1;
            }
            if(l<=r){
                v2.push_back({{(l+r)/2,{l,r}},v[i].second});
            }
        }
        swap(v,v2);
    }
    for (int i = 0; i < q; i++) cout << ans[i] << "\n";
    return 0;
}

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