Submission #1219404

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219404		KindaGoodGames	Floppy (RMI20_floppy)	C++20	28 / 100	1134 ms	5032 KiB

floppy

#include <stdlib.h>
#include <string.h>
#include<bits/stdc++.h>

#include "floppy.h"
#define pii pair<int,int>

using namespace std;
int B = 0;
int INF = numeric_limits<int>::max()/2;

struct SegmentTree{
    vector<pii> S;
    int len = 1;

    SegmentTree(vector<int>arr){
        int n = arr.size();
        while(len < n) len <<= 1;
        
        S.resize(2*len, {-INF,-1});
        for(int i = 0; i < n;i++){
            S[i+len] = {arr[i],i};
        }

        for(int i = len-1; i > 0; i--){
            S[i] = max(S[i*2],S[i*2+1]);
        }
    }

    pii query(int ql, int qr, int l = 0, int r = -2, int i = 1){
        if(r == -2) r = len;
        if(ql <= l && r <= qr) return S[i];
        if(r <= ql || qr <= l) return {-INF,-1};
    
        int mid = (l+r)/2;
        return max(query(ql,qr,l,mid,i*2),query(ql,qr,mid,r,i*2+1));
    }
};

void build(int l, int r, SegmentTree& seg, string& bits){
    if(l == r){
        bits += "00";
        return;
    } 

    pii res = seg.query(l,r+1);
    if(res.second == l){
        bits += "01";
        build(l+1, r, seg, bits);
    }else if(res.second == r){
        bits += "10";
        build(l, r-1, seg, bits); 
    }else{ 
        bits += "11";
        build(l, res.second-1, seg, bits); 
        build(res.second+1, r, seg, bits); 
    }
}

void read_array(int subtask_id, const std::vector<int> &arr) { 
    vector<int >v = arr;
    int n =v.size();
     
    string bits = "";
    
    SegmentTree seg(v);
    build(0,n-1,seg,bits);

    cerr << bits<<endl;
    save_to_floppy(bits);
}
 
int counter = 0;
struct Node{
    int v;
    int l = -1, r = -1;
    int sz = 1;
    int lsz = 0, rsz= 0;
};
vector<Node> cart;
 
void reconstruct(vector<Node>& adj, string& bits){
    bool b1 = bits[counter] == '1';     
    bool b2 = bits[counter+1] == '1';
    counter += 2;
    
    int v = cart.size();
    cart.push_back(Node{});
    if(b1){
        cart[v].l = cart.size();
        reconstruct(adj,bits);
        cart[v].sz += cart[cart[v].l].sz; 
        cart[v].lsz = cart[cart[v].l].sz; 
    }
    if(b2){
        cart[v].r = cart.size();
        reconstruct(adj,bits);
        cart[v].sz += cart[cart[v].r].sz;
        cart[v].rsz = cart[cart[v].r].sz;
    }
}

void buildInd(int v, int l, int r){
    cart[v].v = cart[v].lsz + l;

    if(cart[v].l != -1){
        buildInd(cart[v].l, l, cart[v].v-1);
    }
    if(cart[v].r != -1){
        buildInd(cart[v].r,cart[v].v+1, r);
    }
}

int search(int v, int l, int r){
    if(l <= cart[v].v && cart[v].v <= r){
        return cart[v].v;
    }

    if(cart[v].v < l){
        return search(cart[v].r, l, r);
    }else{ 
        return search(cart[v].l, l, r);
    }
}

std::vector<int> solve_queries(int subtask_id, int N, const std::string &input, const std::vector<int> &a, const std::vector<int> &b) { 
    int n = N; 
    string bits = input;
    B = ceil(log2(n));
    int q = a.size();

    vector<Node> adj;
    reconstruct(adj,bits);
    buildInd(0,0,n-1);

    vector<int> answers(q);

    for(int i = 0; i < q; i++){
        int l, r;
        l = a[i];
        r = b[i];

        answers[i] = search(0,l,r);
    }
    return answers;
}

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