oj.uz

Submission #251082

# Submission time Handle Problem Language Result Execution time Memory
251082 2020-07-20T05:56:41 Z kshitij_sodani Bubble Sort 2 (JOI18_bubblesort2) C++14
60 / 100
 9000 ms 399644 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=600;
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<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: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 171 ms 188664 KB Output is correct
2 Correct 179 ms 188920 KB Output is correct
3 Correct 225 ms 190072 KB Output is correct
4 Correct 214 ms 190136 KB Output is correct
5 Correct 214 ms 190076 KB Output is correct
6 Correct 201 ms 190072 KB Output is correct
7 Correct 204 ms 190072 KB Output is correct
8 Correct 214 ms 190072 KB Output is correct
9 Correct 215 ms 190204 KB Output is correct
10 Correct 228 ms 190072 KB Output is correct
11 Correct 228 ms 190072 KB Output is correct
12 Correct 230 ms 190072 KB Output is correct
13 Correct 245 ms 190144 KB Output is correct
14 Correct 259 ms 190332 KB Output is correct
15 Correct 243 ms 190072 KB Output is correct
16 Correct 252 ms 190200 KB Output is correct
17 Correct 243 ms 190072 KB Output is correct
18 Correct 239 ms 190188 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 188664 KB Output is correct
2 Correct 179 ms 188920 KB Output is correct
3 Correct 225 ms 190072 KB Output is correct
4 Correct 214 ms 190136 KB Output is correct
5 Correct 214 ms 190076 KB Output is correct
6 Correct 201 ms 190072 KB Output is correct
7 Correct 204 ms 190072 KB Output is correct
8 Correct 214 ms 190072 KB Output is correct
9 Correct 215 ms 190204 KB Output is correct
10 Correct 228 ms 190072 KB Output is correct
11 Correct 228 ms 190072 KB Output is correct
12 Correct 230 ms 190072 KB Output is correct
13 Correct 245 ms 190144 KB Output is correct
14 Correct 259 ms 190332 KB Output is correct
15 Correct 243 ms 190072 KB Output is correct
16 Correct 252 ms 190200 KB Output is correct
17 Correct 243 ms 190072 KB Output is correct
18 Correct 239 ms 190188 KB Output is correct
19 Correct 467 ms 195704 KB Output is correct
20 Correct 535 ms 196640 KB Output is correct
21 Correct 468 ms 196728 KB Output is correct
22 Correct 523 ms 196728 KB Output is correct
23 Correct 600 ms 196856 KB Output is correct
24 Correct 610 ms 196856 KB Output is correct
25 Correct 680 ms 196904 KB Output is correct
26 Correct 663 ms 196728 KB Output is correct
27 Correct 716 ms 196792 KB Output is correct
28 Correct 690 ms 196612 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 423 ms 218872 KB Output is correct
2 Correct 3607 ms 235296 KB Output is correct
3 Correct 6140 ms 249868 KB Output is correct
4 Correct 5815 ms 249840 KB Output is correct
5 Correct 5216 ms 249848 KB Output is correct
6 Correct 5264 ms 249804 KB Output is correct
7 Correct 4811 ms 250040 KB Output is correct
8 Correct 4826 ms 249936 KB Output is correct
9 Correct 4914 ms 250176 KB Output is correct
10 Correct 1563 ms 248564 KB Output is correct
11 Correct 1595 ms 248436 KB Output is correct
12 Correct 1482 ms 248436 KB Output is correct
13 Correct 1325 ms 248560 KB Output is correct
14 Correct 1254 ms 248556 KB Output is correct
15 Correct 1251 ms 248688 KB Output is correct
16 Correct 1170 ms 249072 KB Output is correct
17 Correct 1055 ms 248724 KB Output is correct
18 Correct 1132 ms 248944 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 188664 KB Output is correct
2 Correct 179 ms 188920 KB Output is correct
3 Correct 225 ms 190072 KB Output is correct
4 Correct 214 ms 190136 KB Output is correct
5 Correct 214 ms 190076 KB Output is correct
6 Correct 201 ms 190072 KB Output is correct
7 Correct 204 ms 190072 KB Output is correct
8 Correct 214 ms 190072 KB Output is correct
9 Correct 215 ms 190204 KB Output is correct
10 Correct 228 ms 190072 KB Output is correct
11 Correct 228 ms 190072 KB Output is correct
12 Correct 230 ms 190072 KB Output is correct
13 Correct 245 ms 190144 KB Output is correct
14 Correct 259 ms 190332 KB Output is correct
15 Correct 243 ms 190072 KB Output is correct
16 Correct 252 ms 190200 KB Output is correct
17 Correct 243 ms 190072 KB Output is correct
18 Correct 239 ms 190188 KB Output is correct
19 Correct 467 ms 195704 KB Output is correct
20 Correct 535 ms 196640 KB Output is correct
21 Correct 468 ms 196728 KB Output is correct
22 Correct 523 ms 196728 KB Output is correct
23 Correct 600 ms 196856 KB Output is correct
24 Correct 610 ms 196856 KB Output is correct
25 Correct 680 ms 196904 KB Output is correct
26 Correct 663 ms 196728 KB Output is correct
27 Correct 716 ms 196792 KB Output is correct
28 Correct 690 ms 196612 KB Output is correct
29 Correct 423 ms 218872 KB Output is correct
30 Correct 3607 ms 235296 KB Output is correct
31 Correct 6140 ms 249868 KB Output is correct
32 Correct 5815 ms 249840 KB Output is correct
33 Correct 5216 ms 249848 KB Output is correct
34 Correct 5264 ms 249804 KB Output is correct
35 Correct 4811 ms 250040 KB Output is correct
36 Correct 4826 ms 249936 KB Output is correct
37 Correct 4914 ms 250176 KB Output is correct
38 Correct 1563 ms 248564 KB Output is correct
39 Correct 1595 ms 248436 KB Output is correct
40 Correct 1482 ms 248436 KB Output is correct
41 Correct 1325 ms 248560 KB Output is correct
42 Correct 1254 ms 248556 KB Output is correct
43 Correct 1251 ms 248688 KB Output is correct
44 Correct 1170 ms 249072 KB Output is correct
45 Correct 1055 ms 248724 KB Output is correct
46 Correct 1132 ms 248944 KB Output is correct
47 Execution timed out 9104 ms 399644 KB Time limit exceeded
48 Halted 0 ms 0 KB -