oj.uz

Submission #58922

# Submission time Handle Problem Language Result Execution time Memory
58922 2018-07-19T20:17:34 Z khohko Bubble Sort 2 (JOI18_bubblesort2) C++17
22 / 100
 422 ms 5012 KB 
#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)(1e17+100))



ll wl,wr,wx,wi;
struct nodes{
	nodes *L,*R;
	ll 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;
	ll 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<ll> 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;
}

Compilation message

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
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 2424 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 2424 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 2424 KB Output is correct
2 Correct 196 ms 3504 KB Output is correct
3 Correct 370 ms 4756 KB Output is correct
4 Correct 417 ms 4988 KB Output is correct
5 Correct 367 ms 4988 KB Output is correct
6 Correct 348 ms 4988 KB Output is correct
7 Correct 346 ms 4988 KB Output is correct
8 Correct 422 ms 5012 KB Output is correct
9 Correct 354 ms 5012 KB Output is correct
10 Correct 222 ms 5012 KB Output is correct
11 Correct 286 ms 5012 KB Output is correct
12 Correct 289 ms 5012 KB Output is correct
13 Correct 263 ms 5012 KB Output is correct
14 Correct 347 ms 5012 KB Output is correct
15 Correct 269 ms 5012 KB Output is correct
16 Correct 287 ms 5012 KB Output is correct
17 Correct 246 ms 5012 KB Output is correct
18 Correct 255 ms 5012 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 2424 KB Output isn't correct
2 Halted 0 ms 0 KB -