| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 82572 |
2018-10-31T13:51:48 Z |
wjoao |
San (COCI17_san) |
C++11 |
|
541 ms |
37604 KB |
#include<bits/stdc++.h>
#define ll long long
#define pll pair<ll, ll>
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
ll n, k, h[50], g[50], res;
pll solve_left(ll bitmask){
pll r;
for(int i = 0; i < n; i++){
if( (1<<i) & bitmask ){
if(h[i] < r.first) return make_pair(-1, -1);
r.first = h[i];
r.second += g[i];
}
}
return r;
}
pll solve_right(ll bitmask){
pll r; r.first = inf;
for(int i = n-1; i >= 0; i--){
if( (1<<i) & bitmask ){
if(h[i] > r.first) return make_pair(inf, -1);
r.first = h[i];
r.second += g[i];
}
}
return r;
}
vector< pll > l, r;
struct Node {
int valor, key, size, maior;
Node *l, *r;
Node(int _valor) : valor(_valor), key((rand() << 16) ^ rand()), size(1), l(NULL), r(NULL), maior(_valor) {}
~Node() { delete l; delete r; }
void recalc() {
size = 1;
maior = valor;
if (l) size += l->size, maior = max(maior, l->maior);
if (r) size += r->size, maior = max(maior, r->maior);
}
};
struct Treap {
Node * merge(Node * l, Node * r) {
if (!l || !r) return l ? l : r;
// Se a prioridade esquerda é menor.
if (l->key < r->key) {
l->r = merge(l->r, r);
l->recalc();
return l;
// Se a prioridade direita é maior ou igual.
} else {
r->l = merge(l, r->l);
r->recalc();
return r;
}
}
// Valores maiores ou iguais a "valor" ficarão no r, e os demais no l.
void split(Node * v, int valor, Node *& l, Node *& r) {
l = r = NULL;
if (!v) return;
// Se o valor for maior, ir para direita
if (v->valor < valor) {
split(v->r, valor, v->r, r);
l = v;
// Se o valor for menor ou igual ir para esquerda.
} else {
split(v->l, valor, l, v->l);
r = v;
}
v->recalc();
}
Node * root;
Treap() : root(NULL) {}
~Treap() { delete root; }
// Insere o valor mesmo se já exista outro com valor igual
void insert(int valor) {
Node * l, * r;
split(root, valor, l, r);
root = merge(merge(l, new Node(valor)), r);
}
// Quantos valores existem maior igual que "valor"
int maioresIgualQue(int valor){
Node * l, * r;
split(root, valor, l, r);
int res = (r? r->size: 0);
root = merge(l,r);
return res;
}
} treap;
int main(){
scanf(" %lld %lld", &n, &k);
for(ll i = 0; i < n; i++)scanf(" %lld %lld", &h[i], &g[i]);
ll size_left = (1LL << min(20LL, n));
for(ll bitmask = 1; bitmask < size_left; bitmask++){
pll state = solve_left(bitmask);
if(state.first > 0){
l.push_back(state);
if(state.second >= k) res++;
}
}
if(n > 20){
ll size_right = (1LL << (n-20) );
for(ll bitmask = 1; bitmask < size_right; bitmask++){
pll state = solve_right(bitmask << 20);
if(state.first != inf){
r.push_back(state);
if(state.second >= k) res++;
}
}
}
sort(l.begin(), l.end());
reverse(l.begin(), l.end());
sort(r.begin(), r.end());
reverse(r.begin(), r.end());
ll j = 0;
for(ll i = 0; i < l.size(); i++){
while(j < r.size() && r[j].first >= l[i].first){
treap.insert(r[j].second);
j++;
}
res += treap.maioresIgualQue(k-l[i].second);
}
printf("%lld\n", res);
return 0;
}
Compilation message
san.cpp: In constructor 'Node::Node(int)':
san.cpp:40:12: warning: 'Node::r' will be initialized after [-Wreorder]
Node *l, *r;
^
san.cpp:39:24: warning: 'int Node::maior' [-Wreorder]
int valor, key, size, maior;
^~~~~
san.cpp:42:2: warning: when initialized here [-Wreorder]
Node(int _valor) : valor(_valor), key((rand() << 16) ^ rand()), size(1), l(NULL), r(NULL), maior(_valor) {}
^~~~
san.cpp: In function 'int main()':
san.cpp:138:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(ll i = 0; i < l.size(); i++){
~~^~~~~~~~~~
san.cpp:139:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(j < r.size() && r[j].first >= l[i].first){
~~^~~~~~~~~~
san.cpp:110:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf(" %lld %lld", &n, &k);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
san.cpp:111:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(ll i = 0; i < n; i++)scanf(" %lld %lld", &h[i], &g[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
3 ms |
636 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
124 ms |
8748 KB |
Output is correct |
| 2 |
Correct |
27 ms |
8748 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
481 ms |
17088 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
116 ms |
17088 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
541 ms |
37604 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
