#include "bubblesort2.h"
#define here cerr<<"===========================================\n"
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#define ld double
#define ll long long
#define llinf 100000000000000000LL // 10^17
#define pb push_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define sz(a) (ll)(a.size())
#define all(a) a.begin(),a.end()
#define ceri(a,l,r) {for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
#define daj_mi_malo_vremena ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);
using namespace std;
using namespace __gnu_pbds;
typedef tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
#define maxn 2000005
ll n,q;
pll a[maxn];
ll b[maxn];
ll x[maxn];
ll v[maxn];
ll t[4*maxn];
ll lazy[4*maxn];
void push(ll v,ll tl,ll tr){
t[v]+=lazy[v];
if(tl<tr){
lazy[2*v]+=lazy[v];
lazy[2*v+1]+=lazy[v];
}
lazy[v] = 0;
}
void upd(ll v,ll tl,ll tr,ll l,ll r,ll x){
push(v,tl,tr);
if(l>r) return;
if(tl==l&&tr==r){
lazy[v]+=x;
push(v,tl,tr);
return;
}
ll mid = (tl+tr)/2;
upd(2*v,tl,mid,l,min(mid,r),x);
upd(2*v+1,mid+1,tr,max(mid+1,l),r,x);
t[v] = max(t[2*v],t[2*v+1]);
}
ll get(ll v,ll tl,ll tr,ll l,ll r){
push(v,tl,tr);
if(l>r) return 0;
if(tl==l&&tr==r) return t[v];
ll mid = (tl+tr)/2;
return max(get(2*v,tl,mid,l,min(mid,r)),get(2*v+1,mid+1,tr,max(mid+1,l),r));
}
void init(ll v,ll tl,ll tr){
if(tl==tr){
t[v] = b[tl];
return;
}
ll mid = (tl+tr)/2;
init(2*v,tl,mid);
init(2*v+1,mid+1,tr);
t[v] = max(t[2*v],t[2*v+1]);
}
vector<int> countScans(vector<int> A,vector<int> X,vector<int> V){
n = sz(A);
q = sz(X);
set<pll> s;
map<pll,ll> mp;
for(ll i = 1;i<=n;i++) a[i] = {A[i-1],i};
for(ll i = 1;i<=q;i++) x[i] = X[i-1]+1;
for(ll i = 1;i<=q;i++) v[i] = V[i-1];
for(ll i = 1;i<=n;i++) s.insert(a[i]);
for(ll i = 1;i<=q;i++) s.insert({v[i],x[i]});
ll it = 1;
ll m = it-1;
ll mx = maxn-5;
for(pll p : s) mp[p] = it++;
for(ll i = 1;i<=n;i++) a[i].fi = mp[a[i]];
for(ll i = 1;i<=n;i++) b[a[i].fi] = i;
for(ll i = 1;i<=q;i++) v[i] = mp[{v[i],x[i]}];
init(1,1,mx);
for(ll i = 1;i<=n;i++) upd(1,1,mx,a[i].fi+1,mx,-1);
vector<int> ans;
for(ll j = 1;j<=q;j++){
ll i = x[j];
ll val = v[j];
ll z = a[i].fi;
upd(1,1,mx,z+1,mx,1);
upd(1,1,mx,z,z,-i);
upd(1,1,mx,val,val,i);
upd(1,1,mx,val+1,mx,-1);
ans.pb(t[1]-1);
}
return ans;
}
/*
4 2
1 2 3 4
0 3
2 1
*/
Compilation message
bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:82:8: warning: unused variable 'm' [-Wunused-variable]
82 | ll m = it-1;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
25 ms |
33364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
25 ms |
33364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
79 ms |
38484 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
25 ms |
33364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
