Submission #1289523

#	Time	Username	Problem	Language	Result	Execution time	Memory
1289523		MinhKien	Floppy (RMI20_floppy)	C++20	100 / 100	55 ms	4496 KiB

floppy

#include <algorithm>
#include <iostream>
#include "floppy.h"
#include <vector>
#include <string>
#include <stack>

using namespace std;

void read_array(int subtask_id, const vector <int> &v) {
    string bits = "\0";
    stack <int> st;
    for (int i = 0; i < v.size(); ++i) {
        while (!st.empty() && v[st.top()] < v[i]) {
            bits += "0";
            st.pop();
        }

        bits += "1";
        st.push(i);
    }
    save_to_floppy(bits);
}

const int N = 8e4 + 10;
vector <int> q[N];
int ans[N];

vector <int> solve_queries (int subtask_id, int n, const string &bits, const vector <int> &l, const vector <int> &r) {
    for (int i = 0; i < r.size(); ++i) {
        q[r[i]].push_back(i);
    }

    int cnt = 0;
    vector <int> cur;
    for (int i = 0; i < bits.size(); ++i) {
        if (bits[i] == '1') {
            cur.push_back(cnt);

            for (int z: q[cnt]) {
                int L = 0, R = (int)cur.size() - 1, curval = R;
                while (L <= R) {
                    int mid = (L + R) >> 1;

                    if (cur[mid] >= l[z]) {
                        curval = mid;
                        R = mid - 1;
                    } else {
                        L = mid + 1;
                    }
                }

                ans[z] = cur[curval];
            }

            ++cnt;
        } else cur.pop_back();
    }

    vector <int> res;
    for (int i = 0; i < l.size(); ++i) {
        res.push_back(ans[i]);
    }

    return res;
}

• Subtask 1: 7 / 7
• Subtask 2: 21 / 21
• Subtask 3: 72 / 72