oj.uz

Submission #251084

# Submission time Handle Problem Language Result Execution time Memory
251084 2020-07-20T05:59:03 Z kshitij_sodani Bubble Sort 2 (JOI18_bubblesort2) C++14
60 / 100
 9000 ms 398196 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<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 161 ms 188664 KB Output is correct
2 Correct 177 ms 188920 KB Output is correct
3 Correct 286 ms 190200 KB Output is correct
4 Correct 222 ms 190200 KB Output is correct
5 Correct 218 ms 190072 KB Output is correct
6 Correct 212 ms 190072 KB Output is correct
7 Correct 223 ms 190180 KB Output is correct
8 Correct 236 ms 190072 KB Output is correct
9 Correct 236 ms 190072 KB Output is correct
10 Correct 254 ms 190200 KB Output is correct
11 Correct 251 ms 190200 KB Output is correct
12 Correct 256 ms 190200 KB Output is correct
13 Correct 263 ms 190192 KB Output is correct
14 Correct 263 ms 190200 KB Output is correct
15 Correct 268 ms 190072 KB Output is correct
16 Correct 276 ms 190188 KB Output is correct
17 Correct 281 ms 190180 KB Output is correct
18 Correct 274 ms 190072 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 188664 KB Output is correct
2 Correct 177 ms 188920 KB Output is correct
3 Correct 286 ms 190200 KB Output is correct
4 Correct 222 ms 190200 KB Output is correct
5 Correct 218 ms 190072 KB Output is correct
6 Correct 212 ms 190072 KB Output is correct
7 Correct 223 ms 190180 KB Output is correct
8 Correct 236 ms 190072 KB Output is correct
9 Correct 236 ms 190072 KB Output is correct
10 Correct 254 ms 190200 KB Output is correct
11 Correct 251 ms 190200 KB Output is correct
12 Correct 256 ms 190200 KB Output is correct
13 Correct 263 ms 190192 KB Output is correct
14 Correct 263 ms 190200 KB Output is correct
15 Correct 268 ms 190072 KB Output is correct
16 Correct 276 ms 190188 KB Output is correct
17 Correct 281 ms 190180 KB Output is correct
18 Correct 274 ms 190072 KB Output is correct
19 Correct 536 ms 195960 KB Output is correct
20 Correct 598 ms 196856 KB Output is correct
21 Correct 508 ms 196600 KB Output is correct
22 Correct 616 ms 196604 KB Output is correct
23 Correct 765 ms 196600 KB Output is correct
24 Correct 743 ms 196600 KB Output is correct
25 Correct 829 ms 196856 KB Output is correct
26 Correct 829 ms 196728 KB Output is correct
27 Correct 867 ms 196860 KB Output is correct
28 Correct 860 ms 196740 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 423 ms 218688 KB Output is correct
2 Correct 2419 ms 235304 KB Output is correct
3 Correct 5049 ms 249436 KB Output is correct
4 Correct 5216 ms 249848 KB Output is correct
5 Correct 5505 ms 249764 KB Output is correct
6 Correct 5752 ms 249424 KB Output is correct
7 Correct 6040 ms 249464 KB Output is correct
8 Correct 6039 ms 249464 KB Output is correct
9 Correct 5290 ms 249484 KB Output is correct
10 Correct 1713 ms 248736 KB Output is correct
11 Correct 1806 ms 248688 KB Output is correct
12 Correct 1784 ms 248564 KB Output is correct
13 Correct 1348 ms 248788 KB Output is correct
14 Correct 1609 ms 248956 KB Output is correct
15 Correct 1348 ms 249040 KB Output is correct
16 Correct 1119 ms 248520 KB Output is correct
17 Correct 1182 ms 248420 KB Output is correct
18 Correct 1098 ms 248444 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 188664 KB Output is correct
2 Correct 177 ms 188920 KB Output is correct
3 Correct 286 ms 190200 KB Output is correct
4 Correct 222 ms 190200 KB Output is correct
5 Correct 218 ms 190072 KB Output is correct
6 Correct 212 ms 190072 KB Output is correct
7 Correct 223 ms 190180 KB Output is correct
8 Correct 236 ms 190072 KB Output is correct
9 Correct 236 ms 190072 KB Output is correct
10 Correct 254 ms 190200 KB Output is correct
11 Correct 251 ms 190200 KB Output is correct
12 Correct 256 ms 190200 KB Output is correct
13 Correct 263 ms 190192 KB Output is correct
14 Correct 263 ms 190200 KB Output is correct
15 Correct 268 ms 190072 KB Output is correct
16 Correct 276 ms 190188 KB Output is correct
17 Correct 281 ms 190180 KB Output is correct
18 Correct 274 ms 190072 KB Output is correct
19 Correct 536 ms 195960 KB Output is correct
20 Correct 598 ms 196856 KB Output is correct
21 Correct 508 ms 196600 KB Output is correct
22 Correct 616 ms 196604 KB Output is correct
23 Correct 765 ms 196600 KB Output is correct
24 Correct 743 ms 196600 KB Output is correct
25 Correct 829 ms 196856 KB Output is correct
26 Correct 829 ms 196728 KB Output is correct
27 Correct 867 ms 196860 KB Output is correct
28 Correct 860 ms 196740 KB Output is correct
29 Correct 423 ms 218688 KB Output is correct
30 Correct 2419 ms 235304 KB Output is correct
31 Correct 5049 ms 249436 KB Output is correct
32 Correct 5216 ms 249848 KB Output is correct
33 Correct 5505 ms 249764 KB Output is correct
34 Correct 5752 ms 249424 KB Output is correct
35 Correct 6040 ms 249464 KB Output is correct
36 Correct 6039 ms 249464 KB Output is correct
37 Correct 5290 ms 249484 KB Output is correct
38 Correct 1713 ms 248736 KB Output is correct
39 Correct 1806 ms 248688 KB Output is correct
40 Correct 1784 ms 248564 KB Output is correct
41 Correct 1348 ms 248788 KB Output is correct
42 Correct 1609 ms 248956 KB Output is correct
43 Correct 1348 ms 249040 KB Output is correct
44 Correct 1119 ms 248520 KB Output is correct
45 Correct 1182 ms 248420 KB Output is correct
46 Correct 1098 ms 248444 KB Output is correct
47 Execution timed out 9101 ms 398196 KB Time limit exceeded
48 Halted 0 ms 0 KB -