Submission #1274776

#	Time	Username	Problem	Language	Result	Execution time	Memory
1274776		uzukishinobu	Bubble Sort 2 (JOI18_bubblesort2)	C++20	100 / 100	1252 ms	38392 KiB

bubblesort2

#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;
int a,q;
vector <pair<int,int>> v;
int f[4000005];
int lazy[4000005];
void update(int id,int l,int r,int x,int y,int val){
    if (x>r || y<l){
        return;
    }
    if (l>=x && y>=r){
        f[id]+=val;
        lazy[id]+=val;
        return;
    }
    int mid=(l+r)/2;
    update(id*2,l,mid,x,y,val);
    update(id*2+1,mid+1,r,x,y,val);
    f[id]=max(f[id*2],f[id*2+1])+lazy[id];
}

vector<int> countScans(vector<int> A,vector<int> X,vector<int> V){
	 a=A.size();
	 q=X.size();
	 for (int i=0;i<a;i++){
          v.push_back({A[i],i});
	 }
	 for (int i=0;i<q;i++){
          v.push_back({V[i],X[i]});
	 }
	 sort(v.begin(),v.end());
	 v.erase(unique(v.begin(),v.end()),v.end());
	 int n=v.size();
	 vector <int> res(q);
	 for (int i=0;i<a;i++){
          int pos=lower_bound(v.begin(),v.end(),make_pair(A[i],i))-v.begin()+1;
          update(1,1,n,pos,pos,i);
          update(1,1,n,pos+1,n,-1);
	 }
	 for (int i=0;i<q;i++){
          int x=X[i];
          int y=V[i];
          int pos=lower_bound(v.begin(),v.end(),make_pair(A[x],x))-v.begin()+1;
          update(1,1,n,pos,pos,-x);
          update(1,1,n,pos+1,n,1);

          A[x]=y;
          pos=lower_bound(v.begin(),v.end(),make_pair(A[x],x))-v.begin()+1;
          update(1,1,n,pos,pos,x);
          update(1,1,n,pos+1,n,-1);
          res[i]=f[1];
//          cout << res << "\n";
	 }
	 return res;
}

• Subtask 1: 17 / 17
• Subtask 2: 21 / 21
• Subtask 3: 22 / 22
• Subtask 4: 40 / 40