Submission #448237

#	Time	Username	Problem	Language	Result	Execution time	Memory
448237		CSQ31	Bubble Sort 2 (JOI18_bubblesort2)	C++17	100 / 100	2306 ms	136760 KiB

bubblesort2

#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define sz(a) (int)(a.size())
#define all(a) a.begin(),a.end()
typedef pair<int,int> pii;
const int MAXN = 1e6+1;
vector<int>t(4*MAXN,-1e9),lazy(4*MAXN,0);
vector<set<int,greater<int>>>s(MAXN);
vector<int>f(MAXN);
void upd1(int v,int l,int r,int pos,int val){
	if(l > r)return;
	if(l==r){
		//lazy[v] = 0;
		if(val < 0)s[pos].erase(-val);
		else s[pos].insert(val);
		if(!s[pos].empty())t[v] = *s[pos].begin() - f[pos] + lazy[v];
		else t[v] = -1e9;
		return;
	}
	int tm=(l+r)/2;
	if(pos<=tm)upd1(2*v,l,tm,pos,val);
	else upd1(2*v+1,tm+1,r,pos,val);
	t[v] = max(t[2*v],t[2*v+1]) + lazy[v];
}
void upd2(int v,int l,int r,int tl,int tr,int val){
	if(l > r)return;
	if(l==tl && r == tr){
		lazy[v]+=val;
		t[v]+=val;
		return;
	}
	int tm = (tl+tr)/2;
	upd2(2*v,l,min(r,tm),tl,tm,val);
	upd2(2*v+1,max(l,tm+1),r,tm+1,tr,val);
	t[v] = max(t[2*v],t[2*v+1]) + lazy[v];
}
vector<int> countScans(vector<int> a,vector<int> x,vector<int>v){
	int q=sz(x);
	int n = sz(a);
	vector<int> answer(q);
	vector<int>b;
	for(int i=0;i<n;i++)b.push_back(a[i]);
	for(int i=0;i<q;i++)b.push_back(v[i]);
	sort(all(b));
	b.resize(unique(all(b))-b.begin());
	int m = sz(b);
	for(int i=0;i<n;i++)a[i] = lower_bound(all(b),a[i])-b.begin()+1;
	for(int i=0;i<q;i++)v[i] = lower_bound(all(b),v[i])-b.begin()+1;
	for(int i=0;i<n;i++)f[a[i]]++;
	for(int i=1;i<=m;i++)f[i]+=f[i-1];
	for(int i=0;i<n;i++)upd1(1,1,m,a[i],i+1);
	for(int i=0;i<q;i++){
		upd1(1,1,m,a[x[i]],-x[i]-1);
		upd1(1,1,m,v[i],x[i]+1);
		upd2(1,a[x[i]],m,1,m,1);
		upd2(1,v[i],m,1,m,-1);
		a[x[i]] = v[i];
		answer[i] = t[1];
	}
	return answer;
}

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