제출 #1124977

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1124977		yavuzskarahan	Index (COCI21_index)	C++20	20 / 110	2597 ms	29180 KiB

index

// In the name of God, the Most Gracious, the Most Merciful.
// @yavuzskarahan - iflbot();

#include <bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(0); cin.tie(0);
#define file(x) freopen(x ".in", "r", stdin); freopen(x ".out", "w", stdout);
#define FOR(i, L, R) for (int i = (L); i <= (R); i++)
#define SORT(v) sort((v).begin(), (v).end()) 
#define RSORT(v) sort((v).rbegin(), (v).rend()) 
#define int long long
#define ll long long
#define pb push_back
#define ub(v, a) upper_bound((v).begin(), (v).end(), (a))
#define lb(v, a) lower_bound((v).begin(), (v).end(), (a))
#define f first
#define s second
#define tm (tl+(tr-tl)/2)
#define space << " " <<
#define vi vector<int>
#define pii pair<int,int> 
#define vpii vector<pair<int,int>>
#define now chrono::high_resolution_clock::now()

const long long N = 2e5+5;
const long long M = 3e6+5;
const long long K = 23;

const long long SQRTN = sqrt(N);
const long long MOD = 1e9+7;
inline int sum(int a, int b) {return ((a%MOD)+(b%MOD))%MOD;}
inline int mul(int a, int b) {return ((a%MOD)*(b%MOD))%MOD;}
inline int epow(int n, int us){int cvp = 1; while(us){if (us%2){cvp *= n;}n *= n; us /= 2;} return cvp;}

int n, q, l, r, a[N];
vi sgt[4*N];

inline bool compare(const int& a, const int& b){
    return a > b;
}

inline int h(const vi& papers){

    int l = 0;
    int r = papers.size()-1;
    int hIndex = 0;

    while(l<=r){
        int m = l+(r-l)/2;
        if (papers[m] >= m+1) hIndex = l = m+1;
        else r = m-1;
    }

    return hIndex;

}

inline vi merge(const vi& a, const vi& b){
    vi result(a.size()+b.size());
    merge(a.begin(), a.end(), b.begin(), b.end(), result.begin(), compare);
    return result;
}

inline void build(int v, int tl, int tr) {
    if (tl == tr) {sgt[v].pb(a[tl]); return;}
    build(2*v, tl, tm);
    build(2*v+1, tm+1, tr);
    sgt[v] = merge(sgt[2*v], sgt[2*v+1]);
}

inline vi query(int v, int tl, int tr, int l, int r) {
    if (tr < l || tl > r) return {};
    if (l <= tl && tr <= r) return sgt[v];
    return merge(query(2*v, tl, tm, l, r), query(2*v+1, tm+1, tr, l, r));
}

inline int solve() {

    cin >> n >> q;

    FOR(i,1,n) cin >> a[i];
 
    build(1,1,n);

    while (q--) {

        cin >> l >> r;

        vi interval = query(1,1,n,l,r);

        // for(int i : interval) cout << i << " ";
        // cout << endl;

        cout << h(interval) << endl;

    }

    return 0;
}

int32_t main() {
 
    #ifdef LOCAL
        auto start = now;
    #endif
 
    fast;
    int t = 1;
    //cin >> t;
 
    while(t--){
        solve();
    }
 
    #ifdef LOCAL
        auto end = now;
        chrono::duration<double> elapsed = end - start;
        cout << endl << "runtime: " << endl << elapsed.count() << endl;
    #endif
 
    return 0;
}

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