#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]);
//printf("!!!!!%d %d %d %d %d %lld : %lld %lld\n", node, tl, tr, l, r, val, tree[node], lazy[node]);
}
void update_change(int node, int tl, int tr, int pos, ll val)
{
busy(node, tl, tr);
if(tl==tr)
{
tree[node]+=val;
return;
}
int mid=tl+tr>>1;
if(pos<=mid) update_change(node*2, tl, mid, pos, val);
else update_change(node*2+1, mid+1, tr, pos, val);
tree[node]=max(tree[node*2], tree[node*2+1]);
}
ll read(int node, int tl, int tr, int pos)
{
busy(node, tl, tr);
if(tl==tr) return tree[node];
int mid=tl+tr>>1;
if(pos<=mid) return read(node*2, tl, mid, pos);
else return read(node*2+1, mid+1, tr, pos);
}
void update_change(int pos, ll val)
{
//printf("!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!%lld\n", read(1, 1, N, pos));
update_change(1, 1, N, pos, val-read(1, 1, N, pos));
}
void debug(int node, int tl, int tr)
{
busy(node, tl, tr);
if(tl==tr)
{
//printf("(%d : %lld) ", tl, tree[node]);
return;
}
int mid=tl+tr>>1;
debug(node*2, tl, mid);
debug(node*2+1, mid+1, tr);
}
ll query()
{
busy(1, 1, N);
return tree[1];
}
};
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<N; i++) printf("%lld ", A[i]); printf("\n");
//seg.debug(1, 1, S); printf("\n");
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());
A[pos]=V[i];
//printf("%lld %lld %lld\n", pos, bef, aft);
//for(j=0; j<N; j++) printf("%lld ", A[j]); printf("\n");
//seg.debug(1, 1, S); printf("\n");
}
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 'void SEG::update_change(int, int, int, int, ll)':
bubblesort2.cpp:61:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=tl+tr>>1;
~~^~~
bubblesort2.cpp: In member function 'll SEG::read(int, int, int, int)':
bubblesort2.cpp:71:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=tl+tr>>1;
~~^~~
bubblesort2.cpp: In member function 'void SEG::debug(int, int, int)':
bubblesort2.cpp:90: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:115: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:116: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:117: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:113:12: warning: unused variable 'j' [-Wunused-variable]
int i, j;
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
380 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
380 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
3316 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
380 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
