#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 5e5;
const int MAXQ = 5e5;
const ll NEGINF = -1e17;
int N, Q, S;
vector<ll> A, X, V, comp;
vector<int> ans;
ll getcomp(ll x)
{
return lower_bound(comp.begin(), comp.end(), x)-comp.begin()+1;
}
struct SEG
{
int N;
vector<ll> tree, lazy;
SEG(int N) : N(N), tree(4*N+10, NEGINF), lazy(4*N+10, 0ll) {}
void busy(int node, int tl, int tr)
{
if(lazy[node]==0) return;
tree[node]+=lazy[node];
if(tl!=tr) lazy[node*2]+=lazy[node], lazy[node*2+1]=lazy[node];
lazy[node]=0;
}
void update_range(int node, int tl, int tr, int l, int r, ll val)
{
busy(node, tl, tr);
if(tr<l || r<tl) return;
if(l<=tl && tr<=r)
{
tree[node]+=val;
if(tl!=tr) lazy[node*2]+=val, lazy[node*2+1]+=val;
return;
}
int mid=tl+tr>>1;
update_range(node*2, tl, mid, l, r, val);
update_range(node*2+1, mid+1, tr, l, r, val);
tree[node]=max(tree[node*2], tree[node*2+1]);
}
ll query(int node, int tl, int tr, int l, int r)
{
busy(node, tl, tr);
if(tr<l || r<tl) return NEGINF;
if(l<=tl && tr<=r) return tree[node];
int mid=tl+tr>>1;
return max(query(node*2, tl, mid, l, r), query(node*2+1, mid+1, tr, l, r));
}
void update_change(int pos, ll val)
{
update_range(1, 1, N, pos, pos, val-query(1, 1, N, pos, pos));
}
};
struct BIT
{
int N;
vector<ll> tree;
BIT(int N) : N(N), tree(N+10, 0ll) {}
void update(int i, int val) { for(; i<=N; i+=(i&-i)) tree[i]+=val; }
ll query(int i) { ll ret=0; for(; i>0; i-=(i&-i)) ret+=tree[i]; return ret; }
};
vector<int> countScans(vector<int> a, vector<int> x, vector<int> v)
{
int i, j;
N=a.size(); Q=x.size();
for(i=0; i<a.size(); i++) A.push_back((ll)a[i]*N+i), comp.push_back((ll)a[i]*N+i);
for(i=0; i<x.size(); i++) V.push_back((ll)v[i]*N+x[i]), comp.push_back((ll)v[i]*N+x[i]);
for(i=0; i<v.size(); i++) X.push_back((ll)x[i]);
sort(comp.begin(), comp.end());
comp.erase(unique(comp.begin(), comp.end()), comp.end());
S=comp.size();
for(i=0; i<N; i++) A[i]=getcomp(A[i]);
for(i=0; i<Q; i++) V[i]=getcomp(V[i]);
SEG seg(S);
BIT bit(S);
for(i=0; i<N; i++) bit.update(A[i], 1);
for(i=0; i<N; i++) seg.update_change(A[i], i-bit.query(A[i]-1));
for(i=0; i<Q; i++)
{
ll pos=X[i], bef=A[pos], aft=V[i];
bit.update(bef, -1);
bit.update(aft, 1);
if(bef<aft)
{
if(bef+1<=aft-1) seg.update_range(1, 1, S, bef+1, aft-1, 1);
seg.update_change(bef, NEGINF);
seg.update_change(aft, pos-bit.query(aft-1));
}
else
{
if(aft+1<=bef-1) seg.update_range(1, 1, S, aft+1, bef-1, -1);
seg.update_change(bef, NEGINF);
seg.update_change(aft, pos-bit.query(aft-1));
}
ans.push_back(seg.query(1, 1, S, 1, S));
A[pos]=V[i];
}
return ans;
}
Compilation message
bubblesort2.cpp: In member function 'void SEG::update_range(int, int, int, int, int, ll)':
bubblesort2.cpp:46:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=tl+tr>>1;
~~^~~
bubblesort2.cpp: In member function 'll SEG::query(int, int, int, int, int)':
bubblesort2.cpp:57:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=tl+tr>>1;
~~^~~
bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:80:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0; i<a.size(); i++) A.push_back((ll)a[i]*N+i), comp.push_back((ll)a[i]*N+i);
~^~~~~~~~~
bubblesort2.cpp:81:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0; i<x.size(); i++) V.push_back((ll)v[i]*N+x[i]), comp.push_back((ll)v[i]*N+x[i]);
~^~~~~~~~~
bubblesort2.cpp:82:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0; i<v.size(); i++) X.push_back((ll)x[i]);
~^~~~~~~~~
bubblesort2.cpp:78:12: warning: unused variable 'j' [-Wunused-variable]
int i, j;
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
508 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
508 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
30 ms |
3316 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
508 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
