# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
120456 |
2019-06-24T14:26:48 Z |
RockyB |
Teams (IOI15_teams) |
C++11 |
|
4000 ms |
162956 KB |
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include "teams.h"
#include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define pp pop_back
#define mp make_pair
#define sz(x) (int)x.size()
#define sqr(x) ((x) * 1ll * (x))
#define all(x) x.begin(), x.end()
const int MAXN = (int)5e5 + 7;
typedef long long ll;
using namespace std;
int N;
vector < pair <int, int > > a;
int sz;
int root[MAXN];
vector <int> q[MAXN];
ll dp[MAXN];
struct tree {
int t[MAXN * 30], ls[MAXN * 30], rs[MAXN * 30];
inline void upd(int p, int &v, int lv, int tl = 1, int tr = MAXN) {
v = ++sz;
if (tl == tr) {
t[v] = t[lv] + 1;
return;
}
int tm = tl + tr >> 1;
if (p <= tm) rs[v] = rs[lv], upd(p, ls[v], ls[lv], tl, tm);
else ls[v] = ls[lv], upd(p, rs[v], rs[lv], tm + 1, tr);
t[v] = t[ls[v]] + t[rs[v]];
}
inline int get(int l, int r, int v, int tl = 1, int tr = MAXN) {
//cerr << tl << ' ' << tr << ' ' << v << endl;
if (tl > r || tr < l || !v) return 0;
if (l <= tl && tr <= r) return t[v];
int tm = tl + tr >> 1;
return get(l, r, ls[v], tl, tm) + get(l, r, rs[v], tm + 1, tr);
}
} t;
void init(int _N, int A[], int B[]) {
N = _N;
for (int i = 0; i < N; i++) {
a.pb({A[i], B[i]});
q[A[i]].pb(B[i]);
}
root[0] = ++sz;
for (int i = 1; i < MAXN; i++) {
root[i] = root[i - 1];
for (auto it : q[i]) {
t.upd(it, root[i], root[i]);
}
}
}
int can(int M, int K[]) {
sort (K, K + M);
ll sum = 0;
vector < pair <int, int> > k;
for (int i = 0; i < M; i++) {
if (!sz(k) || k.back().f != K[i]) k.pb({K[i], 1});
else k.back().s++;
sum += K[i];
}
if (sum > sz(a)) return 0;
for (int i = 0; i < sz(k); i++) {
int cnt = t.get(k[i].f, MAXN, root[k[i].f]);
ll cur = (ll)k[i].f * k[i].s;
if (cnt < cur) return 0;
dp[i] = 0;
for (int j = i - 1; j >= 0; j--) {
int com = t.get(k[i].f, MAXN, root[k[j].f]);
dp[i] = max(dp[i], dp[j] + com);
}
dp[i] += cur - cnt;
if (dp[i] > 0) return 0;
}
return 1;
}
Compilation message
teams.cpp: In member function 'void tree::upd(int, int&, int, int, int)':
teams.cpp:41:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int tm = tl + tr >> 1;
~~~^~~~
teams.cpp: In member function 'int tree::get(int, int, int, int, int)':
teams.cpp:50:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int tm = tl + tr >> 1;
~~~^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
14052 KB |
Output is correct |
2 |
Correct |
15 ms |
14080 KB |
Output is correct |
3 |
Correct |
16 ms |
14080 KB |
Output is correct |
4 |
Correct |
16 ms |
14080 KB |
Output is correct |
5 |
Correct |
15 ms |
14080 KB |
Output is correct |
6 |
Correct |
18 ms |
14080 KB |
Output is correct |
7 |
Correct |
17 ms |
14080 KB |
Output is correct |
8 |
Correct |
16 ms |
14080 KB |
Output is correct |
9 |
Correct |
16 ms |
14080 KB |
Output is correct |
10 |
Correct |
17 ms |
14080 KB |
Output is correct |
11 |
Correct |
16 ms |
14080 KB |
Output is correct |
12 |
Correct |
17 ms |
14080 KB |
Output is correct |
13 |
Correct |
16 ms |
14080 KB |
Output is correct |
14 |
Correct |
15 ms |
14052 KB |
Output is correct |
15 |
Correct |
18 ms |
14080 KB |
Output is correct |
16 |
Correct |
15 ms |
14080 KB |
Output is correct |
17 |
Correct |
15 ms |
14080 KB |
Output is correct |
18 |
Correct |
17 ms |
14080 KB |
Output is correct |
19 |
Correct |
15 ms |
13980 KB |
Output is correct |
20 |
Correct |
16 ms |
14080 KB |
Output is correct |
21 |
Correct |
15 ms |
14080 KB |
Output is correct |
22 |
Correct |
16 ms |
14080 KB |
Output is correct |
23 |
Correct |
35 ms |
14080 KB |
Output is correct |
24 |
Correct |
16 ms |
14080 KB |
Output is correct |
25 |
Correct |
15 ms |
14080 KB |
Output is correct |
26 |
Correct |
15 ms |
14080 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
94 ms |
40880 KB |
Output is correct |
2 |
Correct |
105 ms |
42052 KB |
Output is correct |
3 |
Correct |
101 ms |
41936 KB |
Output is correct |
4 |
Correct |
111 ms |
42600 KB |
Output is correct |
5 |
Correct |
53 ms |
40556 KB |
Output is correct |
6 |
Correct |
49 ms |
40428 KB |
Output is correct |
7 |
Correct |
49 ms |
40428 KB |
Output is correct |
8 |
Correct |
46 ms |
40432 KB |
Output is correct |
9 |
Correct |
49 ms |
40940 KB |
Output is correct |
10 |
Correct |
46 ms |
40576 KB |
Output is correct |
11 |
Correct |
47 ms |
40580 KB |
Output is correct |
12 |
Correct |
46 ms |
40684 KB |
Output is correct |
13 |
Correct |
55 ms |
40940 KB |
Output is correct |
14 |
Correct |
63 ms |
41452 KB |
Output is correct |
15 |
Correct |
88 ms |
41964 KB |
Output is correct |
16 |
Correct |
87 ms |
41836 KB |
Output is correct |
17 |
Correct |
48 ms |
40812 KB |
Output is correct |
18 |
Correct |
49 ms |
40812 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
108 ms |
41404 KB |
Output is correct |
2 |
Correct |
105 ms |
42704 KB |
Output is correct |
3 |
Correct |
214 ms |
46112 KB |
Output is correct |
4 |
Correct |
101 ms |
42604 KB |
Output is correct |
5 |
Correct |
1357 ms |
41384 KB |
Output is correct |
6 |
Correct |
1018 ms |
41324 KB |
Output is correct |
7 |
Correct |
56 ms |
41196 KB |
Output is correct |
8 |
Correct |
782 ms |
41232 KB |
Output is correct |
9 |
Correct |
50 ms |
40812 KB |
Output is correct |
10 |
Correct |
52 ms |
40812 KB |
Output is correct |
11 |
Correct |
127 ms |
40940 KB |
Output is correct |
12 |
Correct |
752 ms |
41196 KB |
Output is correct |
13 |
Correct |
285 ms |
41964 KB |
Output is correct |
14 |
Correct |
209 ms |
44268 KB |
Output is correct |
15 |
Correct |
128 ms |
42740 KB |
Output is correct |
16 |
Correct |
121 ms |
42700 KB |
Output is correct |
17 |
Correct |
89 ms |
41612 KB |
Output is correct |
18 |
Correct |
81 ms |
41452 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
691 ms |
149460 KB |
Output is correct |
2 |
Correct |
830 ms |
156240 KB |
Output is correct |
3 |
Correct |
1034 ms |
162956 KB |
Output is correct |
4 |
Correct |
705 ms |
155956 KB |
Output is correct |
5 |
Execution timed out |
4093 ms |
146996 KB |
Time limit exceeded |
6 |
Halted |
0 ms |
0 KB |
- |