oj.uz

Submission #251083

# Submission time Handle Problem Language Result Execution time Memory
251083 2020-07-20T05:56:56 Z kshitij_sodani Bubble Sort 2 (JOI18_bubblesort2) C++14
60 / 100
 9000 ms 397876 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=500;
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 166 ms 188664 KB Output is correct
2 Correct 174 ms 188920 KB Output is correct
3 Correct 214 ms 190072 KB Output is correct
4 Correct 217 ms 190072 KB Output is correct
5 Correct 202 ms 190200 KB Output is correct
6 Correct 193 ms 190072 KB Output is correct
7 Correct 206 ms 190072 KB Output is correct
8 Correct 201 ms 190072 KB Output is correct
9 Correct 210 ms 190072 KB Output is correct
10 Correct 251 ms 190072 KB Output is correct
11 Correct 236 ms 190072 KB Output is correct
12 Correct 246 ms 190204 KB Output is correct
13 Correct 247 ms 190072 KB Output is correct
14 Correct 246 ms 190072 KB Output is correct
15 Correct 244 ms 190072 KB Output is correct
16 Correct 253 ms 190072 KB Output is correct
17 Correct 256 ms 190072 KB Output is correct
18 Correct 291 ms 190076 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 188664 KB Output is correct
2 Correct 174 ms 188920 KB Output is correct
3 Correct 214 ms 190072 KB Output is correct
4 Correct 217 ms 190072 KB Output is correct
5 Correct 202 ms 190200 KB Output is correct
6 Correct 193 ms 190072 KB Output is correct
7 Correct 206 ms 190072 KB Output is correct
8 Correct 201 ms 190072 KB Output is correct
9 Correct 210 ms 190072 KB Output is correct
10 Correct 251 ms 190072 KB Output is correct
11 Correct 236 ms 190072 KB Output is correct
12 Correct 246 ms 190204 KB Output is correct
13 Correct 247 ms 190072 KB Output is correct
14 Correct 246 ms 190072 KB Output is correct
15 Correct 244 ms 190072 KB Output is correct
16 Correct 253 ms 190072 KB Output is correct
17 Correct 256 ms 190072 KB Output is correct
18 Correct 291 ms 190076 KB Output is correct
19 Correct 529 ms 195960 KB Output is correct
20 Correct 541 ms 196728 KB Output is correct
21 Correct 436 ms 196728 KB Output is correct
22 Correct 558 ms 196600 KB Output is correct
23 Correct 656 ms 196856 KB Output is correct
24 Correct 656 ms 196600 KB Output is correct
25 Correct 719 ms 196728 KB Output is correct
26 Correct 687 ms 196728 KB Output is correct
27 Correct 715 ms 196676 KB Output is correct
28 Correct 779 ms 196600 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 443 ms 218872 KB Output is correct
2 Correct 2618 ms 235256 KB Output is correct
3 Correct 5910 ms 249464 KB Output is correct
4 Correct 5932 ms 249464 KB Output is correct
5 Correct 5569 ms 249464 KB Output is correct
6 Correct 5403 ms 249464 KB Output is correct
7 Correct 4783 ms 249444 KB Output is correct
8 Correct 4224 ms 249464 KB Output is correct
9 Correct 4338 ms 249464 KB Output is correct
10 Correct 1435 ms 248504 KB Output is correct
11 Correct 1467 ms 248772 KB Output is correct
12 Correct 1637 ms 248596 KB Output is correct
13 Correct 1239 ms 248984 KB Output is correct
14 Correct 1327 ms 248840 KB Output is correct
15 Correct 1341 ms 248948 KB Output is correct
16 Correct 1071 ms 248568 KB Output is correct
17 Correct 1104 ms 248452 KB Output is correct
18 Correct 1098 ms 248560 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 188664 KB Output is correct
2 Correct 174 ms 188920 KB Output is correct
3 Correct 214 ms 190072 KB Output is correct
4 Correct 217 ms 190072 KB Output is correct
5 Correct 202 ms 190200 KB Output is correct
6 Correct 193 ms 190072 KB Output is correct
7 Correct 206 ms 190072 KB Output is correct
8 Correct 201 ms 190072 KB Output is correct
9 Correct 210 ms 190072 KB Output is correct
10 Correct 251 ms 190072 KB Output is correct
11 Correct 236 ms 190072 KB Output is correct
12 Correct 246 ms 190204 KB Output is correct
13 Correct 247 ms 190072 KB Output is correct
14 Correct 246 ms 190072 KB Output is correct
15 Correct 244 ms 190072 KB Output is correct
16 Correct 253 ms 190072 KB Output is correct
17 Correct 256 ms 190072 KB Output is correct
18 Correct 291 ms 190076 KB Output is correct
19 Correct 529 ms 195960 KB Output is correct
20 Correct 541 ms 196728 KB Output is correct
21 Correct 436 ms 196728 KB Output is correct
22 Correct 558 ms 196600 KB Output is correct
23 Correct 656 ms 196856 KB Output is correct
24 Correct 656 ms 196600 KB Output is correct
25 Correct 719 ms 196728 KB Output is correct
26 Correct 687 ms 196728 KB Output is correct
27 Correct 715 ms 196676 KB Output is correct
28 Correct 779 ms 196600 KB Output is correct
29 Correct 443 ms 218872 KB Output is correct
30 Correct 2618 ms 235256 KB Output is correct
31 Correct 5910 ms 249464 KB Output is correct
32 Correct 5932 ms 249464 KB Output is correct
33 Correct 5569 ms 249464 KB Output is correct
34 Correct 5403 ms 249464 KB Output is correct
35 Correct 4783 ms 249444 KB Output is correct
36 Correct 4224 ms 249464 KB Output is correct
37 Correct 4338 ms 249464 KB Output is correct
38 Correct 1435 ms 248504 KB Output is correct
39 Correct 1467 ms 248772 KB Output is correct
40 Correct 1637 ms 248596 KB Output is correct
41 Correct 1239 ms 248984 KB Output is correct
42 Correct 1327 ms 248840 KB Output is correct
43 Correct 1341 ms 248948 KB Output is correct
44 Correct 1071 ms 248568 KB Output is correct
45 Correct 1104 ms 248452 KB Output is correct
46 Correct 1098 ms 248560 KB Output is correct
47 Execution timed out 9115 ms 397876 KB Time limit exceeded
48 Halted 0 ms 0 KB -