Submission #285128

#	Time	Username	Problem	Language	Result	Execution time	Memory
285128		Pyqe	Bubble Sort 2 (JOI18_bubblesort2)	C++14	60 / 100	1902 ms	524292 KiB

bubblesort2

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

using namespace std;

int n,nn=0,ma=1e9,inf=1e9;
multiset<int> ms[1000069];

struct segtree
{
	int l,r,mx,lz,pst;
	segtree *p[2];
	
	void bd(int lh,int rh)
	{
		int ii;
		
		l=lh;
		r=rh;
		mx=-inf;
		lz=0;
		if(l==r)
		{
			nn++;
			pst=nn;
		}
		for(ii=0;ii<2;ii++)
		{
			p[ii]=0;
		}
	}
	void blc()
	{
		int ii,md=(l+r)/2;
		
		for(ii=0;ii<2;ii++)
		{
			if(!p[ii])
			{
				p[ii]=new segtree;
				p[ii]->bd(!ii?l:md+1,!ii?md:r);
			}
			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,int w)
	{
		if(l>x||r<x);
		else if(l>=x&&r<=x)
		{
			ms[pst].insert(w);
			mx=*prev(ms[pst].end())+lz;
		}
		else
		{
			int ii;
			
			blc();
			for(ii=0;ii<2;ii++)
			{
				p[ii]->ins(x,w);
			}
			mx=max(p[0]->mx,p[1]->mx);
		}
	}
	void ers(int x,int w)
	{
		if(l>x||r<x);
		else if(l>=x&&r<=x)
		{
			ms[pst].erase(ms[pst].find(w));
			if(!ms[pst].empty())
			{
				mx=*prev(ms[pst].end())+lz;
			}
			else
			{
				mx=-inf;
			}
		}
		else
		{
			int ii;
			
			blc();
			for(ii=0;ii<2;ii++)
			{
				p[ii]->ers(x,w);
			}
			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();
	sg.bd(1,ma);
	for(i=0;i<n;i++)
	{
		sg.ins(a[i],i+1-n);
		sg.ud(1,a[i]-1,1);
	}
	for(rr=0;rr<t;rr++)
	{
		k=qp[rr];
		w=qw[rr];
		sg.ers(a[k],k+1-n);
		sg.ud(1,a[k]-1,-1);
		a[k]=w;
		sg.ins(w,k+1-n);
		sg.ud(1,w-1,1);
		sq.push_back(sg.mx);
	}
	return sq;
}

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