Submission #82571

#TimeUsernameProblemLanguageResultExecution timeMemory
82571wjoaoSan (COCI17_san)C++11
48 / 120
543 ms37432 KiB
#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(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); } } 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++){ if(l[i].second >= k) res++; 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 (stderr)

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:132:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(ll i = 0; i < l.size(); i++){
                 ~~^~~~~~~~~~
san.cpp:135: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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...