oj.uz

Submission #596689

# Submission time Handle Problem Language Result Execution time Memory
596689 2022-07-15T01:25:59 Z Hacv16 Floppy (RMI20_floppy) C++17
7.22383 / 100
 60 ms 6616 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];
 
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

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 2 ms 808 KB Output is correct
2 Correct 3 ms 804 KB Output is correct
3 Correct 3 ms 820 KB Output is correct
4 Correct 3 ms 816 KB Output is correct
5 Correct 4 ms 824 KB Output is correct

Subtask #2
0.2238296991 / 21.0

# Verdict Execution time Memory Grader output
1 Partially correct 47 ms 4688 KB Partially correct
2 Partially correct 51 ms 5156 KB Partially correct
3 Partially correct 53 ms 5196 KB Partially correct
4 Partially correct 46 ms 5132 KB Partially correct
5 Partially correct 53 ms 5072 KB Partially correct

Subtask #3
0.0 / 72.0

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