#include "bubblesort2.h"
#include<vector>
#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
typedef long long int lld;
typedef std::map<lld,int>::iterator mit;
#define INF 1000000000000000
class FT{
int arr[100000];
int n;
public:
void init(int N){
n=N;
for(int i=0;i<=n;i++){
arr[i]=0;
}
}
int query(int prefix){
prefix++;
int ans=0;
for(;prefix>0;prefix-=(prefix&(-prefix))){
ans+=arr[prefix];
}return ans;
}
void update(int pos){
pos++;
for(;pos<=n;pos+=(pos&(-pos))){
arr[pos]++;
}
}
void update2(int pos){
pos++;
for(;pos<=n;pos+=(pos&(-pos))){
arr[pos]--;
}
}
void print(){
for(int i=0;i<=n;i++){
cout<<arr[i]<<" ";
}cout<<endl;
}
};
FT *F;
int compute(vector<int> v){
int n=v.size();
F->init(n);
pair<int,int> arr[n];
for(int i=0;i<n;i++){
arr[i]=pair<int,int>(v[i],i);
}sort(arr,arr+n);
int prev=n-1;
int ans=0;
for(int i=n-1;i>-1;i--){
if(i==0 || arr[i-1]!=arr[i]){
for(int j=prev;j>=i;j--){
ans=max(ans,F->query(arr[j].second));
}
for(int j=prev;j>=i;j--){
F->update(arr[j].second);
}
prev=i-1;
}
}
return ans;
}
class LP{
lld segtree[4000000];
lld lazy[4000000];
int n;
public:
void build(int a, int b, int node){//cout<<a<<" "<<b<<endl;
lazy[node]=0;
if(a==b){
segtree[node]=-INF;
return;
}
int mid=(a+b)/2;
build(a,mid,2*node);
build(mid+1,b,2*node+1);
segtree[node]=max(segtree[2*node],segtree[2*node+1]);
}
void init(int N){
n=N;
build(0,n-1,1);
}
void extend(int node){
segtree[node]+=lazy[node];
lazy[2*node]+=lazy[node];
lazy[2*node+1]+=lazy[node];
lazy[node]=0;
}
void update(int x, int y, lld val, int a, int b, int node){
if(y<a || b<x)return;
//cout<<x<<" "<<y<<" "<<a<<" "<<b<<" "<<node<<endl;
if(x<=a && b<=y){
lazy[node]+=val;
return;
}extend(node);
int mid=(a+b)/2;
update(x,y,val,a,mid,2*node);
update(x,y,val,mid+1,b,2*node+1);
segtree[node]=max(segtree[2*node]+lazy[2*node],segtree[2*node+1]+lazy[2*node+1]);
}
void Update(int x, int y, int val){
if(x>y)return;
update(x,y,val,0,n-1,1);
}
void set(int pos,lld val,int a, int b, int node){
if(pos<a || pos>b)return;
if(a==b){
segtree[node]=val;
lazy[node]=0;
return;
}extend(node);
int mid=(a+b)/2;
set(pos,val,a,mid,2*node);
set(pos,val,mid+1,b,2*node+1);
segtree[node]=max(segtree[2*node]+lazy[2*node],segtree[2*node+1]+lazy[2*node+1]);
}
void Set(int pos, lld val){
set(pos,val,0,n-1,1);
}
lld query(){
return segtree[1]+lazy[1];
}
void print(){
for(int i=1;i<=2*n;i++){
cout<<segtree[i]<<" "<<lazy[i]<<" ";
}cout<<endl;
}
};
vector<lld> values;
int BSpos(lld x){
int lo,hi;
lo=-1;
hi=values.size();
while(hi-lo>1){
int mid=(hi+lo)/2;
if(values[mid]>x)hi=mid;
else lo=mid;
}
if(values[lo]==x)return lo;
return -1;
}
std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V){
LP *L;
int n=A.size();
L=new LP();
vector<int> a;
int Q=X.size();
for(int i=0;i<n;i++)values.push_back((lld)A[i]*1000000+i);
for(int i=0;i<Q;i++)values.push_back((lld)V[i]*1000000+X[i]);
sort(values.begin(),values.end());
FT *F;
F=new FT();
for(int i=0;i<n;i++)A[i]=A[i]*1000000+i;
for(int i=0;i<Q;i++)V[i]=V[i]*1000000+X[i];
F->init(n+Q);
for(int i=0;i<n;i++){
int pos=BSpos(A[i]);
F->update(pos);
}L->init(n+Q);
for(int i=0;i<n;i++){
int pos=BSpos(A[i]);
//cout<<pos<<endl;
lld questao=F->query(pos)-1;
//cout<<i-questao<<endl;
L->Set(pos,i-questao);
}
//L->print();
//cout<<L->query()<<endl;
for(int i=0;i<Q;i++){
int pos1=BSpos(A[X[i]]);
int pos2=BSpos(V[i]);
F->update2(pos1);
F->update(pos2);
int start,end;
lld query=F->query(pos2)-1;
L->Set(pos1,-INF);
//cout<<X[i]-query<<endl;
L->Set(pos2,X[i]-query);
//cout<<pos1<<" "<<pos2<<endl;
L->Update(pos2+1,n+Q-1,-1);
L->Update(pos1+1,n+Q-1,1);
//cout<<L->query()<<endl;
//L->print();
a.push_back(L->query());
}
return a;
}
Compilation message
bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:186:7: warning: unused variable 'start' [-Wunused-variable]
int start,end;
^~~~~
bubblesort2.cpp:186:13: warning: unused variable 'end' [-Wunused-variable]
int start,end;
^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
9059 ms |
63352 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
9059 ms |
63352 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
81 ms |
64000 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
9059 ms |
63352 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
