oj.uz

Submission #596700

# Submission time Handle Problem Language Result Execution time Memory
596700 2022-07-15T01:33:20 Z Hacv16 Floppy (RMI20_floppy) C++17
28 / 100
 50 ms 6476 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 = 14;
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);
 
    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 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 = "";
 
    set<int> aux;
    map<int, int> comp;
 
    for(auto x : v) aux.insert(x);
    
    int nval = 0;
    for(auto x : aux)
        comp[x] = nval++;
 
    for(auto x : v)
        bits += conv(comp[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 796 KB Output is correct
2 Correct 2 ms 800 KB Output is correct
3 Correct 2 ms 800 KB Output is correct
4 Correct 3 ms 800 KB Output is correct
5 Correct 2 ms 800 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 4408 KB Output is correct
2 Correct 45 ms 4340 KB Output is correct
3 Correct 44 ms 4308 KB Output is correct
4 Correct 40 ms 4412 KB Output is correct
5 Correct 38 ms 4376 KB Output is correct

Subtask #3
0.0 / 72.0

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