# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1056277 | shiocan | Floppy (RMI20_floppy) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include <cstdlib>
#include <stdlib.h>
using namespace std;
/*
#define cin fin
#define cout fout
string __fname = ""; ifstream fin(__fname + ".in"); ofstream fout(__fname + ".out");
*/
#define ull unsigned long long
#define ll long long
//#define int long long
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
int mod = 1e9 + 7;
//const int inf = 1e18;
const int N = 2e5 + 100;
void read_array( int subtask_id , const std :: vector<int> &v){
int n = v.size();
string bits = "";
for(int i = 0; i < n; i++)
for(int j = i; j < n; j++)
if(v[i] >= v[j])
bits.push_back('1');
else
bits.push_back('0');
save_to_floppy(bits);
}
pii get_idx(int l, int r, int n){
int posl = ((n - l) + n) * (n - (n - l) + 1) / 2;
posl -= (n - l);
int dis = r - l;
int posr = posl + dis;
return {posl, posr};
}
int solve(int l, int r, int n, string bits){
if(l == r){
return l;
}
// cout << l << ' ' << r << '\n';
for(int i = l; i <= r; i++){
if(bits[i] == '0'){
int posl = i - l + 1;
pii idx = get_idx(posl, r, n);
return solve(idx.first, r, n, bits);
}
}
return l;
}
vector<int> solve_queries ( int subtask_id,
int N, const std :: string &bits,
const std :: vector<int> &a,
const std :: vector<int> &b){
int q = a.size();
vector<int> ans;
int n = N;
for(int i = 0; i < q; i++){
int l = a[i], r = b[i];
if(a[i] == b[i]){
ans.push_back(l);
continue;
}
pii idx = get_idx(l, r, n);
int x = solve(idx.first, idx.second, n, bits);
int res = 0;
while(x >= (n - res)){
x -= (n - res);
res++;
}
ans.push_back(res);
}
return ans;
}