Submission #399854

#	Time	Username	Problem	Language	Result	Execution time	Memory
399854		rocks03	Floppy (RMI20_floppy)	C++14	100 / 100	130 ms	15336 KiB

floppy

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ff first
#define ss second
#define pb push_back
#define SZ(x) ((int)(x).size())
#define all(x) x.begin(), x.end()
#define debug(x) cout << #x << ": " << x << " "
#define nl cout << "\n"
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define per(i, a, b) for(int i = (a); i >= (b); i--)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

void save_to_floppy(const string &bits);

void read_array(int subtask_id, const vector<int> &a) {
    stack<int> st;
    string bits = "";
    int N = SZ(a);
    per(i, N - 1, 0){
        while(!st.empty() && a[i] >= a[st.top()]){
            st.pop(); bits += '0';
        }
        st.push(i);
        bits += '1';
    }
    save_to_floppy(bits);
}

const int MAXK = 20+5;
const int MAXN = 5e5+100;
int nxt[MAXK][MAXN];

vector<int> solve_queries(int subtask_id, int N, const string &bits, const vector<int> &QL, const vector<int> &QR){
    stack<int> st;
    int j = 0;
    per(i, N - 1, 0){
        while(!st.empty() && bits[j] == '0'){
            st.pop(); j++;
        }
        if(!st.empty()){
            nxt[0][i] = st.top();
        } else{
            nxt[0][i] = i;
        }
        st.push(i); j++;
    }
    rep(k, 0, MAXK - 1){
        rep(i, 0, N){
            nxt[k + 1][i] = nxt[k][nxt[k][i]];
        }
    }
    int Q = SZ(QL);
    vector<int> ans(Q);
    rep(q, 0, Q){
        int l = QL[q], r = QR[q];
        per(k, MAXK - 1, 0) if(nxt[k][l] <= r) l = nxt[k][l];
        ans[q] = l;
    }
    return ans;
}

Compilation message (stderr)

stub.cpp: In function 'void run2()':
stub.cpp:101:30: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  101 |     if (query_answers.size() != M) {
      |         ~~~~~~~~~~~~~~~~~~~~~^~~~

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