oj.uz

Submission #782769

# Submission time Handle Problem Language Result Execution time Memory
782769 2023-07-14T09:09:42 Z ymm Teams (IOI15_teams) C++17
100 / 100
 2741 ms 140804 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) {
		return get(nds[r1], l2, r2, 0, N)
		     - get(nds[l1], l2, r2, 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 can2(int m, int k[])
{
	priority_queue<int,vector<int>,greater<int>> pq;
	int p = 0;
	Loop (i,0,m) {
		while (p < vec.size() && vec[p].first <= k[i])
			pq.push(vec[p++].second);
		while (pq.size() && k[i] >= pq.top())
			pq.pop();
		if (pq.size() < k[i])
			return 0;
		if (i == m-1)
			return 1;
		Loop (_,0,k[i])
			pq.pop();
	}
	return -1;
}

const int S = 700;

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);
	if (m > S)
		return can2(m, k);
	vector<int> dp(m);
	LoopR (i,0,m) {
		dp[i] = cnt[k[i]] - k[i];
		Loop (j,i+1,m) {
			int x = seg::get(0, k[i]+1, k[i]+1, k[j]+1);
			x += dp[j] - k[i];
			dp[i] = min(dp[i], x);
		}
		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:63:15: warning: declaration of 'n' shadows a global declaration [-Wshadow]
   63 | void init(int n, int a[], int b[]) {
      |           ~~~~^
teams.cpp:10:5: note: shadowed declaration is here
   10 | int n;
      |     ^
teams.cpp: In function 'int can2(int, int*)':
teams.cpp:81:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |   while (p < vec.size() && vec[p].first <= k[i])
      |          ~~^~~~~~~~~~~~
teams.cpp:85:17: warning: comparison of integer expressions of different signedness: 'std::priority_queue<int, std::vector<int>, std::greater<int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   85 |   if (pq.size() < k[i])
      |       ~~~~~~~~~~^~~~~~

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4424 KB Output is correct
2 Correct 5 ms 4424 KB Output is correct
3 Correct 5 ms 4424 KB Output is correct
4 Correct 5 ms 4424 KB Output is correct
5 Correct 5 ms 4380 KB Output is correct
6 Correct 4 ms 4424 KB Output is correct
7 Correct 5 ms 4424 KB Output is correct
8 Correct 6 ms 4424 KB Output is correct
9 Correct 5 ms 4424 KB Output is correct
10 Correct 5 ms 4424 KB Output is correct
11 Correct 5 ms 4424 KB Output is correct
12 Correct 9 ms 4424 KB Output is correct
13 Correct 6 ms 4424 KB Output is correct
14 Correct 5 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 5 ms 4424 KB Output is correct
18 Correct 5 ms 4368 KB Output is correct
19 Correct 5 ms 4424 KB Output is correct
20 Correct 5 ms 4424 KB Output is correct
21 Correct 6 ms 4448 KB Output is correct
22 Correct 6 ms 4424 KB Output is correct
23 Correct 5 ms 4424 KB Output is correct
24 Correct 6 ms 4424 KB Output is correct
25 Correct 4 ms 4424 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 40 ms 29456 KB Output is correct
2 Correct 60 ms 29352 KB Output is correct
3 Correct 55 ms 29376 KB Output is correct
4 Correct 43 ms 29572 KB Output is correct
5 Correct 36 ms 29440 KB Output is correct
6 Correct 32 ms 29380 KB Output is correct
7 Correct 40 ms 29388 KB Output is correct
8 Correct 37 ms 29340 KB Output is correct
9 Correct 33 ms 30692 KB Output is correct
10 Correct 37 ms 30404 KB Output is correct
11 Correct 35 ms 30400 KB Output is correct
12 Correct 34 ms 29744 KB Output is correct
13 Correct 44 ms 29784 KB Output is correct
14 Correct 45 ms 29852 KB Output is correct
15 Correct 41 ms 29792 KB Output is correct
16 Correct 53 ms 29820 KB Output is correct
17 Correct 33 ms 29056 KB Output is correct
18 Correct 34 ms 28944 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 29860 KB Output is correct
2 Correct 55 ms 29912 KB Output is correct
3 Correct 61 ms 32976 KB Output is correct
4 Correct 51 ms 29912 KB Output is correct
5 Correct 2033 ms 29960 KB Output is correct
6 Correct 1110 ms 30276 KB Output is correct
7 Correct 1807 ms 30356 KB Output is correct
8 Correct 1236 ms 29908 KB Output is correct
9 Correct 30 ms 30720 KB Output is correct
10 Correct 42 ms 31276 KB Output is correct
11 Correct 129 ms 31392 KB Output is correct
12 Correct 1211 ms 30448 KB Output is correct
13 Correct 249 ms 30568 KB Output is correct
14 Correct 84 ms 31908 KB Output is correct
15 Correct 99 ms 30448 KB Output is correct
16 Correct 95 ms 30376 KB Output is correct
17 Correct 170 ms 29780 KB Output is correct
18 Correct 168 ms 29532 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 313 ms 132312 KB Output is correct
2 Correct 304 ms 131596 KB Output is correct
3 Correct 337 ms 136164 KB Output is correct
4 Correct 295 ms 132268 KB Output is correct
5 Correct 1367 ms 132372 KB Output is correct
6 Correct 2073 ms 132304 KB Output is correct
7 Correct 158 ms 132348 KB Output is correct
8 Correct 1646 ms 132044 KB Output is correct
9 Correct 145 ms 139112 KB Output is correct
10 Correct 294 ms 137448 KB Output is correct
11 Correct 1734 ms 138068 KB Output is correct
12 Correct 2741 ms 135868 KB Output is correct
13 Correct 723 ms 137736 KB Output is correct
14 Correct 451 ms 140804 KB Output is correct
15 Correct 388 ms 138508 KB Output is correct
16 Correct 360 ms 138532 KB Output is correct
17 Correct 435 ms 136512 KB Output is correct
18 Correct 480 ms 136944 KB Output is correct