oj.uz

답안 #251080

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
251080 2020-07-20T05:54:20 Z kshitij_sodani Bubble Sort 2 (JOI18_bubblesort2) C++14
60 / 100
 9000 ms 399256 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
	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

# 결과 실행 시간 메모리 Grader output
1 Correct 176 ms 188664 KB Output is correct
2 Correct 189 ms 189048 KB Output is correct
3 Correct 227 ms 190188 KB Output is correct
4 Correct 224 ms 190072 KB Output is correct
5 Correct 240 ms 190252 KB Output is correct
6 Correct 250 ms 190200 KB Output is correct
7 Correct 246 ms 190200 KB Output is correct
8 Correct 268 ms 190072 KB Output is correct
9 Correct 267 ms 190348 KB Output is correct
10 Correct 239 ms 190204 KB Output is correct
11 Correct 244 ms 190072 KB Output is correct
12 Correct 262 ms 190188 KB Output is correct
13 Correct 279 ms 190132 KB Output is correct
14 Correct 285 ms 190368 KB Output is correct
15 Correct 255 ms 190072 KB Output is correct
16 Correct 264 ms 190072 KB Output is correct
17 Correct 286 ms 190072 KB Output is correct
18 Correct 256 ms 190072 KB Output is correct

Subtask #2
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 176 ms 188664 KB Output is correct
2 Correct 189 ms 189048 KB Output is correct
3 Correct 227 ms 190188 KB Output is correct
4 Correct 224 ms 190072 KB Output is correct
5 Correct 240 ms 190252 KB Output is correct
6 Correct 250 ms 190200 KB Output is correct
7 Correct 246 ms 190200 KB Output is correct
8 Correct 268 ms 190072 KB Output is correct
9 Correct 267 ms 190348 KB Output is correct
10 Correct 239 ms 190204 KB Output is correct
11 Correct 244 ms 190072 KB Output is correct
12 Correct 262 ms 190188 KB Output is correct
13 Correct 279 ms 190132 KB Output is correct
14 Correct 285 ms 190368 KB Output is correct
15 Correct 255 ms 190072 KB Output is correct
16 Correct 264 ms 190072 KB Output is correct
17 Correct 286 ms 190072 KB Output is correct
18 Correct 256 ms 190072 KB Output is correct
19 Correct 519 ms 195832 KB Output is correct
20 Correct 588 ms 196728 KB Output is correct
21 Correct 492 ms 196728 KB Output is correct
22 Correct 548 ms 196728 KB Output is correct
23 Correct 686 ms 196728 KB Output is correct
24 Correct 665 ms 196728 KB Output is correct
25 Correct 744 ms 196728 KB Output is correct
26 Correct 741 ms 196728 KB Output is correct
27 Correct 809 ms 196748 KB Output is correct
28 Correct 765 ms 196728 KB Output is correct

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 429 ms 218744 KB Output is correct
2 Correct 2444 ms 235504 KB Output is correct
3 Correct 5618 ms 249796 KB Output is correct
4 Correct 5446 ms 250008 KB Output is correct
5 Correct 5239 ms 250076 KB Output is correct
6 Correct 4963 ms 249796 KB Output is correct
7 Correct 5019 ms 250012 KB Output is correct
8 Correct 4983 ms 250092 KB Output is correct
9 Correct 4614 ms 249720 KB Output is correct
10 Correct 1645 ms 248912 KB Output is correct
11 Correct 1451 ms 248704 KB Output is correct
12 Correct 1502 ms 248704 KB Output is correct
13 Correct 1296 ms 248588 KB Output is correct
14 Correct 1321 ms 248620 KB Output is correct
15 Correct 1282 ms 248420 KB Output is correct
16 Correct 1066 ms 248700 KB Output is correct
17 Correct 1049 ms 248572 KB Output is correct
18 Correct 1029 ms 248572 KB Output is correct

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 176 ms 188664 KB Output is correct
2 Correct 189 ms 189048 KB Output is correct
3 Correct 227 ms 190188 KB Output is correct
4 Correct 224 ms 190072 KB Output is correct
5 Correct 240 ms 190252 KB Output is correct
6 Correct 250 ms 190200 KB Output is correct
7 Correct 246 ms 190200 KB Output is correct
8 Correct 268 ms 190072 KB Output is correct
9 Correct 267 ms 190348 KB Output is correct
10 Correct 239 ms 190204 KB Output is correct
11 Correct 244 ms 190072 KB Output is correct
12 Correct 262 ms 190188 KB Output is correct
13 Correct 279 ms 190132 KB Output is correct
14 Correct 285 ms 190368 KB Output is correct
15 Correct 255 ms 190072 KB Output is correct
16 Correct 264 ms 190072 KB Output is correct
17 Correct 286 ms 190072 KB Output is correct
18 Correct 256 ms 190072 KB Output is correct
19 Correct 519 ms 195832 KB Output is correct
20 Correct 588 ms 196728 KB Output is correct
21 Correct 492 ms 196728 KB Output is correct
22 Correct 548 ms 196728 KB Output is correct
23 Correct 686 ms 196728 KB Output is correct
24 Correct 665 ms 196728 KB Output is correct
25 Correct 744 ms 196728 KB Output is correct
26 Correct 741 ms 196728 KB Output is correct
27 Correct 809 ms 196748 KB Output is correct
28 Correct 765 ms 196728 KB Output is correct
29 Correct 429 ms 218744 KB Output is correct
30 Correct 2444 ms 235504 KB Output is correct
31 Correct 5618 ms 249796 KB Output is correct
32 Correct 5446 ms 250008 KB Output is correct
33 Correct 5239 ms 250076 KB Output is correct
34 Correct 4963 ms 249796 KB Output is correct
35 Correct 5019 ms 250012 KB Output is correct
36 Correct 4983 ms 250092 KB Output is correct
37 Correct 4614 ms 249720 KB Output is correct
38 Correct 1645 ms 248912 KB Output is correct
39 Correct 1451 ms 248704 KB Output is correct
40 Correct 1502 ms 248704 KB Output is correct
41 Correct 1296 ms 248588 KB Output is correct
42 Correct 1321 ms 248620 KB Output is correct
43 Correct 1282 ms 248420 KB Output is correct
44 Correct 1066 ms 248700 KB Output is correct
45 Correct 1049 ms 248572 KB Output is correct
46 Correct 1029 ms 248572 KB Output is correct
47 Execution timed out 9072 ms 399256 KB Time limit exceeded
48 Halted 0 ms 0 KB -