Submission #1059252

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1059252	2024-08-14T19:49:08 Z	shiocan	Floppy (RMI20_floppy)	C++17	Compilation error	0 ms	0 KB

floppy

#include <bits/stdc++.h>
#include <cstdlib>
#include <stdlib.h>
using namespace std;
/*
    #define cin fin
    #define cout fout
    string __fname = ""; ifstream fin(__fname + ".in"); ofstream fout(__fname + ".out");
*/

#define ull unsigned long long 
#define ll long long
#define int long long
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
int mod = 1e9 + 7; 
const int inf = 1e18;
const int N = 4e4 + 100;

void save_floppy(string bits);

struct segtree{
    struct item{
        int val = 0;
        int lazy = 0;
    };

    // const item DEFAULT = {0, 1, 0};

    vector<int> s;
    int size = 0;

    // void apply(int x, int val){
    //     // s[x].val += val;
    //     // s[x].lazy += val;
    // }
    
    // void push(int x){
    //     // if(s[x].lazy != 0){
    //     //     apply(2 * x + 1, s[x].lazy);
    //     //     apply(2 * x + 2, s[x].lazy);
    //     //     s[x].lazy = 0;
    //     // }
    // }

    // void merge(int x, vector<int> & a){
    //     if(a[s[2 * x + 1]] > a[s[2 * x + 2]])
    //         s[x] = s[2 * x + 1];
    //     else    
    //         s[x] = s[2 * x + 2];
    // }

    void build_tree(int x, int l, int r, vector<int> & a){
        if(l == r){
            s[x] = l;
            return;
        }

        int mid = (l + r) >> 1;

        build_tree(2 * x + 1, l, mid, a);
        build_tree(2 * x + 2, mid+1, r, a);
        
        s[x] = (a[s[2 * x + 1]] > a[s[2 * x + 2]]) ? s[2 * x + 1] : s[2 * x + 2];
    }

    void build_tree(vector<int> & a){
        size = a.size();
        s.resize(4 * size);

        build_tree(0, 0, size - 1, a);
    }

    int query(int x, int lx, int rx, int l, int r, vector<int> & a){
        if(l > r)
            return -1;
        if(l <= lx && rx <= r)
            return s[x];

        // push(x);

        int mid = (lx + rx) >> 1;

        int s1 = query(2 * x + 1, lx, mid, l, min(r, mid), a);
        int s2 = query(2 * x + 2, mid+1, rx, max(l, mid+1), r, a);

        if(s1 == -1 && s2 == s1)
            return -1;
        if(s1 == -1)
            return s2;
        if(s2 == -1)
            return s1;

        if(a[s1] > a[s2])
            return s1;
        return s2;
    }   
    int query(int l, int r, vector<int> & a){
        return query(0, 0, size-1, l, r, a);
    }
} st1, st2;

string res_bits;

void encode(int l, int r, vector<int> & a){
    if(l > r)
        return;

    if(l == r){
        res_bits += "00";
        return;
    }

    int mid = st1.query(l, r, a);

    if(mid == l){
        res_bits += "01";
        encode(mid + 1, r, a);
    }
    else if(mid == r){
        res_bits += "10";
        encode(l, mid - 1, a);
    }
    else{
        res_bits += "11";
        encode(l, mid - 1, a);
        encode(mid + 1, r, a);
    }
}

void read_array(int subtask_id, vector<int> &v){
    int n = v.size();

    st1.build_tree(v);

    encode(0, n - 1, v);

    save_floppy(res_bits);
}

int idx = 0;
vector<int> szl;

void dfs(string bits){
    bool l = (bits[2 * idx] == '1'), r = (bits[2 * idx + 1] == '1');
    if(!l && !r)
        return;

    int old_idx = idx;
    idx++;
    dfs(bits);

    if(!l)
        return;
    if(!r){
        szl[old_idx] = idx - old_idx; 
        return;
    }

    szl[old_idx] = idx - old_idx;
    //old_idx = idx;
    idx++;
    dfs(bits);

    //
}

vector<int> ar;
int val;

void decode(int idx, int l, int r){
    if(l > r)
        return;
    if(l == r){
        ar[l] = val;
        val--;
        return;
    }

    int mid = l + szl[idx];
    ar[mid] = val;
    val--;

    decode(idx + 1, l, mid - 1);
    decode(idx + szl[idx] + 1, mid + 1, r);
}   


vector<int> solve_queries(int sub, int n, string bits, vector<int> l, vector<int> r){
    int q = l.size();

    vector<int> ans;

    szl = vector<int> (n);

    dfs(bits);

    // for(auto i : szl)
    //     cout << i << ' ';
    // cout << '\n';

    ar = vector<int> (n);

    val = n - 1;
    decode(0, 0, n - 1);

    // for(auto i : ar)
    //     cout << i << ' ';
    // cout << '\n';

    st2.build_tree(ar);

    for(int i = 0; i < q; i++)
        ans.push_back(st2.query(l[i], r[i], ar));

    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) {
      |         ~~~~~~~~~~~~~~~~~~~~~^~~~
/usr/bin/ld: /tmp/ccGfQTg4.o: in function `read_array(long long, std::vector<long long, std::allocator<long long> >&)':
floppy.cpp:(.text+0x2480): undefined reference to `save_floppy(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >)'
/usr/bin/ld: /tmp/ccdLA6N1.o: in function `run2()':
stub.cpp:(.text+0x698): undefined reference to `solve_queries(int, int, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&, std::vector<int, std::allocator<int> > const&, std::vector<int, std::allocator<int> > const&)'
/usr/bin/ld: /tmp/ccdLA6N1.o: in function `run1()':
stub.cpp:(.text+0xb1d): undefined reference to `read_array(int, std::vector<int, std::allocator<int> > const&)'
collect2: error: ld returned 1 exit status