| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 635274 |
2022-08-25T20:44:53 Z |
racsosabe |
San (COCI17_san) |
C++14 |
|
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);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
308 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
2508 KB |
Output is correct |
| 2 |
Correct |
2 ms |
564 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
5320 KB |
Output is correct |
| 2 |
Correct |
5 ms |
972 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
144 ms |
21096 KB |
Output is correct |
| 2 |
Correct |
24 ms |
3704 KB |
Output is correct |
