# |
제출 시각 |
아이디 |
문제 |
언어 |
결과 |
실행 시간 |
메모리 |
785765 |
2023-07-17T14:46:32 Z |
ymm |
팀들 (IOI15_teams) |
C++17 |
|
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;
| ^
# |
결과 |
실행 시간 |
메모리 |
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 |
# |
결과 |
실행 시간 |
메모리 |
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 |
# |
결과 |
실행 시간 |
메모리 |
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 |
# |
결과 |
실행 시간 |
메모리 |
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 |