oj.uz

Submission #82573

# Submission time Handle Problem Language Result Execution time Memory
82573 2018-10-31T13:55:06 Z wjoao San (COCI17_san) C++11
120 / 120
 489 ms 29432 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(ll i = 0; i < n; i++){
    if( (1LL<<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(ll i = n-1; i >= 0; i--){
    if( (1LL<<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 {
	ll valor, key, size, maior;
	Node *l, *r;

	Node(ll _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, ll 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(ll valor) {
		Node * l, * r;
		split(root, valor, l, r);
		root = merge(merge(l, new Node(valor)), r);
	}

	// Quantos valores existem maior igual que "valor"
	ll maioresIgualQue(ll valor){
		Node * l, * r;
		split(root, valor, l, r);
		ll 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-20LL) );
    for(ll bitmask = 1; bitmask < size_right; bitmask++){
      pll state = solve_right(bitmask << 20LL);
      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(long long int)':
san.cpp:40:12: warning: 'Node::r' will be initialized after [-Wreorder]
  Node *l, *r;
            ^
san.cpp:39:23: warning:   'long long int Node::maior' [-Wreorder]
  ll valor, key, size, maior;
                       ^~~~~
san.cpp:42:2: warning:   when initialized here [-Wreorder]
  Node(ll _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]);
                            ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 608 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 8744 KB Output is correct
2 Correct 18 ms 8744 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 291 ms 17064 KB Output is correct
2 Correct 16 ms 17064 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 17064 KB Output is correct
2 Correct 49 ms 17064 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 489 ms 29432 KB Output is correct
2 Correct 157 ms 29432 KB Output is correct