제출 #234472

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
234472		kshitij_sodani	운세 보기 2 (JOI14_fortune_telling2)	C++17	0 / 100	3054 ms	19456 KiB

fortune_telling2

#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
llo n,k;
llo aa[200001];
llo bb[200001];
llo pp[200001];

vector<llo> tree2[1];
vector<pair<llo,llo>> tree[800001];
llo build2(llo no1,llo no,llo l,llo r){
	if(l==r){
		tree2[no1][no]=tree[no1][l].b;
	}
	else{
		llo mid=(l+r)/2;
		build2(no1,no*2+1,l,mid);
		build2(no1,no*2+2,mid+1,r);

		tree2[no1][no]=max(tree2[no1][no*2+1],tree2[no1][no*2+2]);
		/*if(no1==0){
			cout<<tree2[no][no]<<","<<l<<","<<r<<endl;
		}*/
	}
}
llo query3(llo no1,llo no,llo l,llo r,llo aa,llo bb){
	if(r<aa or l>bb){
		return -1;
	}
	//cout<<l<<"..."<<r<<endl;
	if(aa<=l and r<=bb){

		return tree2[no1][no];
	}
	else{
		llo mid=(l+r)/2;

		return max(query3(no1,no*2+1,l,mid,aa,bb),query3(no1,no*2+2,mid+1,r,aa,bb));
	}
}
llo build(llo no,llo l,llo r){
	if(no==0){
		for(llo i=0;i<(r-l+1)*4;i++){
			tree2[no].pb(0);
		}
	}
	if(l==r){
		tree[no].pb({pp[l],l});
	}
	else{
		llo mid=(l+r)/2;
		build(no*2+1,l,mid);
		build(no*2+2,mid+1,r);
		llo ind=0;
		llo ind2=0;
		while(ind<tree[no*2+1].size() and ind2<tree[no*2+2].size()){
			if(tree[no*2+1][ind].a<tree[no*2+2][ind2].a){
				tree[no].pb(tree[no*2+1][ind]);
				ind+=1;
			}
			else{
				tree[no].pb(tree[no*2+2][ind2]);
				ind2+=1;
			}
		}
		while(ind<tree[no*2+1].size()){
			tree[no].pb(tree[no*2+1][ind]);
			ind+=1;
		}
		while(ind2<tree[no*2+2].size()){
			tree[no].pb(tree[no*2+2][ind2]);
			ind2+=1;
		}
	}
	if(no==0){
		build2(no,0,0,r-l);
	}
}
llo val1;
llo val2;
llo val3;
llo query(llo no,llo l,llo r,llo aa,llo bb){

		if(tree[no].back().a<val1){
			return -1;
		}
		if(tree[no][0].a>=val2){
			return -1;
		}
	//	cout<<l<<"::"<<r<<endl;
		llo low=0;
		llo high=r-l;
		

		while(low<high-1){
			llo mid=(l+r)/2;
			if(true){//tree[no][mid].a>=val1){
				high=mid;
			}
			else{
				low=mid;
			}
		}
		llo ind=high;
		if(tree[no][low].a>=val1){
			ind=min(ind,low);
		}
		low=0;
		high=r-l;
		while(low<high-1){
			llo mid=(l+r)/2;
			if(true){//tree[no][mid].a<val2){
				low=mid;
			}
			else{
				high=mid;
			}
		}
		llo ind2=low;
		if(tree[no][high].a<val2){
			ind2=max(ind2,high);
		}
	//	cout<<ind<<",,,,,"<<ind2<<endl;

		if(ind>ind2){
			return -1;
		}

		return query3(no,0,0,r-l,ind,ind2);

}
llo query2(llo no,llo l,llo r,llo aa,llo bb){
	if(r<aa or bb<l){
		return 0;
	}
	if(aa<=l and r<=bb){
		if(tree[no].back().a<val3){
			return 0;
		}

		llo low=0;
		llo high=r-l;
		while(low<high-1){
			llo mid=(l+r)/2;
			if(tree[no][mid].a>=val3){
				high=mid;
			}
			else{
				low=mid;
			}
		}
		llo ind=high;
		if(tree[no][low].a>=val3){
			ind=min(ind,low);
		}
		return (llo)(tree[no].size())-ind;
		
	}
	else{
		llo mid=(l+r)/2;
		return query2(no*2+1,l,mid,aa,bb)+query2(no*2+2,mid+1,r,aa,bb);
	}
}


int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n>>k;
	for(llo i=0;i<n;i++){
		cin>>aa[i];
		cin>>bb[i];
	}
	for(llo i=0;i<k;i++){
		cin>>pp[i];
	}
	build(0,0,k-1);
	llo ans=0;
	for(llo i=0;i<n;i++){
		val1=min(aa[i],bb[i]);
		val2=max(aa[i],bb[i]);
	//	cout<<val1<<"///"<<val2<<endl;
		llo indd=query(0,0,k-1,0,k-1);
		continue;

		indd+=1;
	//	cout<<i<<","<<indd-1<<endl;
		if(indd>=k){
			if(aa[i]<bb[i]){
				ans+=bb[i];
			}
			else if(bb[i]<aa[i]){
				ans+=aa[i];
			}
			continue;
		}
		val3=max(val1,val2);
		llo co=query2(0,0,k-1,indd,k-1);
		//cout<<co<<endl;
		llo st;
		if(indd==0){
			st=0;
		}
		else{
			if(aa[i]<bb[i]){
				st=1;
			}
			else{
				st=0;
			}
		}
		st+=co;
		st%=2;
		if(st==1){
			ans+=bb[i];
		}
		else{
			ans+=aa[i];
		}
	}
	cout<<ans<<endl;


	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

fortune_telling2.cpp: In function 'llo build2(llo, llo, llo, llo)':
fortune_telling2.cpp:29:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
fortune_telling2.cpp: In function 'llo build(llo, llo, llo)':
fortune_telling2.cpp:60:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(ind<tree[no*2+1].size() and ind2<tree[no*2+2].size()){
         ~~~^~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:60:41: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(ind<tree[no*2+1].size() and ind2<tree[no*2+2].size()){
                                     ~~~~^~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:70:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(ind<tree[no*2+1].size()){
         ~~~^~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:74:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(ind2<tree[no*2+2].size()){
         ~~~~^~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:82:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^

• Subtask 1: 0 / 4
• Subtask 2: 0 / 31
• Subtask 3: 0 / 65