| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 470659 | 2021-09-04T18:16:54 Z | Carmel_Ab1 | Floppy (RMI20_floppy) | C++17 | 0 ms | 0 KB |
#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"
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_string(conv[v[i]]);
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]={i,v};
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;
}
}
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;
}
};
vi solve_queries(int subtask_id, int n,string &bits,const vi &l, const vi &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;
}