oj.uz

Submission #596629

# Submission time Handle Problem Language Result Execution time Memory
596629 2022-07-14T22:22:17 Z Hacv16 Floppy (RMI20_floppy) C++17
0 / 100
 58 ms 6536 KB 
#include<bits/stdc++.h>
#include "floppy.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];

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 bits = "";
    vector<int> nv = v;

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

    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) bits += conv(x, LOG);
 
    save_to_floppy(bits);
}
 
void build(ll p, ll l, ll r){
    if(l == r){
        seg[p] = {v[l], l};
        return;
    }

    ll m = (l + r) / 2, 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) / 2, 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 curS = "";
 
        for(int j = i; j < i + LOG; j++) 
            curS += bits[j];
 
        v[j++] = findVal(curS);
    }
 
    build(1, 1, N);
 
    int m = sz(a);
    
    for(int i = 0; i < m; i++){
        ans.pb(query(a[i] + 1, b[i] + 1, 1, 1, N).sc);
    }
 
    assert(sz(ans) == m);

    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 796 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 47 ms 4668 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 58 ms 6536 KB L is too large
2 Halted 0 ms 0 KB -