oj.uz

Submission #251068

# Submission time Handle Problem Language Result Execution time Memory
251068 2020-07-20T05:34:21 Z kshitij_sodani Bubble Sort 2 (JOI18_bubblesort2) C++14
38 / 100
 4838 ms 434168 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<int,int>,null_type,less<pair<int,int>>,rb_tree_tag,tree_order_statistics_node_update>

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

void build(int no,int l,int r){
	if(l==r){
		tree2[no].insert({ac[l],ind[l]});
	}
	else{
		int 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);
		}
	}
}

int query(int no,int l,int r,int aa,int bb,int 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{
		int 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(int no,int l,int r,int ind5,pair<int,int> old,pair<int,int> nn){
	if(r<ind5 or l>ind5){
		return;
	}
	tree2[no].erase(old);
	tree2[no].insert(nn);
	if(l<r){
		int 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(int no,int l,int r,int aa,int bb,int 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{
		int 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(int no,int l,int r,int aa,int 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{
		int 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){
	int q=X.size();
	int n=it.size();


	for(int i=0;i<n;i++){
		ac[i]=it[i];
	}
	


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

	//process index
	int co=-1;
	for(int 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
	memset(tree4,-1e9,sizeof(tree4));


	//initial tree
	ord kk;
	for(int i=0;i<n;i++){
		int 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(int i=0;i<n+q;i++){
		cout<<ind[i]<<":";
	}
	cout<<endl;*/
	//pre-process with pbds
	for(int ii=0;ii<q;ii++){
		int ind3=X[ii];
		int val=V[ii];
		int l,r,cc;

		update2(0,0,n+q-1,ind2[ind3],-1e9);
		//remove pairs from mst
		pair<int,int> old={it[ind3],ind2[ind3]};
		pair<int,int> nn={val,ind[ii+n]};
		update3(0,0,n-1,ind3,old,nn);
		// update answer of current index
		int x=0;
		if(ind3>0){
			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];

		int 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(int i=ind3/ss;i<=(n-1)/ss;i++){
			if(i==ind3/ss){
				for(int 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<int,int> kc={l,0};
				int low=lower_bound(tt[i].begin(),tt[i].end(),kc)-tt[i].begin();
				if(low==tt[i].size()){
					continue;
				}
				kc.a=r+1;
				int 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);
	int nn,qq;
	cin>>nn>>qq;
	int pp;
	vector<int> ac;
	vector<int> bc;
	vector<int> dc;

	for(int i=0;i<nn;i++){
		cin>>pp;
		ac.pb(pp);
	}
	for(int 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:220:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(low==tt[i].size()){
        ~~~^~~~~~~~~~~~~~
bubblesort2.cpp:186:7: warning: unused variable 'kk' [-Wunused-variable]
   int kk=0;
       ^~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 345 ms 403960 KB Output is correct
2 Correct 364 ms 404088 KB Output is correct
3 Correct 578 ms 405420 KB Output is correct
4 Correct 579 ms 405368 KB Output is correct
5 Correct 534 ms 405356 KB Output is correct
6 Correct 495 ms 405368 KB Output is correct
7 Correct 529 ms 405368 KB Output is correct
8 Correct 523 ms 405372 KB Output is correct
9 Correct 521 ms 405352 KB Output is correct
10 Correct 553 ms 405588 KB Output is correct
11 Correct 569 ms 405368 KB Output is correct
12 Correct 554 ms 405356 KB Output is correct
13 Correct 554 ms 405356 KB Output is correct
14 Correct 555 ms 405368 KB Output is correct
15 Correct 551 ms 405344 KB Output is correct
16 Correct 555 ms 405568 KB Output is correct
17 Correct 566 ms 405368 KB Output is correct
18 Correct 548 ms 405356 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 345 ms 403960 KB Output is correct
2 Correct 364 ms 404088 KB Output is correct
3 Correct 578 ms 405420 KB Output is correct
4 Correct 579 ms 405368 KB Output is correct
5 Correct 534 ms 405356 KB Output is correct
6 Correct 495 ms 405368 KB Output is correct
7 Correct 529 ms 405368 KB Output is correct
8 Correct 523 ms 405372 KB Output is correct
9 Correct 521 ms 405352 KB Output is correct
10 Correct 553 ms 405588 KB Output is correct
11 Correct 569 ms 405368 KB Output is correct
12 Correct 554 ms 405356 KB Output is correct
13 Correct 554 ms 405356 KB Output is correct
14 Correct 555 ms 405368 KB Output is correct
15 Correct 551 ms 405344 KB Output is correct
16 Correct 555 ms 405568 KB Output is correct
17 Correct 566 ms 405368 KB Output is correct
18 Correct 548 ms 405356 KB Output is correct
19 Correct 3873 ms 411136 KB Output is correct
20 Correct 4838 ms 412280 KB Output is correct
21 Correct 3816 ms 412096 KB Output is correct
22 Correct 3919 ms 412188 KB Output is correct
23 Correct 4295 ms 412104 KB Output is correct
24 Correct 4462 ms 412080 KB Output is correct
25 Correct 4534 ms 412052 KB Output is correct
26 Correct 4434 ms 412164 KB Output is correct
27 Correct 4526 ms 412184 KB Output is correct
28 Correct 4540 ms 411896 KB Output is correct

Subtask #3
0 / 22.0

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

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 345 ms 403960 KB Output is correct
2 Correct 364 ms 404088 KB Output is correct
3 Correct 578 ms 405420 KB Output is correct
4 Correct 579 ms 405368 KB Output is correct
5 Correct 534 ms 405356 KB Output is correct
6 Correct 495 ms 405368 KB Output is correct
7 Correct 529 ms 405368 KB Output is correct
8 Correct 523 ms 405372 KB Output is correct
9 Correct 521 ms 405352 KB Output is correct
10 Correct 553 ms 405588 KB Output is correct
11 Correct 569 ms 405368 KB Output is correct
12 Correct 554 ms 405356 KB Output is correct
13 Correct 554 ms 405356 KB Output is correct
14 Correct 555 ms 405368 KB Output is correct
15 Correct 551 ms 405344 KB Output is correct
16 Correct 555 ms 405568 KB Output is correct
17 Correct 566 ms 405368 KB Output is correct
18 Correct 548 ms 405356 KB Output is correct
19 Correct 3873 ms 411136 KB Output is correct
20 Correct 4838 ms 412280 KB Output is correct
21 Correct 3816 ms 412096 KB Output is correct
22 Correct 3919 ms 412188 KB Output is correct
23 Correct 4295 ms 412104 KB Output is correct
24 Correct 4462 ms 412080 KB Output is correct
25 Correct 4534 ms 412052 KB Output is correct
26 Correct 4434 ms 412164 KB Output is correct
27 Correct 4526 ms 412184 KB Output is correct
28 Correct 4540 ms 411896 KB Output is correct
29 Incorrect 3168 ms 434168 KB Output isn't correct
30 Halted 0 ms 0 KB -