oj.uz

답안 #251070

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
251070 2020-07-20T05:37:26 Z kshitij_sodani Bubble Sort 2 (JOI18_bubblesort2) C++14
38 / 100
 3921 ms 406940 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=500001;
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
	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){
			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:223:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(low==tt[i].size()){
        ~~~^~~~~~~~~~~~~~
bubblesort2.cpp:189:7: warning: unused variable 'kk' [-Wunused-variable]
   int kk=0;
       ^~

Subtask #1
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 315 ms 376568 KB Output is correct
2 Correct 351 ms 376696 KB Output is correct
3 Correct 481 ms 377976 KB Output is correct
4 Correct 482 ms 377980 KB Output is correct
5 Correct 472 ms 377964 KB Output is correct
6 Correct 454 ms 377964 KB Output is correct
7 Correct 443 ms 377976 KB Output is correct
8 Correct 467 ms 377976 KB Output is correct
9 Correct 459 ms 377964 KB Output is correct
10 Correct 453 ms 377976 KB Output is correct
11 Correct 449 ms 377976 KB Output is correct
12 Correct 459 ms 377968 KB Output is correct
13 Correct 477 ms 377976 KB Output is correct
14 Correct 475 ms 377976 KB Output is correct
15 Correct 461 ms 377976 KB Output is correct
16 Correct 499 ms 378232 KB Output is correct
17 Correct 492 ms 377976 KB Output is correct
18 Correct 516 ms 378044 KB Output is correct

Subtask #2
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 315 ms 376568 KB Output is correct
2 Correct 351 ms 376696 KB Output is correct
3 Correct 481 ms 377976 KB Output is correct
4 Correct 482 ms 377980 KB Output is correct
5 Correct 472 ms 377964 KB Output is correct
6 Correct 454 ms 377964 KB Output is correct
7 Correct 443 ms 377976 KB Output is correct
8 Correct 467 ms 377976 KB Output is correct
9 Correct 459 ms 377964 KB Output is correct
10 Correct 453 ms 377976 KB Output is correct
11 Correct 449 ms 377976 KB Output is correct
12 Correct 459 ms 377968 KB Output is correct
13 Correct 477 ms 377976 KB Output is correct
14 Correct 475 ms 377976 KB Output is correct
15 Correct 461 ms 377976 KB Output is correct
16 Correct 499 ms 378232 KB Output is correct
17 Correct 492 ms 377976 KB Output is correct
18 Correct 516 ms 378044 KB Output is correct
19 Correct 2516 ms 383780 KB Output is correct
20 Correct 3305 ms 384768 KB Output is correct
21 Correct 3023 ms 384892 KB Output is correct
22 Correct 2807 ms 385144 KB Output is correct
23 Correct 3012 ms 384888 KB Output is correct
24 Correct 2922 ms 384904 KB Output is correct
25 Correct 3424 ms 384888 KB Output is correct
26 Correct 3635 ms 384856 KB Output is correct
27 Correct 3921 ms 384904 KB Output is correct
28 Correct 3874 ms 384968 KB Output is correct

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2987 ms 406940 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 315 ms 376568 KB Output is correct
2 Correct 351 ms 376696 KB Output is correct
3 Correct 481 ms 377976 KB Output is correct
4 Correct 482 ms 377980 KB Output is correct
5 Correct 472 ms 377964 KB Output is correct
6 Correct 454 ms 377964 KB Output is correct
7 Correct 443 ms 377976 KB Output is correct
8 Correct 467 ms 377976 KB Output is correct
9 Correct 459 ms 377964 KB Output is correct
10 Correct 453 ms 377976 KB Output is correct
11 Correct 449 ms 377976 KB Output is correct
12 Correct 459 ms 377968 KB Output is correct
13 Correct 477 ms 377976 KB Output is correct
14 Correct 475 ms 377976 KB Output is correct
15 Correct 461 ms 377976 KB Output is correct
16 Correct 499 ms 378232 KB Output is correct
17 Correct 492 ms 377976 KB Output is correct
18 Correct 516 ms 378044 KB Output is correct
19 Correct 2516 ms 383780 KB Output is correct
20 Correct 3305 ms 384768 KB Output is correct
21 Correct 3023 ms 384892 KB Output is correct
22 Correct 2807 ms 385144 KB Output is correct
23 Correct 3012 ms 384888 KB Output is correct
24 Correct 2922 ms 384904 KB Output is correct
25 Correct 3424 ms 384888 KB Output is correct
26 Correct 3635 ms 384856 KB Output is correct
27 Correct 3921 ms 384904 KB Output is correct
28 Correct 3874 ms 384968 KB Output is correct
29 Incorrect 2987 ms 406940 KB Output isn't correct
30 Halted 0 ms 0 KB -