Submission #851147

#	Time	Username	Problem	Language	Result	Execution time	Memory
851147		MrM7md	Bubble Sort 2 (JOI18_bubblesort2)	C++17	0 / 100	9005 ms	13812 KiB

bubblesort2

#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
// #define int long long
#define F first
#define S second
#define pb push_back
#define all(a) a.begin(),a.end()
const int N=2e5 + 3;
const int MOD=1e9+7;
const int off=(1<<20);

int mx[off*2],mn[off*2];
void upd(int x,int v){
	x+=off;
	mx[x]=v;
	mn[x]=v;
	while(x/=2){
		mx[x]=max(mx[x*2],mx[x*2+1]);
		if(mn[x*2]==0)mn[x*2]=INT_MAX;
		if(mn[x*2+1]==0)mn[x*2+1]=INT_MAX;
		mn[x]=min(mn[x*2],mn[x*2+1]);
	}
}
int get(int x,int l,int r,int st,int en,int val){
	if(r<st||l>en)return 0;
   if(l>=st&&r<=en){
      if(mn[x]>val)
      return r-l+1;
      if(mx[x]<=val)
      return 0;
   }
   int mid=(l+r)/2;
   return (get(x*2,l,mid,st,en,val)+get(x*2+1,mid+1,r,st,en,val));
}

std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V){
	int q=X.size(),n=A.size();
	int dis[n];
   multiset<int>ms;
	vector<int>ans;
   for(int i=0;i<n;i++){
      int x=A[i];
      upd(i,x);
      dis[i]=get(1,1,off-1,0,i,x);
      ms.insert(dis[i]);
   }
   for(int j=0;j<q;j++){
      int x=X[j],v=V[j];

      upd(x,v);
      dis[x]=get(1,1,off-1,0,x,v);
      ms.insert(dis[x]);
      for(int i=x;i<n;i++){
         if(A[x]<=A[i]&&v>A[i]){
            ms.erase(ms.find(dis[i]));
            dis[i]++;
            // cout<<dis[i]<<endl;
            ms.insert(dis[i]);
         }
         if(A[x]>A[i]&&v<=A[i]){
            ms.erase(ms.find(dis[i]));
            dis[i]--;
            ms.insert(dis[i]);
         }
      }
      A[x]=v;
      ans.pb(*ms.rbegin());
   }
	return ans;
}

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