제출 #285117

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
285117		Pyqe	Bubble Sort 2 (JOI18_bubblesort2)	C++14	60 / 100	1109 ms	524292 KiB

bubblesort2

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

using namespace std;

long long n,ma=1e9,inf=1e18;

struct segtree
{
	long long l,r,mx,lz;
	multiset<long long> ms;
	segtree *p[2];
	
	void bd(long long lh,long long rh)
	{
		long long ii;
		
		l=lh;
		r=rh;
		mx=-inf;
		lz=0;
		for(ii=0;ii<2;ii++)
		{
			p[ii]=0;
		}
	}
	void blc()
	{
		long long 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(long long lh,long long rh,long long w)
	{
		if(l>rh||r<lh);
		else if(l>=lh&&r<=rh)
		{
			mx+=w;
			lz+=w;
		}
		else
		{
			long long ii;
			
			blc();
			for(ii=0;ii<2;ii++)
			{
				p[ii]->ud(lh,rh,w);
			}
			mx=max(p[0]->mx,p[1]->mx);
		}
	}
	void ins(long long x,long long w)
	{
		if(l>x||r<x);
		else if(l>=x&&r<=x)
		{
			ms.insert(w);
			mx=*prev(ms.end())+lz;
		}
		else
		{
			long long ii;
			
			blc();
			for(ii=0;ii<2;ii++)
			{
				p[ii]->ins(x,w);
			}
			mx=max(p[0]->mx,p[1]->mx);
		}
	}
	void ers(long long x,long long w)
	{
		if(l>x||r<x);
		else if(l>=x&&r<=x)
		{
			ms.erase(ms.find(w));
			if(!ms.empty())
			{
				mx=*prev(ms.end())+lz;
			}
			else
			{
				mx=-inf;
			}
		}
		else
		{
			long long 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)
{
	long long 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