# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
282576 |
2020-08-24T15:12:43 Z |
SamAnd |
Teams (IOI15_teams) |
C++17 |
|
4000 ms |
156556 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 (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]));
}
int qryy(int l1, int r1, int l2, int r2)
{
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]);
}
}
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:117:29: warning: declaration of 'v' shadows a global declaration [-Wshadow]
117 | 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 |
8 ms |
12032 KB |
Output is correct |
2 |
Correct |
8 ms |
12032 KB |
Output is correct |
3 |
Correct |
8 ms |
12160 KB |
Output is correct |
4 |
Correct |
8 ms |
12160 KB |
Output is correct |
5 |
Correct |
9 ms |
12160 KB |
Output is correct |
6 |
Correct |
9 ms |
12180 KB |
Output is correct |
7 |
Correct |
9 ms |
12160 KB |
Output is correct |
8 |
Correct |
8 ms |
12160 KB |
Output is correct |
9 |
Correct |
8 ms |
12160 KB |
Output is correct |
10 |
Correct |
9 ms |
12160 KB |
Output is correct |
11 |
Correct |
8 ms |
12160 KB |
Output is correct |
12 |
Correct |
8 ms |
12160 KB |
Output is correct |
13 |
Correct |
8 ms |
12160 KB |
Output is correct |
14 |
Correct |
9 ms |
12160 KB |
Output is correct |
15 |
Correct |
8 ms |
12160 KB |
Output is correct |
16 |
Correct |
8 ms |
12160 KB |
Output is correct |
17 |
Correct |
8 ms |
12160 KB |
Output is correct |
18 |
Correct |
8 ms |
12160 KB |
Output is correct |
19 |
Correct |
8 ms |
12160 KB |
Output is correct |
20 |
Correct |
8 ms |
12160 KB |
Output is correct |
21 |
Correct |
7 ms |
12160 KB |
Output is correct |
22 |
Correct |
9 ms |
12160 KB |
Output is correct |
23 |
Correct |
8 ms |
12160 KB |
Output is correct |
24 |
Correct |
8 ms |
12160 KB |
Output is correct |
25 |
Correct |
8 ms |
12160 KB |
Output is correct |
26 |
Correct |
9 ms |
12160 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
88 ms |
36600 KB |
Output is correct |
2 |
Correct |
89 ms |
36708 KB |
Output is correct |
3 |
Correct |
90 ms |
36580 KB |
Output is correct |
4 |
Correct |
86 ms |
37384 KB |
Output is correct |
5 |
Correct |
44 ms |
35448 KB |
Output is correct |
6 |
Correct |
45 ms |
35448 KB |
Output is correct |
7 |
Correct |
43 ms |
35448 KB |
Output is correct |
8 |
Correct |
44 ms |
35432 KB |
Output is correct |
9 |
Correct |
38 ms |
34672 KB |
Output is correct |
10 |
Correct |
38 ms |
34672 KB |
Output is correct |
11 |
Correct |
49 ms |
35696 KB |
Output is correct |
12 |
Correct |
42 ms |
34552 KB |
Output is correct |
13 |
Correct |
50 ms |
35828 KB |
Output is correct |
14 |
Correct |
60 ms |
35312 KB |
Output is correct |
15 |
Correct |
93 ms |
36472 KB |
Output is correct |
16 |
Correct |
75 ms |
36472 KB |
Output is correct |
17 |
Correct |
44 ms |
35832 KB |
Output is correct |
18 |
Correct |
46 ms |
35960 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
172 ms |
37112 KB |
Output is correct |
2 |
Correct |
193 ms |
37020 KB |
Output is correct |
3 |
Correct |
224 ms |
40444 KB |
Output is correct |
4 |
Correct |
91 ms |
38776 KB |
Output is correct |
5 |
Correct |
85 ms |
37032 KB |
Output is correct |
6 |
Correct |
85 ms |
37032 KB |
Output is correct |
7 |
Correct |
92 ms |
36984 KB |
Output is correct |
8 |
Correct |
99 ms |
37112 KB |
Output is correct |
9 |
Correct |
39 ms |
35568 KB |
Output is correct |
10 |
Correct |
41 ms |
35568 KB |
Output is correct |
11 |
Correct |
109 ms |
36848 KB |
Output is correct |
12 |
Correct |
2400 ms |
36052 KB |
Output is correct |
13 |
Correct |
511 ms |
37876 KB |
Output is correct |
14 |
Correct |
279 ms |
40184 KB |
Output is correct |
15 |
Correct |
133 ms |
38520 KB |
Output is correct |
16 |
Correct |
128 ms |
38520 KB |
Output is correct |
17 |
Correct |
91 ms |
37624 KB |
Output is correct |
18 |
Correct |
84 ms |
37492 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
856 ms |
148832 KB |
Output is correct |
2 |
Correct |
803 ms |
148856 KB |
Output is correct |
3 |
Correct |
977 ms |
156536 KB |
Output is correct |
4 |
Correct |
596 ms |
156556 KB |
Output is correct |
5 |
Correct |
299 ms |
147320 KB |
Output is correct |
6 |
Correct |
295 ms |
147320 KB |
Output is correct |
7 |
Correct |
281 ms |
147320 KB |
Output is correct |
8 |
Correct |
300 ms |
147320 KB |
Output is correct |
9 |
Correct |
181 ms |
141416 KB |
Output is correct |
10 |
Correct |
184 ms |
145128 KB |
Output is correct |
11 |
Correct |
3688 ms |
145908 KB |
Output is correct |
12 |
Execution timed out |
4029 ms |
146336 KB |
Time limit exceeded |
13 |
Halted |
0 ms |
0 KB |
- |