Submission #537199

#	Time	Username	Problem	Language	Result	Execution time	Memory
537199		michao	Bubble Sort 2 (JOI18_bubblesort2)	C++14	0 / 100	30 ms	1428 KiB

bubblesort2

#include <bits/stdc++.h>
//#define int long long
#define mp make_pair
#define pb push_back
#define ld long double
#define pii pair<int,int>
#define sz(x) (int)x.size()
#define piii pair<pii,pii>
#define precise cout<<fixed<<setprecision(10)
#define st first
#define nd second
#define ins insert
#define vi vector<int>
#define BOOST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
const int MAX=1<<20;
const int STALA=1e6;
const int inf=1e9+9;
int LAZY[MAX*4],MAXI[MAX*4];
 
void push(int u){
  LAZY[2*u]+=LAZY[u];
  LAZY[2*u+1]+=LAZY[u];
  MAXI[u]+=LAZY[u];
  LAZY[u]=0;
}
 
void update(int a,int b,int u,int lo,int hi,int c){
  if (b<lo || a>hi)return;
  if (a<=lo && b>=hi){
    LAZY[u]+=c;
    return;
  }
  int mid=(lo+hi)>>1;
  update(a,b,2*u,lo,mid,c);
  update(a,b,2*u+1,mid+1,hi,c);
  MAXI[u]=max(MAXI[2*u]+LAZY[2*u],MAXI[2*u+1]+LAZY[2*u+1]);
}
 
int getmax(int a,int b,int u,int lo,int hi){
  if (b<lo || a>hi)return -inf;
  push(u);
  if (a<=lo && b>=hi)
    return MAXI[u];
  int mid=(lo+hi)>>1;
  int L=getmax(a,b,2*u,lo,mid);
  int R=getmax(a,b,2*u+1,mid+1,hi);
  return max(L,R);
}
void upd(int u,int v,int c){
	update(u,v,1,1,MAX,c);
}

int ran(int u,int v){
	return getmax(u,v,1,1,MAX);
}
int a[MAX],x[MAX],v[MAX];
vi countScans(vi _a,vi _x,vi _v){
	int n=sz(_a);
	int q=sz(_v);
	assert(sz(_v)==sz(_x));
	vector<pii> compress;
	compress.clear();
	for (int i=1;i<=n;i++)a[i]=_a[i-1],compress.pb(mp(a[i],i));
	for (int i=1;i<=q;i++){
		x[i]=_x[i-1];
		v[i]=_v[i-1];
		x[i]++;
		compress.pb(mp(v[i],x[i]));
	}
	sort(compress.begin(),compress.end());
	compress.erase(unique(compress.begin(),compress.end()),compress.end());
	for (int i=1;i<=n;i++){
		a[i]=lower_bound(compress.begin(),compress.end(),mp(a[i],i))-compress.begin()+1;
	}
	
	for (int i=1;i<=q;i++){
		v[i]=lower_bound(compress.begin(),compress.end(),mp(v[i],x[i]))-compress.begin()+1;
	}
	int ile=sz(compress);
	for (int i=1;i<=n;i++){
		upd(a[i],a[i],i); // assert uniqueness
		upd(a[i]+1,ile,-1);
	}
	vi ans;
	ans.clear();
	for (int i=1;i<=q;i++){
		upd(a[x[i]],a[x[i]],-x[i]);
		upd(a[x[i]]+1,ile,1);
		a[x[i]]=v[i];
		upd(a[x[i]],a[x[i]],x[i]);
		upd(a[x[i]]+1,ile,-1);
		ans.pb(ran(1,STALA));
	}
	return ans;
}

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