Submission #1289836

#	Time	Username	Problem	Language	Result	Execution time	Memory
1289836		HoriaHaivas	Floppy (RMI20_floppy)	C++20	100 / 100	162 ms	3820 KiB

floppy

#include<bits/stdc++.h>
#include "floppy.h"
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast")
//#define int long long

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int range_rng(int l, int r) {
    return uniform_int_distribution<int>(l,r)(rng);
}

int st[100005];
int dr[100005];

void read_array(int subtask_id, const vector<int> &v) {
    int i,t;
    string bits;
    t=0;
    for (i=0; i<v.size(); i++) {
        if (t==0 || v[i]<=v[st[t]]) {
            t++;
            st[t]=i;
            bits+="1";
        } else {
            while (t>0 && v[i]>v[st[t]]) {
                bits+="0";
                t--;
            }
            t++;
            st[t]=i;
            bits+="1";
        }
    }
    while (t>0) {
        bits+="0";
        t--;
    }
    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<int> sol;
    int i,j,t,cnt,l,r;
    t=0;
    cnt=0;
    for (i=0; i<bits.size(); i++) {
        if (bits[i]=='1') {
            t++;
            st[t]=cnt;
            cnt++;
        } else {
            dr[st[t]]=cnt;
            t--;
        }
    }
    sol.clear();
    for (i=0; i<a.size(); i++) {
        l=a[i];
        r=b[i];
        for (j=l; j<=r; j++) {
            if (dr[j]>r) {
                sol.push_back(j);
                break;
            }
        }
    }
    return sol;
}

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