# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
282647 |
2020-08-24T16:46:16 Z |
SamAnd |
Teams (IOI15_teams) |
C++17 |
|
997 ms |
524292 KB |
#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define fi first
#define se second
typedef long long ll;
const int N = 500005, L = 20;
struct ban
{
int l, r;
};
bool operator<(const ban& a, const ban& b)
{
return a.l < b.l;
}
int n;
ban a[N];
vector<int> v[N];
int root[N];
int z;
int t[N * L];
int ul[N * L], ur[N * L];
int ubd(int tl, int tr, int x, int pos)
{
int ypos = ++z;
ul[ypos] = ul[pos];
ur[ypos] = ur[pos];
t[ypos] = t[pos];
t[ypos]++;
if (tl == tr)
return ypos;
int m = (tl + tr) / 2;
if (x <= m)
{
ul[ypos] = ubd(tl, m, x, ul[pos]);
}
else
{
ur[ypos] = ubd(m + 1, tr, x, ur[pos]);
}
return ypos;
}
int qry(int tl, int tr, int l, int r, int pos)
{
if (pos == 0)
return 0;
if (l > r)
return 0;
if (tl == l && tr == r)
return t[pos];
int m = (tl + tr) / 2;
return (qry(tl, m, l, min(m, r), ul[pos]) +
qry(m + 1, tr, max(m + 1, l), r, ur[pos]));
}
const int M = 300;
int pp[N];
int p[M][N];
int qryy(int l1, int r1, int l2, int r2)
{
if (r1 < M)
return p[r1][r2] - p[r1][l2 - 1];
return qry(1, n, l2, r2, root[r1]) - qry(1, n, l2, r2, root[l1 - 1]);
}
void init(int N_, int A[], int B[])
{
n = N_;
for (int i = 0; i < n; ++i)
{
a[i].l = A[i];
a[i].r = B[i];
v[a[i].l].push_back(a[i].r);
}
sort(a, a + n);
for (int i = 1; i <= n; ++i)
{
root[i] = root[i - 1];
for (int j = 0; j < sz(v[i]); ++j)
root[i] = ubd(1, n, v[i][j], root[i]);
}
for (int i = 1; i < M; ++i)
{
for (int j = 0; j < sz(v[i]); ++j)
pp[v[i][j]]++;
for (int j = 1; j <= n; ++j)
p[i][j] = p[i][j - 1] + pp[j];
}
}
int m;
int b[N];
int can(int M_, int K[])
{
m = M_;
for (int i = 0; i < m; ++i)
b[i] = K[i];
sort(b, b + m);
ll sum = 0;
for (int i = 0; i < m; ++i)
sum += b[i];
if (sum > n)
return 0;
/*multiset<int> s;
int j = 0;
for (int i = 0; i < m; ++i)
{
while (j < n && a[j].l <= b[i])
s.insert(a[j++].r);
while (!s.empty() && *s.begin() < b[i])
s.erase(s.begin());
if (sz(s) < b[i])
return 0;
for (int j = 0; j < b[i]; ++j)
s.erase(s.begin());
}*/
vector<pair<int, int> > v;
v.push_back(m_p(b[0], b[0]));
for (int i = 1; i < m; ++i)
{
if (b[i] == v.back().fi)
v.back().se += b[i];
else
v.push_back(m_p(b[i], b[i]));
}
vector<int> h;
h.assign(sz(v), 0);
for (int i = 0; i < sz(v); ++i)
{
for (int j = i; j < sz(v); ++j)
{
int nx;
if (j == sz(v) - 1)
nx = n + 1;
else
nx = v[j + 1].fi;
int q = qryy(1, v[i].fi, v[j].fi, nx - 1) - h[j];
if (q < v[i].se)
{
h[j] += q;
v[i].se -= q;
}
else
{
h[j] += v[i].se;
v[i].se = 0;
break;
}
}
if (v[i].se)
return 0;
}
return 1;
}
Compilation message
teams.cpp: In function 'int can(int, int*)':
teams.cpp:133:29: warning: declaration of 'v' shadows a global declaration [-Wshadow]
133 | vector<pair<int, int> > v;
| ^
teams.cpp:24:13: note: shadowed declaration is here
24 | vector<int> v[N];
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
14464 KB |
Output is correct |
2 |
Correct |
9 ms |
14464 KB |
Output is correct |
3 |
Correct |
10 ms |
14592 KB |
Output is correct |
4 |
Correct |
10 ms |
14592 KB |
Output is correct |
5 |
Correct |
10 ms |
14592 KB |
Output is correct |
6 |
Correct |
10 ms |
14592 KB |
Output is correct |
7 |
Correct |
10 ms |
14592 KB |
Output is correct |
8 |
Correct |
10 ms |
14592 KB |
Output is correct |
9 |
Correct |
10 ms |
14592 KB |
Output is correct |
10 |
Correct |
10 ms |
14592 KB |
Output is correct |
11 |
Correct |
10 ms |
14592 KB |
Output is correct |
12 |
Correct |
10 ms |
14592 KB |
Output is correct |
13 |
Correct |
10 ms |
14592 KB |
Output is correct |
14 |
Correct |
11 ms |
14592 KB |
Output is correct |
15 |
Correct |
10 ms |
14720 KB |
Output is correct |
16 |
Correct |
10 ms |
14592 KB |
Output is correct |
17 |
Correct |
9 ms |
14464 KB |
Output is correct |
18 |
Correct |
10 ms |
14464 KB |
Output is correct |
19 |
Correct |
10 ms |
14464 KB |
Output is correct |
20 |
Correct |
9 ms |
14464 KB |
Output is correct |
21 |
Correct |
10 ms |
14464 KB |
Output is correct |
22 |
Correct |
9 ms |
14464 KB |
Output is correct |
23 |
Correct |
10 ms |
14464 KB |
Output is correct |
24 |
Correct |
10 ms |
14464 KB |
Output is correct |
25 |
Correct |
9 ms |
14464 KB |
Output is correct |
26 |
Correct |
9 ms |
14464 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
229 ms |
156168 KB |
Output is correct |
2 |
Correct |
228 ms |
156244 KB |
Output is correct |
3 |
Correct |
251 ms |
156152 KB |
Output is correct |
4 |
Correct |
243 ms |
157176 KB |
Output is correct |
5 |
Correct |
201 ms |
154616 KB |
Output is correct |
6 |
Correct |
190 ms |
154744 KB |
Output is correct |
7 |
Correct |
187 ms |
154616 KB |
Output is correct |
8 |
Correct |
190 ms |
154616 KB |
Output is correct |
9 |
Correct |
183 ms |
153840 KB |
Output is correct |
10 |
Correct |
181 ms |
153712 KB |
Output is correct |
11 |
Correct |
181 ms |
154996 KB |
Output is correct |
12 |
Correct |
187 ms |
153720 KB |
Output is correct |
13 |
Correct |
197 ms |
154996 KB |
Output is correct |
14 |
Correct |
199 ms |
154824 KB |
Output is correct |
15 |
Correct |
220 ms |
155640 KB |
Output is correct |
16 |
Correct |
222 ms |
155768 KB |
Output is correct |
17 |
Correct |
189 ms |
155004 KB |
Output is correct |
18 |
Correct |
188 ms |
155000 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
243 ms |
156540 KB |
Output is correct |
2 |
Correct |
247 ms |
156592 KB |
Output is correct |
3 |
Correct |
375 ms |
159480 KB |
Output is correct |
4 |
Correct |
232 ms |
156920 KB |
Output is correct |
5 |
Correct |
203 ms |
155000 KB |
Output is correct |
6 |
Correct |
204 ms |
154964 KB |
Output is correct |
7 |
Correct |
194 ms |
155000 KB |
Output is correct |
8 |
Correct |
201 ms |
155000 KB |
Output is correct |
9 |
Correct |
186 ms |
153840 KB |
Output is correct |
10 |
Correct |
186 ms |
154140 KB |
Output is correct |
11 |
Correct |
189 ms |
155120 KB |
Output is correct |
12 |
Correct |
825 ms |
153968 KB |
Output is correct |
13 |
Correct |
498 ms |
155508 KB |
Output is correct |
14 |
Correct |
379 ms |
157692 KB |
Output is correct |
15 |
Correct |
234 ms |
156152 KB |
Output is correct |
16 |
Correct |
232 ms |
156280 KB |
Output is correct |
17 |
Correct |
204 ms |
155232 KB |
Output is correct |
18 |
Correct |
206 ms |
155252 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
997 ms |
524292 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |