# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
782769 |
2023-07-14T09:09:42 Z |
ymm |
Teams (IOI15_teams) |
C++17 |
|
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])
| ~~~~~~~~~~^~~~~~
# |
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 |
# |
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 |
# |
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 |
# |
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 |