제출 #1289362

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1289362		MinhKien	Floppy (RMI20_floppy)	C++20	0 / 100	50 ms	3960 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];

bool cmp(const int &x, const int &y) {
    return x > y;
}

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]) {
                auto it = lower_bound(cur.begin(), cur.end(), l[z], cmp);
                ans[z] = *it;
            }
        } else cur.pop_back();
    }

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

    return res;
}

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