제출 #1366074

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1366074		shrimb	Index (COCI21_index)	C++20	60 / 110	2595 ms	40872 KiB

index

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

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

template<class x>
using ordered_set = tree<x, null_type,less<x>,  rb_tree_tag,tree_order_statistics_node_update>;

const int maxn = 200'001;

int l[maxn], r[maxn], la[maxn], ra[maxn], ans[maxn];
vector<int> pos[maxn], buckets[maxn];
// pos[i] = all indices j which have p[j] = i

signed main () {
    cin.tie(0) -> sync_with_stdio(0);

    int n, q; cin >> n >> q;

    int p[n + 1]; 
    for (int i = 1 ; i <= n ; i++) {
        cin >> p[i];
        pos[p[i]].push_back(i);
    }
    for (int i = 1 ; i <= q ; i++) {
        cin >> l[i] >> r[i];
        la[i] = 1, ra[i] = n;
        buckets[(1 + n) / 2].push_back(i);
    }

    for (int _ = 0 ; _ < 19 ; _++) {
        ordered_set<int> os;
        for (int i = maxn - 1 ; i >= 0 ; i--) {
            for (int j : pos[i]) os.insert(j);
            // all values >= i have been inserted into 'os'
            while (buckets[i].size()) {
                int j = buckets[i].back(); buckets[i].pop_back();
                // count the number of k in 'os' such that l[j] <= k <= r[j]
                int k = os.order_of_key(r[j] + 1) - os.order_of_key(l[j]);

                if (k >= i) {
                    ans[j] = i;
                    la[j] = i + 1;
                } else {
                    ra[j] = i - 1;
                }

                if (la[j] <= ra[j]) {
                    buckets[(la[j] + ra[j]) / 2].push_back(j);
                }
            }
        }
    }  

    for (int i = 1 ; i <= q ; i++) cout << ans[i] << ' ';  
}

• 서브태스크 1: 20 / 20
• 서브태스크 2: 40 / 40
• 서브태스크 3: 0 / 50