Submission #646746

#	Time	Username	Problem	Language	Result	Execution time	Memory
646746		TwoFourFive	Floppy (RMI20_floppy)	C++14	0 / 100	92 ms	10404 KiB

floppy

#include <stdlib.h>
#include <string.h>

#include "floppy.h"

#include <bits/stdc++.h>
using namespace std;
typedef int ll;
typedef vector<ll> vl;
const ll INF = 100005, LONGBOI = 100000000005, BITSMAX = 16;

ll maxpos=0;
map<ll, ll> mp;

string ToStr(ll x){
    string ans="";
    for(int i=BITSMAX-1; i >= 0; i--){
        ans += '0' + ((x>>i)&1);
    }
    return ans;
}

ll FromStr(string s){
    ll x = 0;
    for(int i=0; i < BITSMAX; i++){
        x <<= 1;
        x += s[i]-'0';
    }
    return x;
}

void BuildTree(ll we, ll l, ll r, vl &t, vl &a){
    maxpos = max(maxpos, we);
    if(l == r) { t[we] = a[l]; return; }
    ll tm = (l+r)/2;
    BuildTree(2*we+1, l, tm, t, a);
    BuildTree(2*we+2, tm+1, r, t, a);
    t[we] = max(t[2*we+1], t[2*we+2]);
    return;
}

ll GetMax(ll we, ll l, ll r, ll tl, ll tr, vl &t){
    if(l > tr || r < tl) return -LONGBOI;
    if(tl <= l && r <= tr) return t[we];

    ll tm = (l+r)/2;
    return max(GetMax(2*we+1, l, tm, tl, tr, t), GetMax(2*we+2, tm+1, r, tl, tr, t));
}

void read_array(int subtask_id, const vector<int> &v) {
    vl vec;
    map<ll, ll> newNums;
    ll n = v.size();
    for(auto x : v) { vec.push_back(x); }
    sort(vec.begin(), vec.end());
    for(auto x : vec){
        if(newNums.count(x) == false){
            newNums[x] = newNums.size();
        }
    }
    vl t(4*(n+5));
    vl a(n+5);
    for(int i=0; i < n; i++) { a[i+1] = newNums[v[i]]; mp[a[i+1]] = i; }
    /*for(int i=1; i <= n; i++) cout << a[i] << " ";
    cout << endl;
    cout << "map" << endl;
    for(auto x : mp) { cout << x.first << " " << x.second << endl; }
    cout << endl;*/
    BuildTree(0, 1, n, t, a);
    string bits = "";
    //for(int i=0; i <= maxpos; i++) { cout << "i = " << i << " t[i] = " << t[i] << endl; }
    for(int i=0; i <= maxpos; i++) { bits += ToStr(t[i]); /*cout << bits << " " << ToStr(t[i]) << endl;*/ }
    save_to_floppy(bits);
}

vector<int> solve_queries(int subtask_id, int N, const string &bits, const vector<int> &a, const vector<int> &b) {
    vl t(4*(N+5));
    /*for(auto x : a) cout << x << " ";
    cout << endl;
    for(auto x : b) cout << x << " ";
    cout << endl;*/
    for(int i=0; i <= maxpos; i++) { t[i] = FromStr(bits.substr(i*BITSMAX, (i+1)*BITSMAX)); /*cout << i*BITSMAX << " " << (i+1)*BITSMAX << endl;*/ }
    //for(int i=0; i <= maxpos; i++) { cout << "i = " << i << " t[i] = " << t[i] << endl; }

    vl ans;
    ll m  = a.size();
    for(int i=0; i < m; i++){
        //cout << GetMax(0, 1, N, a[i]+1, b[i]+1, t) << endl;
        ans.push_back(mp[GetMax(0, 1, N, a[i]+1, b[i]+1, t)]);
    }
    /*for(auto x : ans) cout << x << " ";
    cout << endl;*/

    //vl ans = {0, 0, 0, 0, 1, 2, 2, 2, 2, 3};
    return ans;
}

Compilation message (stderr)

floppy.cpp:10:34: warning: overflow in conversion from 'long int' to 'll' {aka 'int'} changes value from '100000000005' to '1215752197' [-Woverflow]
   10 | const ll INF = 100005, LONGBOI = 100000000005, BITSMAX = 16;
      |                                  ^~~~~~~~~~~~
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 / 7
• Subtask 2: 0 / 21
• Subtask 3: 0 / 72