Submission #1212982

#	Time	Username	Problem	Language	Result	Execution time	Memory
1212982		Lemser	Teams (IOI15_teams)	C++20	77 / 100	4103 ms	183100 KiB

teams

#include "teams.h"
#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#pragma GCC target("popcnt")
using namespace std;
 
using ll = long long;
using ull = unsigned long long;
using lld = long double;
using ii = pair<int,int>;
using pll = pair<ll, ll>;
 
using vi = vector<int>;
using vll = vector<ll>;
using vii = vector<ii>;
using vpll = vector<pll>;
using vlld = vector<lld>;
 
#define all(x) x.begin(),x.end()
#define lsb(x) x&(-x)
#define gcd(a,b) __gcd(a,b)
#define sz(x) (int)x.size()
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define fls cout.flush()
 
#define fore(i, l, r) for (auto i = l; i < r; i++)
#define fo(i, n) fore (i, 0, n)
#define forex(i, r, l) for (auto i = r-1; i >= l; i--)
#define ffo(i, n) forex (i, n, 0)
 
bool cmin(ll &a, ll b) { if (b < a) { a=b; return 1; } return 0; }
bool cmax(ll &a, ll b) { if (b > a) { a=b; return 1; } return 0; }

const int N = 5e5 + 7;
const int MAX = 15000000;

int snd[MAX], leftnd[MAX], rightnd[MAX];
int n, rts[N], act_idx, dp[1005];
vector<int> ps[N], ot[N];

int new_node (int l, int r) {
	int x = act_idx++;
	snd[x] = 0;
	leftnd[x] = -1;
	rightnd[x] = -1;
	return x;
}

int update (int id, int l, int r, int i, int v){
	if (r<i || l>i) return id;
	auto t = new_node(l, r);
	int m = (l+r)/2;
	if (l == r) snd[t] = snd[id]+v;
	else{
		leftnd[t] = update(leftnd[id], l, m, i, v);
		rightnd[t] = update(rightnd[id], m+1, r, i,v);
		snd[t] = snd[leftnd[t]] + snd[rightnd[t]];
	}
	return t;
}

int query (int id, int l, int r, int i, int j){
	if (l>j || r<i) return 0;
	if (l>=i && r<=j) return snd[id];
	int m = (l+r)/2;
	return query(leftnd[id], l, m, i, j) + query(rightnd[id], m+1, r, i,j);
}

void constr (int id, int l, int r) {
    if (l == r) return;
    int m = (l+r)/2;
    leftnd[id] = new_node(l, m);
    rightnd[id] = new_node(m+1, r);
    constr(leftnd[id], l, m);
    constr(rightnd[id], m+1, r);
}

void init(int N, int a[], int b[]) {
	act_idx = 0;
	n = N;
	rts[n+1] = new_node(1, n);
	constr(rts[n+1], 1, n);
	fo (i, n) ps[a[i]].pb(b[i]);
	fo (i, n) ot[b[i]].pb(a[i]);
	forex  (x, n+1, 1) {
		rts[x] = update(rts[x+1], 1, n, 0, 0);
		for (int y: ot[x]) {
			rts[x] = update(rts[x], 1, n, y, +1);
		}
	}
}

multiset<int> st;

int can(int m, int k[]) {
	sort(k, k+m);
	if (accumulate(k, k+m, 0ll) > n) return 0;
	if (m >= 500) {
		int r = 1;
		st.clear();
		fo (i, m) {
			while (r <= k[i]) {
				for (int b: ps[r])
					st.insert(b);
				r++;
			}
			while (st.size() && *st.begin() < k[i]) st.erase(st.find(*st.begin()));
			while (st.size() && k[i]--) st.erase(st.find(*st.begin()));
			if (k[i] > 0) return 0;
		}
		return 1;
	}
	fo (i, m) {
		// no elegir a nadie
		int r = query(rts[k[i]], 1, n, 1, k[i]);
		dp[i] = r;
		fo (j, i) {
			if (k[i] != k[j]) r = query(rts[k[i]], 1, n, k[j]+1, k[i]);
			else r = 0;
			dp[i] = min(dp[i], dp[j] + r);
		}
		dp[i] -= k[i];
		if (dp[i] < 0) return 0;
	}
	return 1;
}

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