Submission #132563

#	Time	Username	Problem	Language	Result	Execution time	Memory
132563		someone_aa	Teams (IOI15_teams)	C++17	77 / 100	1714 ms	524292 KiB

teams

#include "teams.h"
#include <bits/stdc++.h>
#define ll long long 
#define pb push_back
#define mp make_pair
using namespace std;
const int maxn = 500100; // WARNING: SMALL N
int n;

class node {
public:
	node *l, *r;
	int s;

	node(int _s) {
		s = _s;
		l = r = NULL;
	}
	node(node *lc, node *rc) {
		l = lc; r = rc;
		s = l -> s + r -> s;
	}
};

vector<int>bs[maxn];
node *zero;

node *build(int li=1, int ri=n) {
	if(li == ri) return zero;
	else {
		int mid = (li + ri) / 2;
		return new node(build(li, mid), build(mid+1, ri));
	}
}

node *update(node *curr, int x, int li=1, int ri=n) {
	if(li == ri) {
		return new node(curr->s+1);
	}
	else {
		int mid = (li + ri) / 2;
		if(x <= mid) return new node(update(curr->l, x, li, mid), curr->r);
		else return new node(curr->l, update(curr->r, x, mid+1, ri));
	}
}

// It creates new segment tree such that it takes the first d leafs from f_part
// and the rest of the n - d are from s_part
node *removefirst(int d, node *f_part, node *s_part, int li=1, int ri=n) {
	if(li > d) return s_part;
	else if(ri <= d) return f_part;

	if(li != ri) {
		int mid = (li + ri) / 2;
		return new node(removefirst(d, f_part->l, s_part->l, li, mid), removefirst(d, f_part->r, s_part->r, mid+1, ri));
	}
}

// Takes the first k extra from available that are not in used
node *mergeused(int k, node *available, node *used, int li=1, int ri=n) {
	if(li == ri) {
		return new node(used->s + k);
	}
	else {
		int mid = (li + ri) / 2;
		int l_part = available->l->s - used->l->s;

		if(l_part >= k)
			return new node(mergeused(k, available->l, used->l, li, mid), used->r);
		else 
			return new node(available->l, mergeused(k - l_part, available->r, used->r, mid+1, ri));
	}

}

node *emp;
node *persistent_tree[maxn];

void init(int N, int A[], int B[]) {
	n = N;
	for(int i=0;i<n;i++) {
		bs[A[i]].pb(B[i]);
	}

	zero = new node(0);
	emp = build();
	persistent_tree[0] = emp;
	for(int i=1;i<=n;i++) {
		persistent_tree[i] = persistent_tree[i-1];
		persistent_tree[i] = removefirst(i-1, emp, persistent_tree[i]); // We don't care for the interavals starting before my position

		for(int j:bs[i]) {
			persistent_tree[i] = update(persistent_tree[i], j);
		}	
	}
}

int can(int M, int K[]) {
	sort(K, K+M);
	node *used = emp;
	for(int i=0;i<M;i++) {
		used = removefirst(K[i]-1, emp, used);
		if(persistent_tree[K[i]]->s - used->s < K[i]) return 0;
		used = mergeused(K[i], persistent_tree[K[i]], used);
	}
	return 1;
}

Compilation message (stderr)

teams.cpp: In function 'node* removefirst(int, node*, node*, int, int)':
teams.cpp:57:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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