Submission #406371

#	Time	Username	Problem	Language	Result	Execution time	Memory
406371		pure_mem	Teams (IOI15_teams)	C++14	77 / 100	4101 ms	368636 KiB

teams

#include "teams.h"
#include <bits/stdc++.h>

#define X first
#define Y second
#define MP make_pair
#define ll long long

using namespace std;

const int MAXN = 5e5 + 12, BS = 300;

struct node{
	int val = 0;
	node *l = nullptr, *r = nullptr;
	node(int _val = 0, node* _l = nullptr, node* _r = nullptr){
		val = _val, l = _l, r = _r;
	}
};
int getVal(node* v){
	return v ? v->val: 0;
}
node* upd(node* v, int tl, int tr, int pos, int val){
	if(tl == tr) return new node(getVal(v) + val);
	int tm = (tl + tr) / 2;
	if(pos <= tm) v = new node(0, upd(v ? v->l: v, tl, tm, pos, val), v ? v->r: v);
	else v = new node(0, v ? v->l: v, upd(v ? v->r: v, tm + 1, tr, pos, val));
	v->val = getVal(v->l) + getVal(v->r);
	return v;
}
int get(node* v, int tl, int tr, int l, int r){
	if(tl > r || l > tr) return 0;
	if(tl >= l && tr <= r) return getVal(v);
	int tm = (tl + tr) / 2;
	return (v->l ? get(v->l, tl, tm, l, r): 0) + (v->r ? get(v->r, tm + 1, tr, l, r): 0);
}
node* root[MAXN];

int n, dp[MAXN];
vector< int > rv[MAXN], mine[MAXN];

void init(int N, int A[], int B[]) {
	n = N, root[0] = new node();
	for(int i = 0;i < n;i++)
		rv[n - B[i] + 1].push_back(A[i]), mine[A[i]].push_back(B[i]);
	for(int i = 1;i <= n;i++){
		root[i] = root[i - 1];
		for(int v: rv[i]){
			root[i] = upd(root[i], 1, n, v, 1);
		}
	}			
}

int can(int M, int K[]) {
	sort(K, K + M);
	if(M <= BS){
    	for(int i = 0;i < M;i++){
    		dp[i] = get(root[n - K[i] + 1], 1, n, 1, K[i]) - K[i];
    		for(int j = 0;j < i;j++){
    			dp[i] = min(dp[i], dp[j] + get(root[n - K[i] + 1], 1, n, K[j] + 1, K[i]) - K[i]);
    		}
    		if(dp[i] < 0) return 0;
    	}
	}
	else{
		priority_queue< int > st;
		for(int i = 1, j = 0;i <= n && j < M;i++){
			while(!st.empty() && -st.top() < i)
				st.pop();
			for(int v: mine[i])
				st.push(-v);
			while(K[j] == i){
				if(i > st.size()) return 0;
				while(K[j]--) st.pop();
				j++;		
			}
		}
	}
	return 1;
}

Compilation message (stderr)

teams.cpp: In function 'int can(int, int*)':
teams.cpp:73:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::priority_queue<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |     if(i > st.size()) return 0;
      |        ~~^~~~~~~~~~~

• Subtask 1: 21 / 21
• Subtask 2: 13 / 13
• Subtask 3: 43 / 43
• Subtask 4: 0 / 23