#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e5 + 3;
vector <int> merge(vector <int> &a, vector <int> &b)
{
vector <int> ans;
int pos_a = 0, pos_b = 0, sz_a = (int)a.size(), sz_b = (int)b.size();
while (pos_a < sz_a && pos_b < sz_b)
{
if (a[pos_a] < b[pos_b])
{
ans.push_back(a[pos_a]);
pos_a++;
}
else
{
ans.push_back(b[pos_b]);
pos_b++;
}
}
while (pos_a < sz_a)
{
ans.push_back(a[pos_a]);
pos_a++;
}
while (pos_b < sz_b)
{
ans.push_back(b[pos_b]);
pos_b++;
}
return ans;
}
int n;
vector <int> ve[maxn];
vector <int> tr[maxn * 4];
void build(int v, int l, int r)
{
if (l == r)
{
tr[v] = ve[l];
sort (tr[v].begin(), tr[v].end());
return;
}
int mid = (l + r) / 2;
build(v * 2, l, mid);
build(v * 2 + 1, mid + 1, r);
tr[v] = merge(tr[v * 2], tr[v * 2 + 1]);
}
vector <int> temp;
void get(int v, int l, int r, int ll, int rr)
{
if (l > rr || r < ll)
return;
if (l >= ll && r <= rr)
{
temp.push_back(v);
return;
}
int mid = (l + r) / 2;
get(v * 2, l, mid, ll, rr);
get(v * 2 + 1, mid + 1, r, ll, rr);
}
void init(int _n, int l[], int r[])
{
n = _n;
for (int i = 1; i <= n; i++)
ve[l[i-1]].push_back(r[i-1]);
build(1, 1, n);
}
int cnt[maxn];
bool can(int m, int k[])
{
long long sum = 0;
for (int i = 0; i < m; i++)
sum += k[i];
if (sum > n)
return false;
map <int, int> mp;
for (int i = 0; i < m; i++)
mp[k[i]]++;
for (int i = 0; i < (int)mp.size(); i++)
cnt[i] = 0;
int idx = 0;
for (auto it = mp.begin(); it != mp.end(); it++)
{
int prv = 1;
if (it != mp.begin())
prv = prev(it)->first + 1;
temp.clear();
get(1, 1, n, prv, it->first);
int curr_idx = idx;
for (auto it1 = it; it1 != mp.end(); it1++)
{
int nxt = n;
if (it1 != prev(mp.end()))
nxt = next(it1)->first - 1;
for (auto i: temp)
{
auto it2 = lower_bound(tr[i].begin(), tr[i].end(), it1->first);
auto it3 = upper_bound(tr[i].begin(), tr[i].end(), nxt);
cnt[curr_idx] += it3 - it2;
}
curr_idx++;
}
int to_sub = it->second * it->first;
for (int i = idx; i < (int)mp.size() && to_sub; i++)
{
int curr_to_sub = min(cnt[i], to_sub);
to_sub -= curr_to_sub;
cnt[i] -= curr_to_sub;
}
if (to_sub)
return false;
idx++;
}
return true;
}
Compilation message
teams.cpp: In function 'bool can(int, int*)':
teams.cpp:124:29: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
124 | cnt[curr_idx] += it3 - it2;
| ^~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
40 ms |
59000 KB |
Output is correct |
2 |
Correct |
40 ms |
59000 KB |
Output is correct |
3 |
Correct |
40 ms |
59000 KB |
Output is correct |
4 |
Correct |
41 ms |
59132 KB |
Output is correct |
5 |
Correct |
40 ms |
59128 KB |
Output is correct |
6 |
Correct |
41 ms |
59128 KB |
Output is correct |
7 |
Correct |
41 ms |
59008 KB |
Output is correct |
8 |
Correct |
41 ms |
59008 KB |
Output is correct |
9 |
Correct |
40 ms |
59000 KB |
Output is correct |
10 |
Correct |
41 ms |
59000 KB |
Output is correct |
11 |
Correct |
40 ms |
59000 KB |
Output is correct |
12 |
Correct |
41 ms |
59000 KB |
Output is correct |
13 |
Correct |
40 ms |
59000 KB |
Output is correct |
14 |
Correct |
40 ms |
59008 KB |
Output is correct |
15 |
Correct |
40 ms |
59000 KB |
Output is correct |
16 |
Correct |
40 ms |
59000 KB |
Output is correct |
17 |
Correct |
41 ms |
59000 KB |
Output is correct |
18 |
Correct |
40 ms |
59000 KB |
Output is correct |
19 |
Correct |
40 ms |
59000 KB |
Output is correct |
20 |
Correct |
40 ms |
59008 KB |
Output is correct |
21 |
Correct |
40 ms |
59000 KB |
Output is correct |
22 |
Correct |
41 ms |
59000 KB |
Output is correct |
23 |
Correct |
40 ms |
59000 KB |
Output is correct |
24 |
Correct |
40 ms |
59000 KB |
Output is correct |
25 |
Correct |
40 ms |
59008 KB |
Output is correct |
26 |
Correct |
40 ms |
59000 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
117 ms |
75120 KB |
Output is correct |
2 |
Correct |
115 ms |
74992 KB |
Output is correct |
3 |
Correct |
114 ms |
74992 KB |
Output is correct |
4 |
Correct |
115 ms |
75252 KB |
Output is correct |
5 |
Correct |
65 ms |
69360 KB |
Output is correct |
6 |
Correct |
62 ms |
69488 KB |
Output is correct |
7 |
Correct |
61 ms |
69492 KB |
Output is correct |
8 |
Correct |
61 ms |
69360 KB |
Output is correct |
9 |
Correct |
64 ms |
68464 KB |
Output is correct |
10 |
Correct |
62 ms |
68212 KB |
Output is correct |
11 |
Correct |
62 ms |
68208 KB |
Output is correct |
12 |
Correct |
65 ms |
68544 KB |
Output is correct |
13 |
Correct |
73 ms |
70296 KB |
Output is correct |
14 |
Correct |
87 ms |
71592 KB |
Output is correct |
15 |
Correct |
107 ms |
74612 KB |
Output is correct |
16 |
Correct |
107 ms |
74480 KB |
Output is correct |
17 |
Correct |
64 ms |
69588 KB |
Output is correct |
18 |
Correct |
64 ms |
69624 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
144 ms |
75472 KB |
Output is correct |
2 |
Correct |
147 ms |
75376 KB |
Output is correct |
3 |
Correct |
285 ms |
78704 KB |
Output is correct |
4 |
Correct |
119 ms |
75248 KB |
Output is correct |
5 |
Correct |
807 ms |
70128 KB |
Output is correct |
6 |
Correct |
802 ms |
69868 KB |
Output is correct |
7 |
Correct |
89 ms |
69744 KB |
Output is correct |
8 |
Correct |
613 ms |
69744 KB |
Output is correct |
9 |
Correct |
62 ms |
68592 KB |
Output is correct |
10 |
Correct |
63 ms |
68336 KB |
Output is correct |
11 |
Correct |
77 ms |
68720 KB |
Output is correct |
12 |
Correct |
694 ms |
69012 KB |
Output is correct |
13 |
Correct |
674 ms |
71068 KB |
Output is correct |
14 |
Correct |
367 ms |
75968 KB |
Output is correct |
15 |
Correct |
182 ms |
74992 KB |
Output is correct |
16 |
Correct |
183 ms |
74992 KB |
Output is correct |
17 |
Correct |
138 ms |
70012 KB |
Output is correct |
18 |
Correct |
125 ms |
69916 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
577 ms |
143592 KB |
Output is correct |
2 |
Correct |
596 ms |
143456 KB |
Output is correct |
3 |
Correct |
1008 ms |
149096 KB |
Output is correct |
4 |
Correct |
514 ms |
143224 KB |
Output is correct |
5 |
Correct |
3886 ms |
114408 KB |
Output is correct |
6 |
Correct |
3783 ms |
114396 KB |
Output is correct |
7 |
Correct |
208 ms |
114384 KB |
Output is correct |
8 |
Correct |
3019 ms |
114492 KB |
Output is correct |
9 |
Correct |
165 ms |
109864 KB |
Output is correct |
10 |
Correct |
166 ms |
107964 KB |
Output is correct |
11 |
Correct |
595 ms |
108620 KB |
Output is correct |
12 |
Correct |
2662 ms |
110260 KB |
Output is correct |
13 |
Correct |
2245 ms |
119620 KB |
Output is correct |
14 |
Correct |
1343 ms |
143016 KB |
Output is correct |
15 |
Correct |
619 ms |
137960 KB |
Output is correct |
16 |
Correct |
623 ms |
137964 KB |
Output is correct |
17 |
Correct |
329 ms |
114844 KB |
Output is correct |
18 |
Correct |
336 ms |
114648 KB |
Output is correct |