oj.uz

Submission #596611

# Submission time Handle Problem Language Result Execution time Memory
596611 2022-07-14T21:38:23 Z Hacv16 Floppy (RMI20_floppy) C++17
0 / 100
 63 ms 10088 KB 
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int MAX = 2e6 + 15;
const int LOG = 20;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;

#define pb push_back
#define sz(x) (int) x.size()
#define fr first
#define sc second
#define mp make_pair
#define all(x) x.begin(), x.end()
#define dbg(x) cout << #x << ": " << "[ " << x << " ]\n"

int v[MAX];
pii seg[4 * MAX];

set<int> aux;
map<int, int> comp;

void save_to_floppy(const std::string &bits);

string conv(int x, int log){
    string aux = "";

    for(int i = 0; i < log; i++){
        if(x & (1 << i)) aux += "1";
        else aux += "0";
    }

    return aux;
}

int findVal(string s){
    int ret = 0;

    for(int i = 0; i < sz(s); i++){
        if(s[i] == '1') ret += (1 << i);
    }

    return ret;
}

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

    for(auto x : nv) aux.insert(x);
    
    int nval = 0;
    for(auto x : aux)
        comp[x] = nval++;

    for(int i = 0; i < sz(nv); i++){
        nv[i] = comp[nv[i]];
    }

    for(auto x : nv) s += conv(x, LOG);

    save_to_floppy(s);    
}

void build(int p, int l, int r){
    if(l == r){
        seg[p] = {v[l], l};
        return;
    }

    int m = (l + r) >> 1, e = 2 * p, d = e + 1;
    build(e, l, m);
    build(d, m + 1, r);

    seg[p] = max(seg[e], seg[d]);
}

pii query(ll a, ll b, ll p, ll l, ll r){
    if(b < l || a > r) return {-INF, -INF}; //no nulo
    if(a <= l && r <= b) return seg[p];
        
    ll m = (l + r) >> 1, e = 2 * p, d = e + 1;
    return max(query(a, b, e, l, m), query(a, b, d, m + 1, r));
}

vector<int> solve_queries(int subtask_id, int N, const std::string &bits, const std::vector<int> &a, const std::vector<int> &b){
    vector<int> ans;
    
    for(int i = 0, j = 1; i < sz(bits); i += LOG){
        string aux = "";

        for(int j = i; j < i + LOG; j++) 
            aux += bits[j];

        v[j++] = findVal(aux);
    }

    build(1, 1, N);

    int m = sz(a);
    
    for(int i = 0; i < m; i++){
        ans.pb(query(a[i], b[i], 1, 1, N).sc);
    }

    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
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 900 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 45 ms 5356 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 72.0

# Verdict Execution time Memory Grader output
1 Incorrect 63 ms 10088 KB L is too large
2 Halted 0 ms 0 KB -