Submission #968423

#	Time	Username	Problem	Language	Result	Execution time	Memory
968423		VMaksimoski008	Index (COCI21_index)	C++14	60 / 110	2566 ms	8416 KiB

index

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

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), L(q), R(q, 2e5), ANS(q, 1);
    for(int i=1; i<=n; i++) cin >> v[i];

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

    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:27:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   27 |         for(auto &[mid, st] : to_change) {
      |                   ^

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