Submission #968421

#	Time	Username	Problem	Language	Result	Execution time	Memory
968421		VMaksimoski008	Index (COCI21_index)	C++14	110 / 110	1601 ms	13612 KiB

index

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,bmi,bmi2,lzcnt,popcnt")

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

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

    vector<int> v(n+1);
    for(int i=1; i<=n; i++) cin >> v[i];

    vector<pii> qus(q);
    for(pii &x : qus) cin >> x.first >> x.second;

    vector<int> L(q, 1), R(q, 2e5), ANS(q, 1);
    bool changed = 1;

    while(changed) {
        changed = 0;

        map<int, stack<int> > to_change;
        for(int i=0; i<q; i++)
            if(L[i] <= R[i]) to_change[(L[i] + R[i]) / 2].push(i);

        for(auto &[mid, st] : to_change) {
            vector<int> pref(n+1);
            for(int i=1; i<=n; i++) pref[i] = pref[i-1] + (v[i] >= mid);

            while(!st.empty()) {
                changed = 1;
                int id = st.top();
                st.pop();
                if(pref[qus[id].second] - pref[qus[id].first-1] >= mid) ANS[id] = mid, L[id] = mid + 1;
                else R[id] = mid - 1;
            }
        }
    }

    for(int &x : ANS) cout << x << '\n';
    return 0;
}

Compilation message (stderr)

index.cpp: In function 'int32_t main()':
index.cpp:32:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   32 |         for(auto &[mid, st] : to_change) {
      |                   ^

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