oj.uz

Submission #1059265

# Submission time Handle Problem Language Result Execution time Memory
1059265 2024-08-14T20:00:09 Z shiocan Floppy (RMI20_floppy) C++17
100 / 100
 60 ms 14212 KB 
#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;

#include "floppy.h"

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

    vector<int> s;
    int size = 0;

    void build_tree(int x, int l, int r, const 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(const 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, const 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, const vector<int> & a){
        return query(0, 0, size-1, l, r, a);
    }
} st1, st2;

string res_bits;

void encode(int l, int r, const 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, const vector<int> &v){
    int n = v.size();

    st1.build_tree(v);

    encode(0, n - 1, v);

    save_to_floppy(res_bits);
}

int idx = 0;
vector<int> szl;

void dfs(const 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, const string &bits, const vector<int> & l, const vector<int> &r){
    int q = l.size();

    vector<int> ans;

    szl = vector<int> (n);

    dfs(bits);

    ar = vector<int> (n);

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

    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) {
      |         ~~~~~~~~~~~~~~~~~~~~~^~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 820 KB Output is correct
2 Correct 1 ms 828 KB Output is correct
3 Correct 0 ms 828 KB Output is correct
4 Correct 1 ms 828 KB Output is correct
5 Correct 1 ms 832 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 3768 KB Output is correct
2 Correct 15 ms 3768 KB Output is correct
3 Correct 15 ms 3764 KB Output is correct
4 Correct 14 ms 4020 KB Output is correct
5 Correct 14 ms 3764 KB Output is correct

Subtask #3
72.0 / 72.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 13316 KB Output is correct
2 Correct 57 ms 13180 KB Output is correct
3 Correct 60 ms 13888 KB Output is correct
4 Correct 60 ms 14212 KB Output is correct
5 Correct 57 ms 13232 KB Output is correct