Submission #1174760

#	Time	Username	Problem	Language	Result	Execution time	Memory
1174760		Zero_OP	Floppy (RMI20_floppy)	C++20	100 / 100	63 ms	5456 KiB

floppy

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

using namespace std;

#define FOR(i, l, r) for(int i = (l); i < (r); ++i)
#define ROF(i, r, l) for(int i = (r)-1; i >= (l); --i)

#define mp make_pair
#define mt make_tuple
#define ff first
#define ss second

#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)
#define pb push_back
#define eb emplace_back
#define sz(v) (int)v.size()
#define compact(v) v.erase(unique(all(v)), end(v))

#define dbg(x) "[" #x " = " << (x) << "]"

template<typename T>
      bool minimize(T& a, const T& b){
            if(a > b) return a = b, true;
            return false;
      }

template<typename T>
      bool maximize(T& a, const T& b){
            if(a < b) return a = b, true;
            return false;
      }

using ll = long long;
using db = double;
using ld = long double;
using ull = unsigned long long;

using pi = pair<int, int>;
using pl = pair<ll, ll>;

using vi = vector<int>;
using vl = vector<ll>;
using vc = vector<char>;
using vd = vector<db>;
using vb = vector<bool>;

using vpi = vector<pi>;
using vpl = vector<pl>;


void read_array(int subtask_id, const std::vector<int> &v) {
      std::string bits = "";

      stack<int> st;
      int N = sz(v);
      FOR(i, 0, N){
            while(!st.empty() && v[st.top()] <= v[i]){
                  st.pop();
                  bits += "0";
            }

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

      assert(sz(bits) <= 2 * N);
      save_to_floppy(bits);
}

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

      stack<int> st;
      int idx = 0;

      vector<vi> lift(20, vi(N, -1));
      FOR(i, 0, sz(bits)){
            if(bits[i] == '0') st.pop();
            else{
                  lift[0][idx] = (st.empty() ? -1 : st.top());
                  st.push(idx++);
//                  cout << lift[0][idx-1] << " \n"[i == N];
            }
      }

      for(int i = 1; (1 << i) <= N; ++i){
            for(int j = 0; j < N; ++j){
                  if(lift[i-1][j] == -1) lift[i][j] = -1;
                  else lift[i][j] = lift[i-1][lift[i-1][j]];
            }
      }

      vi answers;
      int M = sz(a);
      FOR(i, 0, M){
            int l = a[i], r = b[i];
            ROF(i, 20, 0){
                  if(lift[i][r] >= l) r = lift[i][r];
            }

            answers.pb(r);
      }
      return answers;
}

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