oj.uz

답안 #251088

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
251088 2020-07-20T06:06:10 Z kshitij_sodani Bubble Sort 2 (JOI18_bubblesort2) C++14
60 / 100
 9000 ms 399196 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=700;
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
	//nlogn
	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 nlogn
	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
	//n*root*logn
	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:237:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(low==tt[i].size()){
        ~~~^~~~~~~~~~~~~~
bubblesort2.cpp:201:7: warning: unused variable 'kk' [-Wunused-variable]
   int kk=0;
       ^~

Subtask #1
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 170 ms 188664 KB Output is correct
2 Correct 174 ms 188952 KB Output is correct
3 Correct 216 ms 190124 KB Output is correct
4 Correct 233 ms 190072 KB Output is correct
5 Correct 242 ms 190072 KB Output is correct
6 Correct 197 ms 190072 KB Output is correct
7 Correct 210 ms 190076 KB Output is correct
8 Correct 224 ms 190072 KB Output is correct
9 Correct 215 ms 190072 KB Output is correct
10 Correct 240 ms 190200 KB Output is correct
11 Correct 240 ms 190200 KB Output is correct
12 Correct 244 ms 190072 KB Output is correct
13 Correct 254 ms 190200 KB Output is correct
14 Correct 253 ms 190072 KB Output is correct
15 Correct 244 ms 190204 KB Output is correct
16 Correct 252 ms 190072 KB Output is correct
17 Correct 252 ms 190060 KB Output is correct
18 Correct 266 ms 190072 KB Output is correct

Subtask #2
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 170 ms 188664 KB Output is correct
2 Correct 174 ms 188952 KB Output is correct
3 Correct 216 ms 190124 KB Output is correct
4 Correct 233 ms 190072 KB Output is correct
5 Correct 242 ms 190072 KB Output is correct
6 Correct 197 ms 190072 KB Output is correct
7 Correct 210 ms 190076 KB Output is correct
8 Correct 224 ms 190072 KB Output is correct
9 Correct 215 ms 190072 KB Output is correct
10 Correct 240 ms 190200 KB Output is correct
11 Correct 240 ms 190200 KB Output is correct
12 Correct 244 ms 190072 KB Output is correct
13 Correct 254 ms 190200 KB Output is correct
14 Correct 253 ms 190072 KB Output is correct
15 Correct 244 ms 190204 KB Output is correct
16 Correct 252 ms 190072 KB Output is correct
17 Correct 252 ms 190060 KB Output is correct
18 Correct 266 ms 190072 KB Output is correct
19 Correct 477 ms 195984 KB Output is correct
20 Correct 604 ms 196856 KB Output is correct
21 Correct 469 ms 196728 KB Output is correct
22 Correct 589 ms 196728 KB Output is correct
23 Correct 659 ms 196900 KB Output is correct
24 Correct 660 ms 196728 KB Output is correct
25 Correct 747 ms 196764 KB Output is correct
26 Correct 718 ms 196728 KB Output is correct
27 Correct 731 ms 196732 KB Output is correct
28 Correct 754 ms 196728 KB Output is correct

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 413 ms 218744 KB Output is correct
2 Correct 2227 ms 235384 KB Output is correct
3 Correct 5008 ms 249932 KB Output is correct
4 Correct 4944 ms 249824 KB Output is correct
5 Correct 4620 ms 249720 KB Output is correct
6 Correct 4641 ms 249636 KB Output is correct
7 Correct 4450 ms 249720 KB Output is correct
8 Correct 4618 ms 249968 KB Output is correct
9 Correct 4568 ms 249720 KB Output is correct
10 Correct 1477 ms 248704 KB Output is correct
11 Correct 1528 ms 249008 KB Output is correct
12 Correct 1676 ms 248976 KB Output is correct
13 Correct 1243 ms 248572 KB Output is correct
14 Correct 1435 ms 248572 KB Output is correct
15 Correct 1456 ms 248572 KB Output is correct
16 Correct 1094 ms 248700 KB Output is correct
17 Correct 1127 ms 248788 KB Output is correct
18 Correct 1081 ms 248512 KB Output is correct

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 170 ms 188664 KB Output is correct
2 Correct 174 ms 188952 KB Output is correct
3 Correct 216 ms 190124 KB Output is correct
4 Correct 233 ms 190072 KB Output is correct
5 Correct 242 ms 190072 KB Output is correct
6 Correct 197 ms 190072 KB Output is correct
7 Correct 210 ms 190076 KB Output is correct
8 Correct 224 ms 190072 KB Output is correct
9 Correct 215 ms 190072 KB Output is correct
10 Correct 240 ms 190200 KB Output is correct
11 Correct 240 ms 190200 KB Output is correct
12 Correct 244 ms 190072 KB Output is correct
13 Correct 254 ms 190200 KB Output is correct
14 Correct 253 ms 190072 KB Output is correct
15 Correct 244 ms 190204 KB Output is correct
16 Correct 252 ms 190072 KB Output is correct
17 Correct 252 ms 190060 KB Output is correct
18 Correct 266 ms 190072 KB Output is correct
19 Correct 477 ms 195984 KB Output is correct
20 Correct 604 ms 196856 KB Output is correct
21 Correct 469 ms 196728 KB Output is correct
22 Correct 589 ms 196728 KB Output is correct
23 Correct 659 ms 196900 KB Output is correct
24 Correct 660 ms 196728 KB Output is correct
25 Correct 747 ms 196764 KB Output is correct
26 Correct 718 ms 196728 KB Output is correct
27 Correct 731 ms 196732 KB Output is correct
28 Correct 754 ms 196728 KB Output is correct
29 Correct 413 ms 218744 KB Output is correct
30 Correct 2227 ms 235384 KB Output is correct
31 Correct 5008 ms 249932 KB Output is correct
32 Correct 4944 ms 249824 KB Output is correct
33 Correct 4620 ms 249720 KB Output is correct
34 Correct 4641 ms 249636 KB Output is correct
35 Correct 4450 ms 249720 KB Output is correct
36 Correct 4618 ms 249968 KB Output is correct
37 Correct 4568 ms 249720 KB Output is correct
38 Correct 1477 ms 248704 KB Output is correct
39 Correct 1528 ms 249008 KB Output is correct
40 Correct 1676 ms 248976 KB Output is correct
41 Correct 1243 ms 248572 KB Output is correct
42 Correct 1435 ms 248572 KB Output is correct
43 Correct 1456 ms 248572 KB Output is correct
44 Correct 1094 ms 248700 KB Output is correct
45 Correct 1127 ms 248788 KB Output is correct
46 Correct 1081 ms 248512 KB Output is correct
47 Execution timed out 9055 ms 399196 KB Time limit exceeded
48 Halted 0 ms 0 KB -