Submission #805269

#	Time	Username	Problem	Language	Result	Execution time	Memory
805269		NothingXD	Teams (IOI15_teams)	C++17	100 / 100	2787 ms	163336 KiB

teams

#include "teams.h"

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef complex<ld> point;

void debug_out(){cerr << endl;}

template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
	cerr << H << ' ';
	debug_out(T...);
}

#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 5e5 + 10;
const int lg = 22;
const int inf = 1e9;

int n, a[maxn], b[maxn], seg[maxn*lg], lc[maxn*lg], rc[maxn*lg], root[maxn], vercnt = 1;
vector<int> val[maxn];

void build(int v, int l, int r){
	if (l + 1 == r){
		return;
	}
	lc[v] = vercnt++;
	rc[v] = vercnt++;
	int mid = (l + r) >> 1;
	build(lc[v], l, mid);
	build(rc[v], mid, r);
}

void add(int v, int newv, int l, int r, int idx){
	if (l + 1 == r){
		seg[newv] = seg[v] + 1;
		return;
	}
	int mid = (l + r) >> 1;
	if (idx < mid){
		lc[newv] = vercnt++;
		rc[newv] = rc[v];
		add(lc[v], lc[newv], l, mid, idx);
	}
	else{
		lc[newv] = lc[v];
		rc[newv] = vercnt++;
		add(rc[v], rc[newv], mid, r, idx);
	}
	seg[newv] = seg[lc[newv]] + seg[rc[newv]];
}

int get(int v, int l, int r, int ql, int qr){
	if (qr <= l || r <= ql) return 0;
	if (ql <= l && r <= qr) return seg[v];
	int mid = (l + r) >> 1;
	return get(lc[v], l, mid, ql, qr)
		+ get(rc[v], mid, r, ql, qr);
}

void init(int N, int A[], int B[]){
	n = N;
	for (int i = 0; i < n; i++){
		val[A[i]].push_back(B[i]);
	}
	root[0] = 0;
	build(0, 1, n+1);
	for (int i = 1; i <= n; i++){
		root[i] = root[i-1];
		for (auto x: val[i]){
			int tmp = vercnt++;
			add(root[i], tmp, 1, n+1, x);
			root[i] = tmp;
		}
	}
}

int k[maxn], dp[maxn], func[maxn << 2];

int f(int idx, int x){
//	debug(idx, x, dp[idx], get(root[x], 1, n+1, x, n+1), get(root[k[idx]], 1, n+1, x, n+1));
	if (k[idx] > x) return -inf - idx;
	return dp[idx] + get(root[x], 1, n+1, x, n+1) - get(root[k[idx]], 1, n+1, x, n+1);
}

vector<int> del;
bool mark[maxn << 2];
void addfunc(int v, int l, int r, int idx){
//	debug(v, l, r, idx);
	if (!mark[v]){
		mark[v] = true;
		del.push_back(v);
	}
	int mid = (l + r) >> 1;
	bool L = f(idx, l) < f(func[v], l);
	bool M = f(idx, mid) < f(func[v], mid);
	if (M){
		swap(func[v], idx);
	}
//	debug(func[v]);
	if (l + 1 == r) return;
	if (L != M){
		addfunc(v << 1, l, mid, idx);
	}
	else{
		addfunc(v << 1 | 1, mid, r, idx);
	}
}

int getmin(int v, int l, int r, int idx){
	if (l + 1 == r) return f(func[v], idx);
	int mid = (l + r) >> 1;
	if (idx < mid) return min(f(func[v], idx), getmin(v << 1, l, mid, idx));
	else return min(f(func[v], idx), getmin(v << 1 | 1, mid, r, idx));
}

int can(int M, int K[]) {
	for (auto x: del){
		func[x] = 0;
		mark[x] = false;
	}
	del.clear();
	sort(K, K+M);
	for (int i = 1; i <= M; i++){
		k[i] = K[i-1];
	}
	dp[0] = 0;
	for (int i = 1; i <= M; i++){
		dp[i] = getmin(1, 1, n+1, k[i]) - k[i];
//		debug(i, dp[i]);
		if (dp[i] < 0) return 0;
		addfunc(1, 1, n+1, i);
	}
	return 1;
}

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