#include<bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
using namespace std;
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<pl> vpl;
typedef vector<ld> vld;
typedef pair<ld, ld> pld;
//typedef tree<ll, null_type, less_equal<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
template<typename T>
ostream &operator<<(ostream &os, vector<T> &a) {
os << "[";
for (int i = 0; i < ll(a.size()); i++) { os << a[i] << ((i != ll(a.size() - 1) ? " " : "")); }
os << "]\n";
return os;
}
#define all(x) x.begin(),x.end()
#define YES out("YES")
#define NO out("NO")
#define out(x){cout << x << "\n"; return;}
#define GLHF ios_base::sync_with_stdio(false); cin.tie(NULL)
#define print(x){for(auto ait:x) cout << ait << " "; cout << "\n";}
#define pb push_back
#define umap unordered_map
#include "floppy.h"
//#include "grader.cpp"
string to_base(int n,int b){
string ans;
while(n){
ans+=to_string(n%b);
n/=b;
}
reverse(all(ans));
return ans;
}
void read_array(int subtask_id, const vi &v) {
vi so(v);
sort(all(so));
map<int,int>conv;
int n=v.size();
for(int i=0; i<n; i++)
conv[so[i]]=i;
string ans;
for(int i=0; i<n; i++){
string s=to_base(conv[v[i]],2);
while(s.size()!=14)
s='0'+s;
ans+=s;
}
save_to_floppy(ans);
}
struct seg{
int sz=1;
vpl t;
vl a;
seg(vl A){
int n=A.size();
while(sz<=2*n)
sz*=2;
t.resize(sz);
a.resize(n);
}
void update(int i,int v){
a[i]=v;
i+=sz/2;
t[i]={v,i-sz/2};
while(i){
pl p1=t[i],p2=t[i^1];
pl ans={max(p1.first,p2.first),-1};
if(p1.first>p2.first)
ans.second=p1.second;
else
ans.second=p2.second;
t[i/2]=ans;
i/=2;
}
}
int query(int l,int r){
int ans=l;
for(l+=sz/2,r+=sz/2 +1; l<r; l/=2,r/=2){
if(l&1){
if(t[l].first>a[ans])
ans=t[l].second;
l++;
}
if(r&1){
r--;
if(t[r].first>a[ans])
ans=t[r].second;
}
}
return ans;
}
};
std::vector<int> solve_queries(int subtask_id, int n,
const std::string &bits,
const std::vector<int> &l, const std::vector<int> &r){
vl a(n);
for(int i=0; i<n; i++)
a[i]=stoi(bits.substr(14*i,14),0,2);
seg s(a);
vi ans;
for(int i=0; i<n; i++)
s.update(i,a[i]);
for(int i=0; i<l.size(); i++)
ans.pb(s.query(l[i],r[i]));
return ans;
}
Compilation message
floppy.cpp: In function 'std::vector<int> solve_queries(int, int, const string&, const std::vector<int>&, const std::vector<int>&)':
floppy.cpp:119:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
119 | for(int i=0; i<l.size(); i++)
| ~^~~~~~~~~
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 |
Correct |
3 ms |
808 KB |
Output is correct |
| 2 |
Correct |
3 ms |
780 KB |
Output is correct |
| 3 |
Correct |
3 ms |
788 KB |
Output is correct |
| 4 |
Correct |
3 ms |
780 KB |
Output is correct |
| 5 |
Correct |
3 ms |
780 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
49 ms |
4972 KB |
Output is correct |
| 2 |
Correct |
50 ms |
5224 KB |
Output is correct |
| 3 |
Correct |
48 ms |
4944 KB |
Output is correct |
| 4 |
Correct |
48 ms |
5144 KB |
Output is correct |
| 5 |
Correct |
49 ms |
5012 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1088 ms |
5764 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
