# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
415974 |
2021-06-01T18:45:03 Z |
iulia2100 |
Cake 3 (JOI19_cake3) |
C++14 |
|
4000 ms |
139644 KB |
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
//ifstream cin ("idk.in");
//ofstream cout ("idk.out");
const int N = 2e5 + 5;
int n, m;
struct idk {
long long v, c;
} v[N];
bool cmp(idk x, idk y) {
return x.c < y.c;
}
namespace segment_tree {
struct nod {
vector <long long> val, sp;
} a[4 * N];
vector <int> noduri;
int start;
void build() {
for (int i = start - 1; i; --i) {
int sz = a[i + i].val.size();
int p1 = 0, p2 = 0;
while((p1 < sz || p2 < sz) && p1 + p2 < m) {
if (p2 == sz || p1 < sz && a[i + i].val[p1] > a[i + i + 1].val[p2]) {
a[i].val.push_back(a[i + i].val[p1]);
++p1;
} else {
a[i].val.push_back(a[i + i + 1].val[p2]);
++p2;
}
}
long long sum = 0;
for (auto it : a[i].val) {
sum += it;
a[i].sp.push_back(sum);
}
}
}
long long nr_bigger(int nod, long long val) {
int st = 0, dr = a[nod].val.size() - 1, mij, ans = 0;
while (st <= dr) {
mij = (st + dr) / 2;
if (a[nod].val[mij] >= val) {
ans = mij + 1;
st = mij + 1;
}
else dr = mij - 1;
}
return ans;
}
long long sum_bigger(int nod, long long val) {
int st = 0, dr = a[nod].val.size() - 1, mij, ans = 0;
while (st <= dr) {
mij = (st + dr) / 2;
if (a[nod].val[mij] >= val) {
ans = mij + 1;
st = mij + 1;
}
else dr = mij - 1;
}
if (ans == 0)
return 0;
return a[nod].sp[ans - 1];
}
int nr_noduri(int val) {
int ans = 0;
for (auto it : noduri) {
ans += nr_bigger(it, val);
}
return ans;
}
long long sum_noduri(long long val) {
long long ans = 0;
for (auto it : noduri) {
ans += sum_bigger(it, val);
}
long long aux = nr_noduri(val);
return ans - (aux - (long long)m) * val;
}
void Query_aint(int st, int dr) {
if (st & 1)
noduri.push_back(st++);
if (!(dr & 1))
noduri.push_back(dr--);
if (st <= dr)
Query_aint(st / 2, dr / 2);
}
long long Query(int st, int dr) {
st += start - 1, dr += start - 1;
noduri.clear();
Query_aint(st, dr);
for (auto it : noduri) {
int st = 0, dr = a[it].val.size() - 1, mij;
while (st <= dr) {
mij = (st + dr) / 2;
long long aux = nr_noduri(a[it].val[mij]);
if (aux < m) {
st = mij + 1;
continue;
}
if (nr_noduri(a[it].val[mij] + 1) < m) {
return sum_noduri(a[it].val[mij]);
}
dr = mij - 1;
}
}
}
void init() {
start = 1;
while (start < n) {
start <<= 1;
}
for (int i = 1; i <= n; ++i) {
a[i + start - 1].val.push_back(v[i].v);
a[i + start - 1].sp.push_back(v[i].v);
}
for (int i = n + 1; i <= start; ++i) {
a[i + start - 1].val.push_back(0);
a[i + start - 1].sp.push_back(0);
}
build();
}
}
long long calc(int x, int r) {
if (r - x + 1 < m || r > n || r < 1 || x > n || x < 1)
return -1;
return segment_tree::Query(x, r) - 2 * (v[r].c - v[x].c);
}
int ans[N];
long long Max[N];
bool viz[N];
void find_ans(int poz, int st, int dr, int l, int r) {
if (ans[poz] || l > r || poz < l || r < poz || st == 0 && dr == 0 || viz[poz])
return;
viz[poz] = true;
ans[poz] = -1;
for (int i = max(st, poz + m - 1); i <= dr; ++i) {
long long k = calc(poz, i);
if (k >= Max[poz]) {
Max[poz] = k;
ans[poz] = i;
}
}
if (poz != l)
find_ans((l + poz) / 2, st, (ans[poz] != -1 ? ans[poz] : dr), l, poz - 1);
if (poz != r)
find_ans((r + poz) / 2, (ans[poz] != -1 ? ans[poz] : st), dr, poz + 1, r);
}
namespace brut {
priority_queue <long long> pq;
long long brut() {
long long sum = 0, ans = -1e18;
for (int i = 1; i <= n; ++i) {
sum = 0;
while (!pq.empty())
pq.pop();
for (int j = i; j <= n; ++j) {
pq.push(- v[j].v);
sum += v[j].v;
while (pq.size() > m) {
sum += pq.top();
pq.pop();
}
if (pq.size() == m)
ans = max(ans, sum - 2 * (v[j].c - v[i].c));
}
}
return ans;
}
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
cin >> v[i].v >> v[i].c;
Max[i] = -1e18;
}
sort (v + 1, v + n + 1, cmp);
if (n <= 2000) {
cout << brut::brut();
return 0;
}
// for (int i = 1; i <= n; ++i) {
// cout << v[i].v << ' ' << v[i].c << '\n';
// }
segment_tree::init();
find_ans((n + 1) / 2, 1, n, 1, n);
long long ANS = -1e18;
for (int i = 1; i <= n; ++i) {
ANS = max(ANS, Max[i]);
}
cout << ANS;
return 0;
}
Compilation message
cake3.cpp: In function 'void segment_tree::build()':
cake3.cpp:37:41: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
37 | if (p2 == sz || p1 < sz && a[i + i].val[p1] > a[i + i + 1].val[p2]) {
cake3.cpp: In function 'void find_ans(int, int, int, int, int)':
cake3.cpp:157:60: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
157 | if (ans[poz] || l > r || poz < l || r < poz || st == 0 && dr == 0 || viz[poz])
| ~~~~~~~~^~~~~~~~~~
cake3.cpp: In function 'long long int brut::brut()':
cake3.cpp:187:34: warning: comparison of integer expressions of different signedness: 'std::priority_queue<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
187 | while (pq.size() > m) {
| ~~~~~~~~~~^~~
cake3.cpp:191:31: warning: comparison of integer expressions of different signedness: 'std::priority_queue<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
191 | if (pq.size() == m)
| ~~~~~~~~~~^~~~
cake3.cpp: In function 'long long int segment_tree::Query(int, int)':
cake3.cpp:126:5: warning: control reaches end of non-void function [-Wreturn-type]
126 | }
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
37876 KB |
Output is correct |
2 |
Correct |
22 ms |
37984 KB |
Output is correct |
3 |
Correct |
24 ms |
37836 KB |
Output is correct |
4 |
Correct |
26 ms |
37836 KB |
Output is correct |
5 |
Correct |
22 ms |
37904 KB |
Output is correct |
6 |
Correct |
29 ms |
37836 KB |
Output is correct |
7 |
Correct |
26 ms |
37836 KB |
Output is correct |
8 |
Correct |
21 ms |
37808 KB |
Output is correct |
9 |
Correct |
25 ms |
37836 KB |
Output is correct |
10 |
Correct |
22 ms |
37844 KB |
Output is correct |
11 |
Correct |
27 ms |
37876 KB |
Output is correct |
12 |
Correct |
26 ms |
37836 KB |
Output is correct |
13 |
Correct |
25 ms |
37828 KB |
Output is correct |
14 |
Correct |
21 ms |
37836 KB |
Output is correct |
15 |
Correct |
28 ms |
37864 KB |
Output is correct |
16 |
Correct |
26 ms |
37848 KB |
Output is correct |
17 |
Correct |
23 ms |
37836 KB |
Output is correct |
18 |
Correct |
23 ms |
37836 KB |
Output is correct |
19 |
Correct |
25 ms |
37840 KB |
Output is correct |
20 |
Correct |
26 ms |
37848 KB |
Output is correct |
21 |
Correct |
26 ms |
37888 KB |
Output is correct |
22 |
Correct |
25 ms |
37888 KB |
Output is correct |
23 |
Correct |
25 ms |
37872 KB |
Output is correct |
24 |
Correct |
22 ms |
37884 KB |
Output is correct |
25 |
Correct |
26 ms |
37836 KB |
Output is correct |
26 |
Correct |
22 ms |
37904 KB |
Output is correct |
27 |
Correct |
22 ms |
37836 KB |
Output is correct |
28 |
Correct |
22 ms |
37816 KB |
Output is correct |
29 |
Correct |
22 ms |
37836 KB |
Output is correct |
30 |
Correct |
28 ms |
37804 KB |
Output is correct |
31 |
Correct |
23 ms |
37864 KB |
Output is correct |
32 |
Correct |
30 ms |
37836 KB |
Output is correct |
33 |
Correct |
25 ms |
37868 KB |
Output is correct |
34 |
Correct |
24 ms |
37808 KB |
Output is correct |
35 |
Correct |
21 ms |
37788 KB |
Output is correct |
36 |
Correct |
21 ms |
37848 KB |
Output is correct |
37 |
Correct |
23 ms |
37868 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
37876 KB |
Output is correct |
2 |
Correct |
22 ms |
37984 KB |
Output is correct |
3 |
Correct |
24 ms |
37836 KB |
Output is correct |
4 |
Correct |
26 ms |
37836 KB |
Output is correct |
5 |
Correct |
22 ms |
37904 KB |
Output is correct |
6 |
Correct |
29 ms |
37836 KB |
Output is correct |
7 |
Correct |
26 ms |
37836 KB |
Output is correct |
8 |
Correct |
21 ms |
37808 KB |
Output is correct |
9 |
Correct |
25 ms |
37836 KB |
Output is correct |
10 |
Correct |
22 ms |
37844 KB |
Output is correct |
11 |
Correct |
27 ms |
37876 KB |
Output is correct |
12 |
Correct |
26 ms |
37836 KB |
Output is correct |
13 |
Correct |
25 ms |
37828 KB |
Output is correct |
14 |
Correct |
21 ms |
37836 KB |
Output is correct |
15 |
Correct |
28 ms |
37864 KB |
Output is correct |
16 |
Correct |
26 ms |
37848 KB |
Output is correct |
17 |
Correct |
23 ms |
37836 KB |
Output is correct |
18 |
Correct |
23 ms |
37836 KB |
Output is correct |
19 |
Correct |
25 ms |
37840 KB |
Output is correct |
20 |
Correct |
26 ms |
37848 KB |
Output is correct |
21 |
Correct |
26 ms |
37888 KB |
Output is correct |
22 |
Correct |
25 ms |
37888 KB |
Output is correct |
23 |
Correct |
25 ms |
37872 KB |
Output is correct |
24 |
Correct |
22 ms |
37884 KB |
Output is correct |
25 |
Correct |
26 ms |
37836 KB |
Output is correct |
26 |
Correct |
22 ms |
37904 KB |
Output is correct |
27 |
Correct |
22 ms |
37836 KB |
Output is correct |
28 |
Correct |
22 ms |
37816 KB |
Output is correct |
29 |
Correct |
22 ms |
37836 KB |
Output is correct |
30 |
Correct |
28 ms |
37804 KB |
Output is correct |
31 |
Correct |
23 ms |
37864 KB |
Output is correct |
32 |
Correct |
30 ms |
37836 KB |
Output is correct |
33 |
Correct |
25 ms |
37868 KB |
Output is correct |
34 |
Correct |
24 ms |
37808 KB |
Output is correct |
35 |
Correct |
21 ms |
37788 KB |
Output is correct |
36 |
Correct |
21 ms |
37848 KB |
Output is correct |
37 |
Correct |
23 ms |
37868 KB |
Output is correct |
38 |
Correct |
158 ms |
37956 KB |
Output is correct |
39 |
Correct |
182 ms |
37976 KB |
Output is correct |
40 |
Correct |
181 ms |
37968 KB |
Output is correct |
41 |
Correct |
169 ms |
37964 KB |
Output is correct |
42 |
Correct |
197 ms |
38076 KB |
Output is correct |
43 |
Correct |
173 ms |
37976 KB |
Output is correct |
44 |
Correct |
162 ms |
37956 KB |
Output is correct |
45 |
Correct |
178 ms |
37960 KB |
Output is correct |
46 |
Correct |
188 ms |
37968 KB |
Output is correct |
47 |
Correct |
159 ms |
37956 KB |
Output is correct |
48 |
Correct |
153 ms |
37956 KB |
Output is correct |
49 |
Correct |
201 ms |
37972 KB |
Output is correct |
50 |
Correct |
200 ms |
37888 KB |
Output is correct |
51 |
Correct |
197 ms |
37960 KB |
Output is correct |
52 |
Correct |
196 ms |
37960 KB |
Output is correct |
53 |
Correct |
184 ms |
37964 KB |
Output is correct |
54 |
Correct |
202 ms |
37996 KB |
Output is correct |
55 |
Correct |
201 ms |
37976 KB |
Output is correct |
56 |
Correct |
188 ms |
37980 KB |
Output is correct |
57 |
Correct |
184 ms |
38084 KB |
Output is correct |
58 |
Correct |
190 ms |
37976 KB |
Output is correct |
59 |
Correct |
66 ms |
37964 KB |
Output is correct |
60 |
Correct |
74 ms |
37964 KB |
Output is correct |
61 |
Correct |
66 ms |
37960 KB |
Output is correct |
62 |
Correct |
71 ms |
37896 KB |
Output is correct |
63 |
Correct |
105 ms |
37984 KB |
Output is correct |
64 |
Correct |
70 ms |
37968 KB |
Output is correct |
65 |
Correct |
152 ms |
37960 KB |
Output is correct |
66 |
Correct |
155 ms |
37964 KB |
Output is correct |
67 |
Correct |
153 ms |
37956 KB |
Output is correct |
68 |
Correct |
179 ms |
37976 KB |
Output is correct |
69 |
Correct |
167 ms |
37956 KB |
Output is correct |
70 |
Correct |
168 ms |
37956 KB |
Output is correct |
71 |
Correct |
157 ms |
37836 KB |
Output is correct |
72 |
Correct |
170 ms |
38084 KB |
Output is correct |
73 |
Correct |
169 ms |
37860 KB |
Output is correct |
74 |
Correct |
212 ms |
37992 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
37876 KB |
Output is correct |
2 |
Correct |
22 ms |
37984 KB |
Output is correct |
3 |
Correct |
24 ms |
37836 KB |
Output is correct |
4 |
Correct |
26 ms |
37836 KB |
Output is correct |
5 |
Correct |
22 ms |
37904 KB |
Output is correct |
6 |
Correct |
29 ms |
37836 KB |
Output is correct |
7 |
Correct |
26 ms |
37836 KB |
Output is correct |
8 |
Correct |
21 ms |
37808 KB |
Output is correct |
9 |
Correct |
25 ms |
37836 KB |
Output is correct |
10 |
Correct |
22 ms |
37844 KB |
Output is correct |
11 |
Correct |
27 ms |
37876 KB |
Output is correct |
12 |
Correct |
26 ms |
37836 KB |
Output is correct |
13 |
Correct |
25 ms |
37828 KB |
Output is correct |
14 |
Correct |
21 ms |
37836 KB |
Output is correct |
15 |
Correct |
28 ms |
37864 KB |
Output is correct |
16 |
Correct |
26 ms |
37848 KB |
Output is correct |
17 |
Correct |
23 ms |
37836 KB |
Output is correct |
18 |
Correct |
23 ms |
37836 KB |
Output is correct |
19 |
Correct |
25 ms |
37840 KB |
Output is correct |
20 |
Correct |
26 ms |
37848 KB |
Output is correct |
21 |
Correct |
26 ms |
37888 KB |
Output is correct |
22 |
Correct |
25 ms |
37888 KB |
Output is correct |
23 |
Correct |
25 ms |
37872 KB |
Output is correct |
24 |
Correct |
22 ms |
37884 KB |
Output is correct |
25 |
Correct |
26 ms |
37836 KB |
Output is correct |
26 |
Correct |
22 ms |
37904 KB |
Output is correct |
27 |
Correct |
22 ms |
37836 KB |
Output is correct |
28 |
Correct |
22 ms |
37816 KB |
Output is correct |
29 |
Correct |
22 ms |
37836 KB |
Output is correct |
30 |
Correct |
28 ms |
37804 KB |
Output is correct |
31 |
Correct |
23 ms |
37864 KB |
Output is correct |
32 |
Correct |
30 ms |
37836 KB |
Output is correct |
33 |
Correct |
25 ms |
37868 KB |
Output is correct |
34 |
Correct |
24 ms |
37808 KB |
Output is correct |
35 |
Correct |
21 ms |
37788 KB |
Output is correct |
36 |
Correct |
21 ms |
37848 KB |
Output is correct |
37 |
Correct |
23 ms |
37868 KB |
Output is correct |
38 |
Correct |
158 ms |
37956 KB |
Output is correct |
39 |
Correct |
182 ms |
37976 KB |
Output is correct |
40 |
Correct |
181 ms |
37968 KB |
Output is correct |
41 |
Correct |
169 ms |
37964 KB |
Output is correct |
42 |
Correct |
197 ms |
38076 KB |
Output is correct |
43 |
Correct |
173 ms |
37976 KB |
Output is correct |
44 |
Correct |
162 ms |
37956 KB |
Output is correct |
45 |
Correct |
178 ms |
37960 KB |
Output is correct |
46 |
Correct |
188 ms |
37968 KB |
Output is correct |
47 |
Correct |
159 ms |
37956 KB |
Output is correct |
48 |
Correct |
153 ms |
37956 KB |
Output is correct |
49 |
Correct |
201 ms |
37972 KB |
Output is correct |
50 |
Correct |
200 ms |
37888 KB |
Output is correct |
51 |
Correct |
197 ms |
37960 KB |
Output is correct |
52 |
Correct |
196 ms |
37960 KB |
Output is correct |
53 |
Correct |
184 ms |
37964 KB |
Output is correct |
54 |
Correct |
202 ms |
37996 KB |
Output is correct |
55 |
Correct |
201 ms |
37976 KB |
Output is correct |
56 |
Correct |
188 ms |
37980 KB |
Output is correct |
57 |
Correct |
184 ms |
38084 KB |
Output is correct |
58 |
Correct |
190 ms |
37976 KB |
Output is correct |
59 |
Correct |
66 ms |
37964 KB |
Output is correct |
60 |
Correct |
74 ms |
37964 KB |
Output is correct |
61 |
Correct |
66 ms |
37960 KB |
Output is correct |
62 |
Correct |
71 ms |
37896 KB |
Output is correct |
63 |
Correct |
105 ms |
37984 KB |
Output is correct |
64 |
Correct |
70 ms |
37968 KB |
Output is correct |
65 |
Correct |
152 ms |
37960 KB |
Output is correct |
66 |
Correct |
155 ms |
37964 KB |
Output is correct |
67 |
Correct |
153 ms |
37956 KB |
Output is correct |
68 |
Correct |
179 ms |
37976 KB |
Output is correct |
69 |
Correct |
167 ms |
37956 KB |
Output is correct |
70 |
Correct |
168 ms |
37956 KB |
Output is correct |
71 |
Correct |
157 ms |
37836 KB |
Output is correct |
72 |
Correct |
170 ms |
38084 KB |
Output is correct |
73 |
Correct |
169 ms |
37860 KB |
Output is correct |
74 |
Correct |
212 ms |
37992 KB |
Output is correct |
75 |
Execution timed out |
4038 ms |
139644 KB |
Time limit exceeded |
76 |
Halted |
0 ms |
0 KB |
- |