제출 #1212963

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1212963		Lemser	Teams (IOI15_teams)	C++20	77 / 100	2756 ms	391992 KiB

teams

#include "teams.h"
#include <bits/stdc++.h>
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 lnd[MAX], rnd[MAX], snd[MAX], leftnd[MAX], rightnd[MAX];
int n, rts[N], act_idx;
vector<int> ps[N];

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

int update (int id, int i, int v){
	if (rnd[id]<i || lnd[id]>i) return id;
	auto t = new_node(lnd[id], rnd[id]);
	if (lnd[id] == rnd[id]) snd[t] = snd[id]+v;
	else{
		leftnd[t] = update(leftnd[id], i, v);
		rightnd[t] = update(rightnd[id], i,v);
		snd[t] = snd[leftnd[t]] + snd[rightnd[t]];
	}
	return t;
}

int query (int id, int i, int j){
	if (lnd[id]>j || rnd[id]<i) return 0;
	if (lnd[id]>=i && rnd[id]<=j) return snd[id];
	return query(leftnd[id], i, j) + query(rightnd[id], 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[]) {
	n = N;
	rts[0] = new_node(0, n);
	constr(rts[0], 0, n);
	fo (i, n) ps[a[i]].pb(b[i]);
	fore  (x, 1, n+1) {
		rts[x] = update(rts[x-1], 0, 0);
		for (int y: ps[x]) {
			rts[x] = update(rts[x], y, +1);
		}
	}
}

int rectangles (int x1, int x2, int y1, int y2) {
	int ans = query(rts[x2], y1, y2);
	if (x1 > 0) ans -= query(rts[x1-1], y1, y2);
	return ans;
}

int isec (int k1, int k2) {
	if (k1 == k2) return 0ll;
	return rectangles (k1+1, k2, k2, n);
}

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;
		multiset<int> st;
		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;
	}
	vector<int> dp(m, 0);
	fo (i, m) {
		// no elegir a nadie
		dp[i] = rectangles(0, k[i], k[i], n) - k[i];
		fo (j, i) {
			dp[i] = min(dp[i], dp[j] + isec(k[j], k[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