Submission #1264471

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264471		Sofiatpc	Floppy (RMI20_floppy)	C++20	100 / 100	57 ms	3912 KiB

floppy

#include <bits/stdc++.h>
#include "floppy.h"

using namespace std;

#define fi first
#define sc second

void read_array(int subtask_id, const vector<int> &v) {
    string bits;
    stack<int> st;
    for(int i = 0; i < v.size(); i++){
        while(st.size() > 0 && v[st.top()] < v[i]){
            bits.push_back('0');
            st.pop();
        }
        bits.push_back('1');
        st.push(i);
    }
    save_to_floppy(bits);
}

vector<int> solve_queries(int subtask_id, int N, const string &bits, const vector<int> &a, const vector<int> &b) {

    vector< pair< pair<int,int>, int > > q; // b a i

    for(int i = 0; i < a.size(); i++)q.push_back({ { b[i], a[i]}, i});
    sort(q.begin(),q.end());
    
    vector<int> answers; answers.resize(a.size());
    int cur = 0, id = 0;
    vector<int> st;
    for(int i = 0; i < bits.size(); i++){
        if(bits[i] == '0')st.pop_back();
        else{
            st.push_back(id);
            while( cur < q.size() && q[cur].fi.fi == id){
                int x = lower_bound(st.begin(),st.end(),q[cur].fi.sc)-st.begin();
                answers[ q[cur].sc ] = st[x];
                cur++;
            }
            id++;
        }
    }
    return answers;
}

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