제출 #58925

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
58925		khohko	Bubble Sort 2 (JOI18_bubblesort2)	C++17	60 / 100	7142 ms	525312 KiB

bubblesort2

#include<bits/stdc++.h>
#include "bubblesort2.h"
using namespace std;
#define ll int
#define fr first
#define sc second
#define pb push_back
#define ARRS ((ll)(2e6+100))
#define MAX ((ll)(1e9+100))



ll wl,wr,wx,wi;
struct nodes{
	nodes *L,*R;
	int x;
	nodes(){
		L=R=NULL;
		x=0;
	}
	void updt(){
		x=0;
		if(L)x+=L->x;
		if(R)x+=R->x;
	}
};

void updt(ll l,ll r,nodes *& x){
	if(wi<l||r-1<wi)return;
	if(!x)x=new nodes();
	if(l==r-1){
		x->x+=wx;
		return;
	}
	updt(l,l+r>>1,x->L);
	updt(l+r>>1,r,x->R);
	x->updt();
}

ll quer(ll l,ll r,nodes *& x){
	if(wr<l||r-1<wl)return 0;
	if(!x)return 0;
	if(wl<=l&&r-1<=wr)return x->x;
	return quer(l,l+r>>1,x->L)
				+quer(l+r>>1,r,x->R);
}

struct node{
	node *L,*R;
	int x,s;
	node(){
		L=R=NULL;
		s=0;
		x=-MAX;
	}
	void updt(){
		x=-MAX;
		if(L)x=max(x,L->x);
		if(R)x=max(x,R->x);
	}
	void shep(ll y){
		s+=y;
		x+=y;
	}
	void shplit(){
		if(!L)L=new node();
		if(!R)R=new node();
		L->shep(s);
		R->shep(s);
		s=0;
	}
};

void updt(ll l,ll r,node *& x){
	if(wr<l||r-1<wl)return;
	if(!x)x=new node();
	if(wl<=l&&r-1<=wr){
		x->shep(wx);
		return;
	}
	x->shplit();
	updt(l,l+r>>1,x->L);
	updt(l+r>>1,r,x->R);
	x->updt();
}

void updt1(ll l,ll r,node *& x){
	if(wr<l||r-1<wl)return;
	if(!x)x=new node();
	if(wl<=l&&r-1<=wr){
		x->x=wx;
		x->s=0;
		return;
	}
	x->shplit();
	updt1(l,l+r>>1,x->L);
	updt1(l+r>>1,r,x->R);
	x->updt();
}


map<ll, set<ll> > mp;

node *rt=NULL;
nodes *rts=NULL;

void up(ll x){
	if(mp[x].size()){
		wl=x+1; wr=MAX;

		wx=-(*mp[x].begin())+quer(-MAX,MAX,rts);
		wl=wr=x;
//		cout<<wl<<" "<<wx<<" "<<x<<" "<<(-*mp[x].begin())<<endl;
		updt1(-MAX,MAX,rt);
	}
	else {
		wl=wr=x;
		wx=-MAX;
		updt1(-MAX,MAX,rt);
	}
}

ll a[ARRS],n;

void quer(ll i,ll x){

	mp[a[i]].erase(n-i-1);
	mp[x].insert(n-i-1);

	wi=a[i];
	wx=-1;
	updt(-MAX,MAX,rts);

	wi=x;
	wx=1;
	updt(-MAX,MAX,rts);

	up(x);
	up(a[i]);
	if(a[i]<=x){
		wl=a[i]+1;
		wr=x-1;
		wx=1;
	}
	else {
		wl=x+1;
		wr=a[i]-1;
		wx=-1;
	}
	updt(-MAX,MAX,rt);
	a[i]=x;
}


vector<int> countScans(vector<int> A,vector<int> X,vector<int> V){
	n=A.size();
	ll q=X.size();
	vector<int> PAS;
	for(int i=0; i<n; i++){
		a[i]=A[i];
		wi=a[i];
		wx=1;
		updt(-MAX,MAX,rts);
	}
	for(int i=0; i<n; i++){
		mp[a[i]].insert(n-i-1);
		up(a[i]);
	}
	//cout<<" ----> "<<rt->x<<endl;

	for(int i=0; i<q; i++){
		ll k=X[i];
		ll p=V[i];
		quer(k,p);
		PAS.pb(rt->x);
	}

	return PAS;
}

컴파일 시 표준 에러 (stderr) 메시지

bubblesort2.cpp: In function 'void updt(int, int, nodes*&)':
bubblesort2.cpp:35:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  updt(l,l+r>>1,x->L);
         ~^~
bubblesort2.cpp:36:8: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  updt(l+r>>1,r,x->R);
       ~^~
bubblesort2.cpp: In function 'int quer(int, int, nodes*&)':
bubblesort2.cpp:44:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  return quer(l,l+r>>1,x->L)
                ~^~
bubblesort2.cpp:45:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     +quer(l+r>>1,r,x->R);
           ~^~
bubblesort2.cpp: In function 'void updt(int, int, node*&)':
bubblesort2.cpp:82:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  updt(l,l+r>>1,x->L);
         ~^~
bubblesort2.cpp:83:8: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  updt(l+r>>1,r,x->R);
       ~^~
bubblesort2.cpp: In function 'void updt1(int, int, node*&)':
bubblesort2.cpp:96:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  updt1(l,l+r>>1,x->L);
          ~^~
bubblesort2.cpp:97:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  updt1(l+r>>1,r,x->R);
        ~^~

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