Submission #596689

#	Time	Username	Problem	Language	Result	Execution time	Memory
596689		Hacv16	Floppy (RMI20_floppy)	C++17	7.22 / 100	60 ms	6616 KiB

floppy

#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];
 
int findVal(string s){
    int ret = 0;
    for(int i = 0; i < sz(s); i++){
        if(s[i] == '1') ret += (1 << i);
    }
    return ret;
}
 
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;
}
 
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);
 
    if(seg[e].fr > seg[d].fr) seg[p] = seg[e];
    else seg[p] = 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;
    pii esq = query(a, b, e, l, m);
    pii dir = query(a, b, d, m + 1, r);
    
    if(esq.fr > dir.fr) return esq;
    return dir;
}
 
vector<int> solve_queries(int subtask_id, int N, const string &bits, const vector<int>& a, const 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);
 
    for(int i = 0; i < sz(a); i++)
        ans.pb(query(a[i] + 1, b[i] + 1, 1, 1, N).sc - 1);
 
    return ans;
}
 
void read_array(int subtask_id, const 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);
}

Compilation message (stderr)

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 / 7
• Subtask 2: 0.2238296991 / 21
• Subtask 3: 0 / 72