oj.uz

Submission #399854

# Submission time Handle Problem Language Result Execution time Memory
399854 2021-05-06T18:13:36 Z rocks03 Floppy (RMI20_floppy) C++14
100 / 100
 130 ms 15336 KB 
#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

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 896 KB Output is correct
2 Correct 4 ms 896 KB Output is correct
3 Correct 4 ms 900 KB Output is correct
4 Correct 2 ms 904 KB Output is correct
5 Correct 3 ms 900 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 4228 KB Output is correct
2 Correct 28 ms 4212 KB Output is correct
3 Correct 29 ms 4360 KB Output is correct
4 Correct 30 ms 4224 KB Output is correct
5 Correct 28 ms 4268 KB Output is correct

Subtask #3
72.0 / 72.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 15240 KB Output is correct
2 Correct 130 ms 15316 KB Output is correct
3 Correct 119 ms 15336 KB Output is correct
4 Correct 121 ms 15276 KB Output is correct
5 Correct 116 ms 15192 KB Output is correct