Submission #285137

#	Time	Username	Problem	Language	Result	Execution time	Memory
285137		Pyqe	Bubble Sort 2 (JOI18_bubblesort2)	C++14	100 / 100	3813 ms	129084 KiB

bubblesort2

#include "bubblesort2.h"
#include <bits/stdc++.h>

using namespace std;

#define mp make_pair
#define fr first
#define sc second

int n,inf=1e9;
pair<int,int> as[1000069];

struct segtree
{
	int l,r,mx,lz;
	segtree *p[2];
	
	void bd(int lh,int rh)
	{
		l=lh;
		r=rh;
		mx=-inf;
		lz=0;
		if(l==r);
		else
		{
			int ii,md=(l+r)/2;
			
			for(ii=0;ii<2;ii++)
			{
				p[ii]=new segtree;
				p[ii]->bd(!ii?l:md+1,!ii?md:r);
			}
		}
	}
	void blc()
	{
		int ii;
		
		for(ii=0;ii<2;ii++)
		{
			p[ii]->mx+=lz;
			p[ii]->lz+=lz;
		}
		lz=0;
	}
	void ud(int lh,int rh,int w)
	{
		if(l>rh||r<lh);
		else if(l>=lh&&r<=rh)
		{
			mx+=w;
			lz+=w;
		}
		else
		{
			int ii;
			
			blc();
			for(ii=0;ii<2;ii++)
			{
				p[ii]->ud(lh,rh,w);
			}
			mx=max(p[0]->mx,p[1]->mx);
		}
	}
	void ins(int x)
	{
		if(l>x||r<x);
		else if(l>=x&&r<=x)
		{
			mx=lz-(n-1-as[l].sc);
		}
		else
		{
			int ii;
			
			blc();
			for(ii=0;ii<2;ii++)
			{
				p[ii]->ins(x);
			}
			mx=max(p[0]->mx,p[1]->mx);
		}
	}
	void ers(int x)
	{
		if(l>x||r<x);
		else if(l>=x&&r<=x)
		{
			mx=-inf;
		}
		else
		{
			int ii;
			
			blc();
			for(ii=0;ii<2;ii++)
			{
				p[ii]->ers(x);
			}
			mx=max(p[0]->mx,p[1]->mx);
		}
	}
}
sg;

vector<int> countScans(vector<int> a,vector<int> qp,vector<int> qw)
{
	int t=qp.size(),rr,i,k,w;
	vector<int> sq;
	
	n=a.size();
	for(i=0;i<n;i++)
	{
		as[i]={a[i],i};
	}
	for(rr=0;rr<t;rr++)
	{
		k=qp[rr];
		w=qw[rr];
		as[n+rr]={w,k};
	}
	sort(as,as+n+t);
	sg.bd(0,n+t-1);
	for(i=0;i<n;i++)
	{
		sg.ins(lower_bound(as,as+n+t,mp(a[i],i))-as);
		sg.ud(0,lower_bound(as,as+n+t,mp(a[i],0))-as-1,1);
	}
	for(rr=0;rr<t;rr++)
	{
		k=qp[rr];
		w=qw[rr];
		sg.ers(lower_bound(as,as+n+t,mp(a[k],k))-as);
		sg.ud(0,lower_bound(as,as+n+t,mp(a[k],0))-as-1,-1);
		a[k]=w;
		sg.ins(lower_bound(as,as+n+t,mp(w,k))-as);
		sg.ud(0,lower_bound(as,as+n+t,mp(w,0))-as-1,1);
		sq.push_back(sg.mx);
	}
	return sq;
}

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