oj.uz

Submission #251072

# Submission time Handle Problem Language Result Execution time Memory
251072 2020-07-20T05:43:57 Z kshitij_sodani Bubble Sort 2 (JOI18_bubblesort2) C++14
38 / 100
 3651 ms 408072 KB 
#include <bits/stdc++.h>
using namespace std;
typedef int64_t llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace __gnu_pbds;
#define ord tree<pair<llo,llo>,null_type,less<pair<llo,llo>>,rb_tree_tag,tree_order_statistics_node_update>

//#include "bubblesort2.h"
const llo ss=500001;
llo ind2[500001];//current index of element i
vector<pair<llo,llo>> tt[500001/ss+1];
llo ind[1000001];//index of each n+q-1 in seg tree
llo lazy[4000001];
llo tree4[4000001];
ord tree2[4000001];
llo ac[500001];

void build(llo no,llo l,llo r){
	if(l==r){
		tree2[no].insert({ac[l],ind[l]});
	}
	else{
		llo mid=(l+r)/2;
		build(no*2+1,l,mid);
		build(no*2+2,mid+1,r);
		tree2[no]=tree2[no*2+1];
		for(auto j:tree2[no*2+2]){
			tree2[no].insert(j);
		}
	}
}

llo query(llo no,llo l,llo r,llo aa,llo bb,llo val){
	if(r<aa or l>bb){
		return 0;
	}
	if(aa<=l and r<=bb){
		return tree2[no].size()-tree2[no].order_of_key({val+1,0});
	}
	else{
		llo mid=(l+r)/2;
		return query(no*2+1,l,mid,aa,bb,val)+query(no*2+2,mid+1,r,aa,bb,val);
	}
}
void update3(llo no,llo l,llo r,llo ind5,pair<llo,llo> old,pair<llo,llo> nn){
	if(r<ind5 or l>ind5){
		return;
	}
	tree2[no].erase(old);
	tree2[no].insert(nn);
	if(l<r){
		llo mid=(l+r)/2;
		update3(no*2+1,l,mid,ind5,old,nn);
		update3(no*2+2,mid+1,r,ind5,old,nn);
	}
}
void update(llo no,llo l,llo r,llo aa,llo bb,llo val){
	tree4[no]+=lazy[no];
	if(l<r){
		lazy[no*2+1]+=lazy[no];
		lazy[no*2+2]+=lazy[no];
	}
	lazy[no]=0;
	if(r<aa or l>bb){
		return;
	}
	if(aa<=l and r<=bb){
		tree4[no]+=val;
		if(l<r){
			lazy[no*2+1]+=val;
			lazy[no*2+2]+=val;
		}
	}
	else{
		llo mid=(l+r)/2;
		update(no*2+1,l,mid,aa,bb,val);
		update(no*2+2,mid+1,r,aa,bb,val);
		tree4[no]=max(tree4[no*2+1],tree4[no*2+2]);
	}
}
void update2(llo no,llo l,llo r,llo aa,llo val){
	tree4[no]+=lazy[no];
	if(l<r){
		lazy[no*2+1]+=lazy[no];
		lazy[no*2+2]+=lazy[no];
	}
	lazy[no]=0;
	if(r<aa or l>aa){
		return;
	}
	if(l==r){
		tree4[no]=val;
	}
	else{
		llo mid=(l+r)/2;
		update2(no*2+1,l,mid,aa,val);
		update2(no*2+2,mid+1,r,aa,val);
		tree4[no]=max(tree4[no*2+1],tree4[no*2+2]);
	}
}
std::vector<int> countScans(std::vector<int> it,std::vector<int> X,std::vector<int> V){
	llo q=X.size();
	llo n=it.size();


	for(llo i=0;i<n;i++){
		ac[i]=it[i];
	}
	//sqrt blocks process
	for(llo i=0;i<n;i++){
		tt[i/ss].pb({it[i],i});
	}
	for(llo i=0;i<q;i++){
		tt[X[i]/ss].pb({V[i],i+n});
	}
	for(llo i=0;i<=(n-1)/ss;i++){
		sort(tt[i].begin(),tt[i].end());
	}
	//end

	//process index
	llo co=-1;
	for(llo i=0;i<=(n-1)/ss;i++){
		for(auto j:tt[i]){
			co+=1;
			ind[j.b]=co;
			if(j.b<n){
				ind2[j.b]=co;
			}
		}
	}
	build(0,0,n-1);
	//end
	for(llo i=0;i<4*(n+q);i++){
		tree4[i]=-1e9;
	}
//	memset(tree4,-1e9,sizeof(tree4));


	//initial tree
	ord kk;
	for(llo i=0;i<n;i++){
		llo cur=kk.size()-kk.order_of_key({it[i]+1,0});
		update2(0,0,n+q-1,ind[i],cur);
		kk.insert({it[i],i});

		//cout<<i<<","<<cur<<endl;
	}
	//end


	vector<int> ans;
/*	for(llo i=0;i<n+q;i++){
		cout<<ind[i]<<":";
	}
	cout<<endl;*/
	//pre-process with pbds
	for(llo ii=0;ii<q;ii++){
		llo ind3=X[ii];
		llo val=V[ii];
		llo l,r,cc;

		update2(0,0,n+q-1,ind2[ind3],-1e9);
		//remove pairs from mst
		pair<llo,llo> old={it[ind3],ind2[ind3]};
		pair<llo,llo> nn={val,ind[ii+n]};
		update3(0,0,n-1,ind3,old,nn);
		// update answer of current index
		llo x=0;
		if(ind3>0){
			/*for(llo i=0;i<ind3;i++){
				if(it[i]>val){
					x+=1;
				}
			}*/
			x=query(0,0,n-1,0,ind3-1,val);
		}
	//	cout<<x<<endl;
		update2(0,0,n+q-1,ind[ii+n],x);
		//end


		ind2[ind3]=ind[ii+n];

		llo kk=0;
		if(val<it[ind3]){
			l=val;
			r=it[ind3]-1;
			cc=-1;
		}
		else if(val>it[ind3]){
			l=it[ind3];
			r=val-1;
			cc=1;
		}
		else{
			continue;
		}
	//	cout<<l<<","<<r<<","<<cc<<endl;


		it[ind3]=val;

		for(llo i=ind3/ss;i<=(n-1)/ss;i++){
			if(i==ind3/ss){
				for(llo j=ind3+1;j<n;j++){
					if(j/ss>i){
						break;
					}
					if(it[j]>=l and it[j]<=r){

						update(0,0,n+q-1,ind2[j],ind2[j],cc);
					}
				}
				//for each index check individually and update
			}
			else{
				pair<llo,llo> kc={l,0};
				llo low=lower_bound(tt[i].begin(),tt[i].end(),kc)-tt[i].begin();
				if(low==tt[i].size()){
					continue;
				}
				kc.a=r+1;
				llo rr=lower_bound(tt[i].begin(),tt[i].end(),kc)-tt[i].begin();
				if(rr==low){
					continue;
				}
				update(0,0,n+q-1,ind[tt[i][low].b],ind[tt[i][low].b]+rr-low-1,cc);
				//binary search to find index in each block and update in seg tree
			}
		}
		ans.pb(tree4[0]);
	}
/*	for(auto j:ans){
		cout<<j<<",";
	}
	cout<<endl;*/
	return ans;
}

//#define endl '\n'

/*int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	llo nn,qq;
	cin>>nn>>qq;
	llo pp;
	vector<int> ac;
	vector<int> bc;
	vector<int> dc;

	for(llo i=0;i<nn;i++){
		cin>>pp;
		ac.pb(pp);
	}
	for(llo i=0;i<qq;i++){
		cin>>pp;
		bc.pb(pp);
		cin>>pp;
		dc.pb(pp);
	}
	countScans(ac,bc,dc);
 
	return 0;
}*/

Compilation message

bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:226:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(low==tt[i].size()){
        ~~~^~~~~~~~~~~~~~
bubblesort2.cpp:191:7: warning: unused variable 'kk' [-Wunused-variable]
   llo kk=0;
       ^~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 308 ms 376568 KB Output is correct
2 Correct 324 ms 376824 KB Output is correct
3 Correct 515 ms 378120 KB Output is correct
4 Correct 493 ms 378104 KB Output is correct
5 Correct 479 ms 378232 KB Output is correct
6 Correct 466 ms 378104 KB Output is correct
7 Correct 489 ms 378136 KB Output is correct
8 Correct 473 ms 378220 KB Output is correct
9 Correct 476 ms 378104 KB Output is correct
10 Correct 504 ms 378024 KB Output is correct
11 Correct 500 ms 378232 KB Output is correct
12 Correct 486 ms 378232 KB Output is correct
13 Correct 516 ms 378104 KB Output is correct
14 Correct 514 ms 378124 KB Output is correct
15 Correct 513 ms 378244 KB Output is correct
16 Correct 524 ms 378104 KB Output is correct
17 Correct 539 ms 378104 KB Output is correct
18 Correct 531 ms 378240 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 308 ms 376568 KB Output is correct
2 Correct 324 ms 376824 KB Output is correct
3 Correct 515 ms 378120 KB Output is correct
4 Correct 493 ms 378104 KB Output is correct
5 Correct 479 ms 378232 KB Output is correct
6 Correct 466 ms 378104 KB Output is correct
7 Correct 489 ms 378136 KB Output is correct
8 Correct 473 ms 378220 KB Output is correct
9 Correct 476 ms 378104 KB Output is correct
10 Correct 504 ms 378024 KB Output is correct
11 Correct 500 ms 378232 KB Output is correct
12 Correct 486 ms 378232 KB Output is correct
13 Correct 516 ms 378104 KB Output is correct
14 Correct 514 ms 378124 KB Output is correct
15 Correct 513 ms 378244 KB Output is correct
16 Correct 524 ms 378104 KB Output is correct
17 Correct 539 ms 378104 KB Output is correct
18 Correct 531 ms 378240 KB Output is correct
19 Correct 2448 ms 384376 KB Output is correct
20 Correct 3059 ms 385544 KB Output is correct
21 Correct 2731 ms 385240 KB Output is correct
22 Correct 2510 ms 385364 KB Output is correct
23 Correct 2678 ms 385512 KB Output is correct
24 Correct 2742 ms 385372 KB Output is correct
25 Correct 3156 ms 385532 KB Output is correct
26 Correct 3151 ms 385276 KB Output is correct
27 Correct 3651 ms 385404 KB Output is correct
28 Correct 3599 ms 385528 KB Output is correct

Subtask #3
0 / 22.0

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

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 308 ms 376568 KB Output is correct
2 Correct 324 ms 376824 KB Output is correct
3 Correct 515 ms 378120 KB Output is correct
4 Correct 493 ms 378104 KB Output is correct
5 Correct 479 ms 378232 KB Output is correct
6 Correct 466 ms 378104 KB Output is correct
7 Correct 489 ms 378136 KB Output is correct
8 Correct 473 ms 378220 KB Output is correct
9 Correct 476 ms 378104 KB Output is correct
10 Correct 504 ms 378024 KB Output is correct
11 Correct 500 ms 378232 KB Output is correct
12 Correct 486 ms 378232 KB Output is correct
13 Correct 516 ms 378104 KB Output is correct
14 Correct 514 ms 378124 KB Output is correct
15 Correct 513 ms 378244 KB Output is correct
16 Correct 524 ms 378104 KB Output is correct
17 Correct 539 ms 378104 KB Output is correct
18 Correct 531 ms 378240 KB Output is correct
19 Correct 2448 ms 384376 KB Output is correct
20 Correct 3059 ms 385544 KB Output is correct
21 Correct 2731 ms 385240 KB Output is correct
22 Correct 2510 ms 385364 KB Output is correct
23 Correct 2678 ms 385512 KB Output is correct
24 Correct 2742 ms 385372 KB Output is correct
25 Correct 3156 ms 385532 KB Output is correct
26 Correct 3151 ms 385276 KB Output is correct
27 Correct 3651 ms 385404 KB Output is correct
28 Correct 3599 ms 385528 KB Output is correct
29 Incorrect 3028 ms 408072 KB Output isn't correct
30 Halted 0 ms 0 KB -