oj.uz

Submission #785765

# Submission time Handle Problem Language Result Execution time Memory
785765 2023-07-17T14:46:32 Z ymm Teams (IOI15_teams) C++17
100 / 100
 1753 ms 150344 KB 
#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

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.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4424 KB Output is correct
2 Correct 6 ms 4424 KB Output is correct
3 Correct 5 ms 4424 KB Output is correct
4 Correct 5 ms 4392 KB Output is correct
5 Correct 5 ms 4424 KB Output is correct
6 Correct 5 ms 4424 KB Output is correct
7 Correct 8 ms 4396 KB Output is correct
8 Correct 5 ms 4424 KB Output is correct
9 Correct 8 ms 4424 KB Output is correct
10 Correct 5 ms 4396 KB Output is correct
11 Correct 5 ms 4424 KB Output is correct
12 Correct 22 ms 4424 KB Output is correct
13 Correct 11 ms 4424 KB Output is correct
14 Correct 6 ms 4424 KB Output is correct
15 Correct 5 ms 4424 KB Output is correct
16 Correct 5 ms 4424 KB Output is correct
17 Correct 7 ms 4424 KB Output is correct
18 Correct 6 ms 4400 KB Output is correct
19 Correct 5 ms 4424 KB Output is correct
20 Correct 6 ms 4392 KB Output is correct
21 Correct 5 ms 4424 KB Output is correct
22 Correct 5 ms 4392 KB Output is correct
23 Correct 5 ms 4424 KB Output is correct
24 Correct 5 ms 4424 KB Output is correct
25 Correct 5 ms 4476 KB Output is correct
26 Correct 5 ms 4424 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 29536 KB Output is correct
2 Correct 44 ms 29520 KB Output is correct
3 Correct 43 ms 29580 KB Output is correct
4 Correct 46 ms 30140 KB Output is correct
5 Correct 34 ms 29508 KB Output is correct
6 Correct 32 ms 29508 KB Output is correct
7 Correct 34 ms 29548 KB Output is correct
8 Correct 35 ms 29504 KB Output is correct
9 Correct 274 ms 29684 KB Output is correct
10 Correct 144 ms 29468 KB Output is correct
11 Correct 37 ms 29488 KB Output is correct
12 Correct 29 ms 29452 KB Output is correct
13 Correct 33 ms 29452 KB Output is correct
14 Correct 35 ms 29504 KB Output is correct
15 Correct 42 ms 29404 KB Output is correct
16 Correct 42 ms 29404 KB Output is correct
17 Correct 32 ms 28764 KB Output is correct
18 Correct 31 ms 28580 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 29764 KB Output is correct
2 Correct 49 ms 29712 KB Output is correct
3 Correct 143 ms 35804 KB Output is correct
4 Correct 46 ms 30144 KB Output is correct
5 Correct 625 ms 31432 KB Output is correct
6 Correct 353 ms 30544 KB Output is correct
7 Correct 621 ms 31424 KB Output is correct
8 Correct 389 ms 30868 KB Output is correct
9 Correct 269 ms 29684 KB Output is correct
10 Correct 677 ms 29704 KB Output is correct
11 Correct 562 ms 29636 KB Output is correct
12 Correct 659 ms 29848 KB Output is correct
13 Correct 362 ms 31244 KB Output is correct
14 Correct 147 ms 33500 KB Output is correct
15 Correct 167 ms 30956 KB Output is correct
16 Correct 166 ms 30988 KB Output is correct
17 Correct 228 ms 30164 KB Output is correct
18 Correct 312 ms 29888 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 282 ms 132260 KB Output is correct
2 Correct 260 ms 138556 KB Output is correct
3 Correct 718 ms 150344 KB Output is correct
4 Correct 260 ms 138156 KB Output is correct
5 Correct 1504 ms 138924 KB Output is correct
6 Correct 888 ms 137588 KB Output is correct
7 Correct 1501 ms 138932 KB Output is correct
8 Correct 964 ms 137832 KB Output is correct
9 Correct 1753 ms 136148 KB Output is correct
10 Correct 1333 ms 134528 KB Output is correct
11 Correct 1225 ms 135248 KB Output is correct
12 Correct 1399 ms 136284 KB Output is correct
13 Correct 884 ms 140776 KB Output is correct
14 Correct 752 ms 145552 KB Output is correct
15 Correct 846 ms 141068 KB Output is correct
16 Correct 791 ms 141196 KB Output is correct
17 Correct 1058 ms 138740 KB Output is correct
18 Correct 1152 ms 138996 KB Output is correct