oj.uz

답안 #681877

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
681877 2023-01-14T18:20:15 Z Doncho_Bonboncho San (COCI17_san) C++14
72 / 120
 125 ms 54568 KB 
#include <algorithm>
#include <bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

const int MAX_N = 1e6;
const int INF = 1e9;
const int mod = 1e9 + 7;

int n, k;

std::vector<ll> L[MAX_N];
std::vector<ll> R[MAX_N];

ll h[MAX_N];
ll c[MAX_N];

std::vector<int> hs; 
void rec_left(int pos, int last, ll sum) {
	if (pos == n/2) {
		int idx = lower_bound(hs.begin(), hs.end(), last) - hs.begin();
		L[idx].push_back(sum);
		return;
	}
	rec_left(pos+1, last, sum);
	if (h[pos] >= last) {
		rec_left(pos+1, h[pos], sum + c[pos]);
	}
}

void rec_right(int pos, int first, int last, ll sum) {
	if (pos == n) {
		int idx = lower_bound(hs.begin(), hs.end(), first) - hs.begin();
		R[idx].push_back(sum);
		return;
	}
	rec_right(pos+1, first, last, sum);
	if (h[pos] >= last) {
		int nfirst = (first == 0) ? h[pos] : first;
		rec_right(pos+1, nfirst, h[pos], sum + c[pos]);
	}
}
void left( int pos, int currH, int sum ){
	if( pos == n/2 ){
		int ind = std::lower_bound( hs.begin(), hs.end(), currH ) - hs.begin();
		L[ind].push_back(sum);
		return;
	}

	left( pos +1, currH, sum );
	if( currH <= h[pos] ){
		left( pos +1, h[pos], sum + c[pos] );
	}
}

void right( int pos, int first, int currH, int sum ){
	if( pos == n ){
		int ind = std::lower_bound( hs.begin(), hs.end(), first ) - hs.begin();
		R[ind].push_back( sum );	
		return ;
	}

	right( pos +1, first, currH, sum );
	if( h[pos] >= currH ){
		if( first == 0 ) first = h[pos];
		right( pos +1, first, h[pos], sum + c[pos] );
	}
}

int main () {

	std::ios_base::sync_with_stdio(false); std::cin.tie(NULL);

	std::cin>>n>>k;
	for( int i=0 ; i<n ; i++ ){
		std::cin>>h[i]>>c[i];
		hs.push_back( h[i] );
	}
	hs.push_back(0);
	std::sort( hs.begin(), hs.end() );

	/*
	left( 0, 0, 0 );
	right(n/2, 0, 0, 0);
	*/
	rec_left( 0, 0, 0 );
	rec_right( n/2, 0, 0, 0 );
	/*
	   std::cerr<<" L:\n";
	   for( int i=0 ; i<n ; i++ ){
	   std::cerr<<i<<" : ";
	   for( auto j : L[i] ){
	   std::cerr<<j<<" ";
	   }
	   std::cerr<<"\n";
	   }

	   std::cerr<<" R:\n";
	   for( int i=0 ; i<n ; i++ ){
	   std::cerr<<i<<" : ";
	   for( auto j : R[i] ){
	   std::cerr<<j<<" ";
	   }
	   std::cerr<<"\n";
	   }
	 */

	for( int i=0 ; i<(int)hs.size() ; i++ ) std::sort( R[i].begin(), R[i].end() );

	ll nas = 0;
	for( int i=0 ; i<(int)hs.size(); i++ ){

		//	std::cerr<<i<<":\n";
		for( auto it : L[i] ){
			nas += R[0].end() - std::lower_bound( R[0].begin(), R[0].end(), k - it );
			//		std::cerr<<"	"<<it<<"\n";
			for( int j=i ; j<(int)hs.size() ; j++ ){
				ll currNas = R[j].end() - std::lower_bound( R[j].begin(), R[j].end(), k-it );
				//			std::cerr<<"	  # "<<j<<" "<<currNas<<"\n";
				nas += currNas;
			}
		}
	}

	std::cout<<nas<<"\n";

	return 0;
}

Subtask #1
0 / 24.0

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

Subtask #2
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 47196 KB Output is correct
2 Incorrect 24 ms 47192 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 48200 KB Output is correct
2 Correct 23 ms 47316 KB Output is correct

Subtask #4
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 48976 KB Output is correct
2 Correct 30 ms 47432 KB Output is correct

Subtask #5
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 125 ms 54568 KB Output is correct
2 Correct 40 ms 48620 KB Output is correct