Submission #785765

#	Time	Username	Problem	Language	Result	Execution time	Memory
785765		ymm	Teams (IOI15_teams)	C++17	100 / 100	1753 ms	150344 KiB

teams

#include "teams.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef std::pair<int,int> pii;
typedef long long ll;
using namespace std;

const int N = 500010;
int n;

namespace seg {
	vector<int> nds;
	vector<int> ls;
	int nxt = 1;
	struct node {
		int cnt, l, r;
	} nd[(1<<27)/sizeof(node)];

	int get(int t, int l, int r, int b, int e) {
		if (l <= b && e <= r)
			return nd[t].cnt;
		int ans = 0;
		if (l < (b+e)/2 && nd[t].l)
			ans += get(nd[t].l, l, r, b, (b+e)/2);
		if ((b+e)/2 < r && nd[t].r)
			ans += get(nd[t].r, l, r, (b+e)/2, e);
		return ans;
	}
	int add(int t, int p, int b, int e) {
		int ans = nxt++;
		nd[ans].cnt = nd[t].cnt+1;
		nd[ans].l = nd[t].l;
		nd[ans].r = nd[t].r;
		if (e-b == 1)
			return ans;
		if (p < (b+e)/2)
			nd[ans].l = add(nd[t].l, p, b, (b+e)/2);
		else
			nd[ans].r = add(nd[t].r, p, (b+e)/2, e);
		return ans;
	}

	void mk_seg(const vector<pii> &vec) {
		nds = {0};
		int p = 0;
		Loop (i,1,N+1) {
			int t = nds.back();
			while (p < vec.size() && vec[p].first < i)
				t = add(t, vec[p++].second, 0, N);
			nds.push_back(t);
		}
	}
	int get(int l1, int r1, int l2, int r2) {
		if (l2 == r2)
			return 0;
		if (l2 < r2)
			return get(nds[r1], l2, r2, 0, N)
			     - get(nds[l1], l2, r2, 0, N);
		else
			return get(nds[l1], r2, l2, 0, N)
			     - get(nds[r1], r2, l2, 0, N);
	}
}

namespace lichao {
	struct fn {
		int val;
		int p;
	};
	int eval(fn f, int x) {
		return seg::get(0, x+1, x+1, f.p+1) + f.val;
	}
	struct node {
		fn f;
		int l, r;
	} nds[(1<<27)/sizeof(node)];
	int nxt = 1;

	int get(int t, int p, int b, int e) {
		if (!t)
			return 1e9;
		int ans = eval(nds[t].f, p);
		if (e-b == 1)
			return ans;
		if (p < (b+e)/2)
			ans = min(ans, get(nds[t].l, p, b, (b+e)/2));
		else
			ans = min(ans, get(nds[t].r, p, (b+e)/2, e));
		return ans;
	}
	int get(int t, int p) { return get(t, p, 0, N); }
	void up(int &t, fn f, int b, int e) {
		if (!t) {
			t = nxt++;
			nds[t].f = f;
			return;
		}
		int m = (b+e)/2;
		bool b1 = eval(nds[t].f, b) > eval(f, b);
		bool b2 = eval(nds[t].f, m) > eval(f, m);
		if (b2)
			swap(nds[t].f, f);
		if (e-b == 1)
			return;
		if (b1 != b2)
			up(nds[t].l, f, b, m);
		else
			up(nds[t].r, f, m, e);
	}
	void up(int &t, fn f) { return up(t, f, 0, N); }
}

int cnt[N];
vector<pii> vec;

void init(int n, int a[], int b[]) {
	Loop (i,0,n) {
		cnt[a[i]]++;
		cnt[b[i]+1]--;
		vec.push_back({a[i], b[i]+1});
	}
	Loop (i,1,N)
		cnt[i] += cnt[i-1];
	::n = n;
	sort(vec.begin(), vec.end());
	seg::mk_seg(vec);
}

int can(int m, int k[]) {
	ll sum = 0;
	Loop (i,0,m)
		sum += k[i];
	if (sum > n)
		return 0;
	sort(k, k+m);
	int li = 0;
	lichao::fn tmp;
	lichao::up(li, tmp = { .val = 0, .p = n+1 });
	vector<int> dp(m);
	LoopR (i,0,m) {
		dp[i] = lichao::get(li, k[i]) - k[i];
		lichao::up(li, { .val = dp[i], .p = k[i] });
		if (dp[i] < 0)
			return 0;
	}
	return 1;
}

Compilation message (stderr)

teams.cpp: In function 'void seg::mk_seg(const std::vector<std::pair<int, int> >&)':
teams.cpp:49:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |    while (p < vec.size() && vec[p].first < i)
      |           ~~^~~~~~~~~~~~
teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:117:15: warning: declaration of 'n' shadows a global declaration [-Wshadow]
  117 | void init(int n, int a[], int b[]) {
      |           ~~~~^
teams.cpp:10:5: note: shadowed declaration is here
   10 | int n;
      |     ^

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