oj.uz

Submission #251085

# Submission time Handle Problem Language Result Execution time Memory
251085 2020-07-20T05:59:47 Z kshitij_sodani Bubble Sort 2 (JOI18_bubblesort2) C++14
60 / 100
 9000 ms 398412 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=900;
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[2000001];
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){
	if(lazy[no]>0 or lazy[no]<0){
		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){
	if(lazy[no]>0 or lazy[no]<0){
		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
	for(int i=0;i<4*(n+q);i++){
		tree4[i]=-1e9;
	}
//	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){
			/*for(int 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];

		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{
			ans.pb(tree4[0]);
			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<min(n,(i+1)*ss);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:232:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(low==tt[i].size()){
        ~~~^~~~~~~~~~~~~~
bubblesort2.cpp:196:7: warning: unused variable 'kk' [-Wunused-variable]
   int kk=0;
       ^~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 188664 KB Output is correct
2 Correct 208 ms 188796 KB Output is correct
3 Correct 242 ms 190072 KB Output is correct
4 Correct 255 ms 190368 KB Output is correct
5 Correct 265 ms 190072 KB Output is correct
6 Correct 231 ms 190072 KB Output is correct
7 Correct 399 ms 190200 KB Output is correct
8 Correct 235 ms 190112 KB Output is correct
9 Correct 245 ms 190328 KB Output is correct
10 Correct 280 ms 190072 KB Output is correct
11 Correct 280 ms 190072 KB Output is correct
12 Correct 261 ms 190072 KB Output is correct
13 Correct 278 ms 190072 KB Output is correct
14 Correct 288 ms 190200 KB Output is correct
15 Correct 272 ms 190072 KB Output is correct
16 Correct 293 ms 190216 KB Output is correct
17 Correct 296 ms 190212 KB Output is correct
18 Correct 288 ms 190316 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 188664 KB Output is correct
2 Correct 208 ms 188796 KB Output is correct
3 Correct 242 ms 190072 KB Output is correct
4 Correct 255 ms 190368 KB Output is correct
5 Correct 265 ms 190072 KB Output is correct
6 Correct 231 ms 190072 KB Output is correct
7 Correct 399 ms 190200 KB Output is correct
8 Correct 235 ms 190112 KB Output is correct
9 Correct 245 ms 190328 KB Output is correct
10 Correct 280 ms 190072 KB Output is correct
11 Correct 280 ms 190072 KB Output is correct
12 Correct 261 ms 190072 KB Output is correct
13 Correct 278 ms 190072 KB Output is correct
14 Correct 288 ms 190200 KB Output is correct
15 Correct 272 ms 190072 KB Output is correct
16 Correct 293 ms 190216 KB Output is correct
17 Correct 296 ms 190212 KB Output is correct
18 Correct 288 ms 190316 KB Output is correct
19 Correct 536 ms 195688 KB Output is correct
20 Correct 651 ms 196856 KB Output is correct
21 Correct 547 ms 196728 KB Output is correct
22 Correct 702 ms 196728 KB Output is correct
23 Correct 830 ms 196856 KB Output is correct
24 Correct 790 ms 196908 KB Output is correct
25 Correct 856 ms 196780 KB Output is correct
26 Correct 818 ms 196692 KB Output is correct
27 Correct 898 ms 196600 KB Output is correct
28 Correct 855 ms 196728 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 462 ms 218744 KB Output is correct
2 Correct 2698 ms 235536 KB Output is correct
3 Correct 6152 ms 249504 KB Output is correct
4 Correct 5674 ms 249784 KB Output is correct
5 Correct 5610 ms 249932 KB Output is correct
6 Correct 5572 ms 249628 KB Output is correct
7 Correct 5557 ms 249424 KB Output is correct
8 Correct 5490 ms 249652 KB Output is correct
9 Correct 5149 ms 249616 KB Output is correct
10 Correct 1777 ms 248692 KB Output is correct
11 Correct 1684 ms 248692 KB Output is correct
12 Correct 1655 ms 248692 KB Output is correct
13 Correct 1382 ms 248844 KB Output is correct
14 Correct 1437 ms 248828 KB Output is correct
15 Correct 1368 ms 248972 KB Output is correct
16 Correct 1090 ms 248700 KB Output is correct
17 Correct 1102 ms 248572 KB Output is correct
18 Correct 1093 ms 248604 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 188664 KB Output is correct
2 Correct 208 ms 188796 KB Output is correct
3 Correct 242 ms 190072 KB Output is correct
4 Correct 255 ms 190368 KB Output is correct
5 Correct 265 ms 190072 KB Output is correct
6 Correct 231 ms 190072 KB Output is correct
7 Correct 399 ms 190200 KB Output is correct
8 Correct 235 ms 190112 KB Output is correct
9 Correct 245 ms 190328 KB Output is correct
10 Correct 280 ms 190072 KB Output is correct
11 Correct 280 ms 190072 KB Output is correct
12 Correct 261 ms 190072 KB Output is correct
13 Correct 278 ms 190072 KB Output is correct
14 Correct 288 ms 190200 KB Output is correct
15 Correct 272 ms 190072 KB Output is correct
16 Correct 293 ms 190216 KB Output is correct
17 Correct 296 ms 190212 KB Output is correct
18 Correct 288 ms 190316 KB Output is correct
19 Correct 536 ms 195688 KB Output is correct
20 Correct 651 ms 196856 KB Output is correct
21 Correct 547 ms 196728 KB Output is correct
22 Correct 702 ms 196728 KB Output is correct
23 Correct 830 ms 196856 KB Output is correct
24 Correct 790 ms 196908 KB Output is correct
25 Correct 856 ms 196780 KB Output is correct
26 Correct 818 ms 196692 KB Output is correct
27 Correct 898 ms 196600 KB Output is correct
28 Correct 855 ms 196728 KB Output is correct
29 Correct 462 ms 218744 KB Output is correct
30 Correct 2698 ms 235536 KB Output is correct
31 Correct 6152 ms 249504 KB Output is correct
32 Correct 5674 ms 249784 KB Output is correct
33 Correct 5610 ms 249932 KB Output is correct
34 Correct 5572 ms 249628 KB Output is correct
35 Correct 5557 ms 249424 KB Output is correct
36 Correct 5490 ms 249652 KB Output is correct
37 Correct 5149 ms 249616 KB Output is correct
38 Correct 1777 ms 248692 KB Output is correct
39 Correct 1684 ms 248692 KB Output is correct
40 Correct 1655 ms 248692 KB Output is correct
41 Correct 1382 ms 248844 KB Output is correct
42 Correct 1437 ms 248828 KB Output is correct
43 Correct 1368 ms 248972 KB Output is correct
44 Correct 1090 ms 248700 KB Output is correct
45 Correct 1102 ms 248572 KB Output is correct
46 Correct 1093 ms 248604 KB Output is correct
47 Execution timed out 9079 ms 398412 KB Time limit exceeded
48 Halted 0 ms 0 KB -