oj.uz

답안 #635274

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
635274 2022-08-25T20:44:53 Z racsosabe San (COCI17_san) C++14
120 / 120
 144 ms 21096 KB 
#include<bits/stdc++.h>
using namespace::std;

const int N = 50;
const int MAX = (1 << 20) + 5;

int n;
int h[N];
int c[N];
long long k;
int ft[MAX];

void get_paths(int pos, int end, int last, long long sum, int value, vector<pair<int, long long>> &values){
	if(pos == end){
		if(value == -2) value = last;
		if(value == -1) value = INT_MAX;
		values.emplace_back(make_pair(value, sum));
		return;
	}
	get_paths(pos + 1, end, last, sum, value, values);
	if(last <= h[pos]){
		if(value == -1) value = h[pos];
		get_paths(pos + 1, end, h[pos], sum + c[pos], value, values);
	}
}

int get_sum(int pos){
	pos++;
	int res = 0;
	while(pos > 0){
		res += ft[pos];
		pos &= pos - 1;
	}
	return res;
}

void update(int pos, int val){
	pos++;
	while(pos < MAX){
		ft[pos] += val;
		pos += (-pos) & pos;
	}
}

long long solve(vector<pair<int, long long>> &a, vector<pair<int, long long>> &b){
	sort(a.begin(), a.end());
	sort(b.begin(), b.end());
	vector<int> a_by_sum(a.size()), b_by_sum(b.size());
	iota(a_by_sum.begin(), a_by_sum.end(), 0);
	sort(a_by_sum.begin(), a_by_sum.end(), [&] (int i, int j){
		return a[i].second < a[j].second;
	});
	iota(b_by_sum.begin(), b_by_sum.end(), 0);
	sort(b_by_sum.begin(), b_by_sum.end(), [&] (int i, int j){
		return b[i].second < b[j].second;
	});
	long long ans = 0;
	int pos = b_by_sum.size() - 1;
	for(int i = 0; i < a_by_sum.size(); i++){
		while(pos >= 0 and a[a_by_sum[i]].second + b[b_by_sum[pos]].second >= k){
			update(b_by_sum[pos], 1);
			pos--;
		}
		int lo = lower_bound(b.begin(), b.end(), make_pair(a[a_by_sum[i]].first, 0ll)) - b.begin();
		ans += (int)b.size() - (pos + 1) - get_sum(lo - 1);
	}
	return ans;
}

int main(){
	scanf("%d %lld", &n, &k);
	for(int i = 0; i < n; i++) scanf("%d %d", h + i, c + i);
	if(n == 1){
		puts(c[0] >= k ? "1" : "0");
		return 0;
	}
	vector<pair<int, long long>> values1, values2;
	get_paths(0, n / 2, 0, 0, -2, values1);
	get_paths(n / 2, n, 0, 0, -1, values2);
	printf("%lld\n", solve(values1, values2));
	return 0;
}

Compilation message

san.cpp: In function 'long long int solve(std::vector<std::pair<int, long long int> >&, std::vector<std::pair<int, long long int> >&)':
san.cpp:59:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |  for(int i = 0; i < a_by_sum.size(); i++){
      |                 ~~^~~~~~~~~~~~~~~~~
san.cpp: In function 'int main()':
san.cpp:71:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |  scanf("%d %lld", &n, &k);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~
san.cpp:72:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |  for(int i = 0; i < n; i++) scanf("%d %d", h + i, c + i);
      |                             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
24.0 / 24.0

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

Subtask #2
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 308 KB Output is correct
2 Correct 1 ms 340 KB Output is correct

Subtask #3
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 2508 KB Output is correct
2 Correct 2 ms 564 KB Output is correct

Subtask #4
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 5320 KB Output is correct
2 Correct 5 ms 972 KB Output is correct

Subtask #5
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 144 ms 21096 KB Output is correct
2 Correct 24 ms 3704 KB Output is correct