#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
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) {
| ~~~~~~~~~~~~~~~~~~~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
800 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
20 ms |
3072 KB |
L is too large |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
92 ms |
10404 KB |
L is too large |
| 2 |
Halted |
0 ms |
0 KB |
- |
