# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
541102 |
2022-03-22T08:27:33 Z |
GioChkhaidze |
Teams (IOI15_teams) |
C++14 |
|
1465 ms |
144544 KB |
#include <bits/stdc++.h>
#include "teams.h"
#define lf (h << 1)
#define mf ((l + r) >> 1)
#define rf ((h << 1) | 1)
#define tree int h, int l, int r
#define left lf, l, mf
#define right rf, mf + 1, r
#define ll long long
#define pb push_back
#define f first
#define s second
using namespace std;
const int Nn = 5e5 + 5;
bool used[Nn];
int n, m, cost, a[Nn], b[Nn], k[Nn], dp[Nn], pr[Nn], nx[Nn], mpr[Nn];
vector < int > v[4* Nn], O[Nn];
void build(tree) {
if (l == r) {
v[h] = O[l];
return;
}
build(left), build(right);
int li = 0, ri = 0, ls = v[lf].size(), rs = v[rf].size();
while (li < ls || ri < rs) {
if (li < ls && (ri == rs || v[lf][li] <= v[rf][ri])) {
v[h].pb(v[lf][li++]);
}
else
if (ri < rs && (li == ls || v[rf][ri] <= v[lf][li])) {
v[h].pb(v[rf][ri++]);
}
}
}
int Mn, Mx, id;
int g(int h) {
int l = (lower_bound(v[h].begin(), v[h].end(), Mn) - v[h].begin());
int r = (lower_bound(v[h].begin(), v[h].end(), Mx + 1) - v[h].begin());
return max(0, r - l);
}
int get(tree) {
if (l == r) return g(h);
if (Mx <= mf) return get(left) + g(rf);
return get(right);
}
int Get(tree, int vl) {
if (l == r) {
if (g(h) <= vl) return l;
return n + 1;
}
int rc = g(rf);
if (rc <= vl)
return min(mf + 1, Get(left, vl - rc));
return Get(right, vl);
}
int Mm(int tl, int tr) {
Mn = k[tl] + 1, Mx = k[tr];
return Get(1, 1, n, dp[tr] - dp[tl]);
}
void init(int N, int A[], int B[]) {
n = N;
for (int i = 1; i <= n; ++i) {
a[i] = A[i - 1];
b[i] = B[i - 1];
O[b[i]].pb(a[i]);
}
for (int i = 1; i <= n; ++i) {
sort(O[i].begin(), O[i].end());
}
build(1, 1, n);
}
int can(int M, int K[]) {
m = M;
ll sum = 0;
for (int i = 1; i <= m; ++i) {
pr[i] = nx[i] = used[i] = 0;
k[i] = K[i - 1];
sum += k[i];
}
sort(k + 1, k + m + 1);
if (sum > n) return 0;
set < pair < int , int > > st;
vector < int > dq;
dq.push_back(0);
for (int i = 1; i <= m; ++i) {
while (st.size() && (*st.begin()).f <= k[i]) {
int mo = (*st.begin()).f;
int id = (*st.begin()).s;
st.erase(st.find({mo, id}));
used[id] = true;
int tl = pr[id], tr = nx[id];
if (tr) {
st.erase({mpr[tr], tr});
mpr[tr] = Mm(tl, tr);
st.insert({mpr[tr], tr});
nx[tl] = tr, pr[tr] = tl;
}
}
while (used[dq.back()]) {
dq.pop_back();
}
int l = dq.back();
Mn = k[l] + 1, Mx = k[i];
dp[i] = dp[l] - k[i] + get(1, 1, n);
if (dp[i] < 0) return false;
dq.push_back(i);
mpr[i] = Mm(l, i);
pr[i] = l, nx[l] = i;
st.insert({mpr[i], i});
}
return true;
}
Compilation message
teams.cpp: In function 'void build(int, int, int)':
teams.cpp:29:38: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
29 | int li = 0, ri = 0, ls = v[lf].size(), rs = v[rf].size();
| ~~~~~~~~~~^~
teams.cpp:29:57: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
29 | int li = 0, ri = 0, ls = v[lf].size(), rs = v[rf].size();
| ~~~~~~~~~~^~
teams.cpp: In function 'int g(int)':
teams.cpp:43:53: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
43 | int l = (lower_bound(v[h].begin(), v[h].end(), Mn) - v[h].begin());
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~
teams.cpp:44:57: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
44 | int r = (lower_bound(v[h].begin(), v[h].end(), Mx + 1) - v[h].begin());
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:99:8: warning: declaration of 'id' shadows a global declaration [-Wshadow]
99 | int id = (*st.begin()).s;
| ^~
teams.cpp:41:13: note: shadowed declaration is here
41 | int Mn, Mx, id;
| ^~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
34 ms |
58984 KB |
Output is correct |
2 |
Correct |
39 ms |
58940 KB |
Output is correct |
3 |
Correct |
33 ms |
58988 KB |
Output is correct |
4 |
Correct |
35 ms |
59068 KB |
Output is correct |
5 |
Correct |
38 ms |
59044 KB |
Output is correct |
6 |
Correct |
35 ms |
59176 KB |
Output is correct |
7 |
Correct |
36 ms |
59060 KB |
Output is correct |
8 |
Correct |
34 ms |
58932 KB |
Output is correct |
9 |
Correct |
32 ms |
59056 KB |
Output is correct |
10 |
Correct |
35 ms |
59016 KB |
Output is correct |
11 |
Correct |
37 ms |
59068 KB |
Output is correct |
12 |
Correct |
37 ms |
58988 KB |
Output is correct |
13 |
Correct |
32 ms |
58964 KB |
Output is correct |
14 |
Correct |
37 ms |
58976 KB |
Output is correct |
15 |
Correct |
37 ms |
59164 KB |
Output is correct |
16 |
Correct |
35 ms |
59056 KB |
Output is correct |
17 |
Correct |
34 ms |
59032 KB |
Output is correct |
18 |
Correct |
37 ms |
59016 KB |
Output is correct |
19 |
Correct |
33 ms |
58968 KB |
Output is correct |
20 |
Correct |
32 ms |
59012 KB |
Output is correct |
21 |
Correct |
34 ms |
59064 KB |
Output is correct |
22 |
Correct |
39 ms |
58956 KB |
Output is correct |
23 |
Correct |
36 ms |
59052 KB |
Output is correct |
24 |
Correct |
37 ms |
59064 KB |
Output is correct |
25 |
Correct |
33 ms |
59040 KB |
Output is correct |
26 |
Correct |
39 ms |
58964 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
102 ms |
74356 KB |
Output is correct |
2 |
Correct |
103 ms |
74348 KB |
Output is correct |
3 |
Correct |
91 ms |
74448 KB |
Output is correct |
4 |
Correct |
90 ms |
75920 KB |
Output is correct |
5 |
Correct |
50 ms |
69400 KB |
Output is correct |
6 |
Correct |
48 ms |
69496 KB |
Output is correct |
7 |
Correct |
47 ms |
69480 KB |
Output is correct |
8 |
Correct |
46 ms |
69428 KB |
Output is correct |
9 |
Correct |
90 ms |
70308 KB |
Output is correct |
10 |
Correct |
53 ms |
68980 KB |
Output is correct |
11 |
Correct |
47 ms |
68360 KB |
Output is correct |
12 |
Correct |
50 ms |
68048 KB |
Output is correct |
13 |
Correct |
57 ms |
69064 KB |
Output is correct |
14 |
Correct |
65 ms |
70984 KB |
Output is correct |
15 |
Correct |
84 ms |
73864 KB |
Output is correct |
16 |
Correct |
84 ms |
73984 KB |
Output is correct |
17 |
Correct |
50 ms |
69272 KB |
Output is correct |
18 |
Correct |
51 ms |
69276 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
96 ms |
74580 KB |
Output is correct |
2 |
Correct |
98 ms |
74568 KB |
Output is correct |
3 |
Correct |
323 ms |
77436 KB |
Output is correct |
4 |
Correct |
97 ms |
76012 KB |
Output is correct |
5 |
Correct |
159 ms |
69500 KB |
Output is correct |
6 |
Correct |
134 ms |
69444 KB |
Output is correct |
7 |
Correct |
56 ms |
69444 KB |
Output is correct |
8 |
Correct |
111 ms |
69392 KB |
Output is correct |
9 |
Correct |
82 ms |
70236 KB |
Output is correct |
10 |
Correct |
88 ms |
69332 KB |
Output is correct |
11 |
Correct |
90 ms |
68528 KB |
Output is correct |
12 |
Correct |
112 ms |
68148 KB |
Output is correct |
13 |
Correct |
237 ms |
69284 KB |
Output is correct |
14 |
Correct |
397 ms |
74808 KB |
Output is correct |
15 |
Correct |
179 ms |
74056 KB |
Output is correct |
16 |
Correct |
181 ms |
74112 KB |
Output is correct |
17 |
Correct |
172 ms |
69412 KB |
Output is correct |
18 |
Correct |
165 ms |
69264 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
427 ms |
140020 KB |
Output is correct |
2 |
Correct |
470 ms |
140020 KB |
Output is correct |
3 |
Correct |
1136 ms |
144544 KB |
Output is correct |
4 |
Correct |
422 ms |
142652 KB |
Output is correct |
5 |
Correct |
428 ms |
113692 KB |
Output is correct |
6 |
Correct |
378 ms |
113484 KB |
Output is correct |
7 |
Correct |
121 ms |
113548 KB |
Output is correct |
8 |
Correct |
333 ms |
113760 KB |
Output is correct |
9 |
Correct |
347 ms |
118720 KB |
Output is correct |
10 |
Correct |
209 ms |
110360 KB |
Output is correct |
11 |
Correct |
212 ms |
109232 KB |
Output is correct |
12 |
Correct |
274 ms |
109324 KB |
Output is correct |
13 |
Correct |
865 ms |
112644 KB |
Output is correct |
14 |
Correct |
1465 ms |
138384 KB |
Output is correct |
15 |
Correct |
586 ms |
134716 KB |
Output is correct |
16 |
Correct |
578 ms |
134528 KB |
Output is correct |
17 |
Correct |
456 ms |
112096 KB |
Output is correct |
18 |
Correct |
434 ms |
112136 KB |
Output is correct |