Submission #82572

#	Time	Username	Problem	Language	Result	Execution time	Memory
82572		wjoao	San (COCI17_san)	C++11	48 / 120	541 ms	37604 KiB

san

#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 (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: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 / 24
• Subtask 2: 24 / 24
• Subtask 3: 0 / 24
• Subtask 4: 0 / 24
• Subtask 5: 0 / 24