Submission #782886

#	Time	Username	Problem	Language	Result	Execution time	Memory
782886		Sohsoh84	Teams (IOI15_teams)	C++17	0 / 100	978 ms	398960 KiB

teams

#include "teams.h"
#include <bits/stdc++.h>

using namespace std;

#define debug(x)		cerr << #x << ": " << x << endl;
#define all(x)			(x).begin(), (x).end()

typedef long long ll;

const int MAXN = 1e6 + 10;
const int INF = 1e9 + 10;

struct node {
	node *lc, *rc;
	int val;

	node() {}
	node(int val_): lc(nullptr), rc(nullptr), val(val_) {}
	node(node* lc_, node* rc_): lc(lc_), rc(rc_) {
		val = lc_ -> val + rc_ -> val;
	}
};

namespace segment {
	node* sg[MAXN];

	node* build(int l, int r) {
		if (l == r) return new node(0);
		int mid = (l + r) >> 1;
		return new node(build(l, mid), build(mid + 1, r));
	}

	node* update(int ind, int l, int r, node* v) {
		if (l == r) return new node((v -> val) + 1);
		int mid = (l + r) >> 1;
		if (ind <= mid) return new node(update(ind, l, mid, v -> lc), v -> rc);
		else return new node(v -> lc, update(ind, mid + 1, r, v -> rc));
	}

	int query(int ql, int qr, int l, int r, node* v) {
		if (ql > r || qr < l) return 0;
		if (ql <= l && qr >= r) return v -> val;

		int mid = (l + r) >> 1;
		return query(ql, qr, l, mid, v -> lc) +
			query(ql, qr, mid + 1, r, v -> rc);
	}
}

namespace segment2 {
	int sg[MAXN], lz[MAXN];
	
	inline void push(int v) {
		sg[v] += lz[v];
		if ((v << 1 | 1) < MAXN)
			lz[v << 1] += lz[v], lz[v << 1 | 1] += lz[v];

		lz[v] = 0;
	}

	void build(int l, int r, int v) {
		lz[v] = 0;
		if (l == r) sg[v] = -INF;
		else {
			int mid = (l + r) >> 1;
			build(l, mid, v << 1);
			build(mid + 1, r, v << 1 | 1);
			sg[v] = max(sg[v << 1], sg[v << 1 | 1]);
		}
	}

	void update(int ql, int qr, int val, int l, int r, int v) {
		push(v);
		if (ql > r || qr < l) return;
		if (ql <= l && qr >= r) {
			lz[v] += val;
			push(v);
			return;
		}

		int mid = (l + r) >> 1;
		update(ql, qr, val, l, mid, v << 1);
		update(ql, qr, val, mid + 1, r, v << 1 | 1);
		sg[v] = max(sg[v << 1], sg[v << 1 | 1]);
	}

	void point_set(int ind, int val, int l, int r, int v) {
		push(v);
		if (l == r) sg[v] = val;
		else {
			int mid = (l + r) >> 1;
			if (ind <= mid) point_set(ind, val, l, mid, v << 1), push(v << 1 | 1);
			else point_set(ind, val, mid + 1, r, v << 1 | 1), push(v << 1);

			sg[v] = max(sg[v << 1], sg[v << 1 | 1]);
		}
	}
}

int n;
vector<int> R[MAXN];

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

	segment::sg[0] = segment::build(1, n);
	for (int i = 1; i <= n; i++) {
		node* v = segment::sg[i - 1];
		for (int l : R[i])
			v = segment::update(l, 1, n, v);

		segment::sg[i] = v;
	}
}

inline int get(int l, int r) {
	if (r < l) return 0;
	return segment::query(l, n, 1, n, segment::sg[r]);
}

int can(int M, int K[]) {
	int m = M;

	vector<int> vec;
	vec.push_back(0);

	int s = 0;
	for (int i = 0; i < m; i++) {
		vec.push_back(K[i]);
		s += K[i];
		if (s > n) return 0;
	}

	sort(all(vec));
	segment2::build(1, m, 1);
	
	int ans = -INF;
	for (int i = 1; i <= m; i++) {
		if (i > 1) segment2::update(1, i - 1, vec[i] + get(vec[i - 1] + 1, vec[i] - 1), 1, m, 1);
		segment2::point_set(i, get(1, vec[i] - 1) + vec[i], 1, m, 1);

		ans = max(ans, segment2::sg[1] + get(vec[i] + 1, n));
	}

	if (n < ans) return 0;
	return 1;
}    

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