Submission #132571

#	Time	Username	Problem	Language	Result	Execution time	Memory
132571		someone_aa	Teams (IOI15_teams)	C++17	100 / 100	2643 ms	351244 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>value, l, r;

int makenewleaf(int s) {
	value.pb(s);
	l.pb(-1);
	r.pb(-1);
	return value.size() - 1;
}

int makenewparent(int lchild, int rchild) {
	value.pb(value[lchild] + value[rchild]);
	l.pb(lchild);
	r.pb(rchild);
	return value.size() - 1;
}

vector<int>bs[maxn];

int build(int li=1, int ri=n) {
	if(li == ri) return makenewleaf(0);
	else {
		int mid = (li + ri) / 2;
		return makenewparent(build(li, mid), build(mid+1, ri));
	}
}

int update(int curr, int x, int li=1, int ri=n) {
	if(li == ri) {
		return makenewleaf(value[curr]+1);
	}
	else {
		int mid = (li + ri) / 2;
		if(x <= mid) return makenewparent(update(l[curr], x, li, mid), r[curr]);
		else return makenewparent(l[curr], update(r[curr], 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
int removefirst(int d, int f_part, int 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 makenewparent(removefirst(d, l[f_part], l[s_part], li, mid), removefirst(d, r[f_part], r[s_part], mid+1, ri));
	}
}

// Takes the first k extra from available that are not in used
int mergeused(int k, int available, int used, int li=1, int ri=n) {
	if(li == ri) {
		return makenewleaf(value[used] + k);
	}
	else {
		int mid = (li + ri) / 2;
		int l_part = value[l[available]] - value[l[used]];

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

}

int emp;
int 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]);
	}

	
	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);
	int used = emp;
	for(int i=0;i<M;i++) {
		used = removefirst(K[i]-1, emp, used);
		if(value[persistent_tree[K[i]]] - value[used] < K[i]) return 0;
		used = mergeused(K[i], persistent_tree[K[i]], used);
	}
	return 1;
}

Compilation message (stderr)

teams.cpp: In function 'int makenewleaf(int)':
teams.cpp:31:22: warning: conversion to 'int' from 'std::vector<int>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
  return value.size() - 1;
         ~~~~~~~~~~~~~^~~
teams.cpp: In function 'int makenewparent(int, int)':
teams.cpp:38:22: warning: conversion to 'int' from 'std::vector<int>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
  return value.size() - 1;
         ~~~~~~~~~~~~~^~~
teams.cpp: In function 'int removefirst(int, int, int, int, int)':
teams.cpp:72: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: 23 / 23