# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
977565 |
2024-05-08T07:01:25 Z |
12345678 |
Cake 3 (JOI19_cake3) |
C++17 |
|
832 ms |
208248 KB |
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
const int nx=2e5+5;
ll n, m, cnt, ans=-1e18;
vector<pair<ll, ll>> v;
struct cake
{
ll v, c, idx;
cake(): v(0), c(0), idx(0){}
bool operator< (const cake &o) const {
if (c==o.c) return v<o.v;
return c<o.c;
}
} c[nx];
struct persist
{
struct node
{
ll f, s;
node *l, *r;
node(ll f, ll s): f(f), s(s), l(0), r(0) {}
};
typedef node* pnode;
pnode rt[nx];
void build(int l, int r, pnode &k)
{
k=new node(0, 0);
if (l==r) return;
int md=(l+r)/2;
build(l, md, k->l);
build(md+1, r, k->r);
}
void update(int l, int r, pnode &k, pnode t, int idx, ll vl)
{
k=new node(*t);
k->f++;
k->s+=vl;
if (l==r) return;
int md=(l+r)/2;
if (idx<=md) update(l, md, k->l, t->l, idx, vl);
else update(md+1, r, k->r, t->r, idx, vl);
}
ll query2(int l, int r, pnode k, pnode t, ll key)
{
if (l==r) return k->s-t->s;
int md=(l+r)/2;
if ((k->r->f-t->r->f)<key) return query2(l, md, k->l, t->l, key-(k->r->f-t->r->f))+k->r->s-t->r->s;
else return query2(md+1, r, k->r, t->r, key);
}
ll query(int l, int r)
{
return query2(1, n, rt[r], rt[l-1], m)-2*(c[r].c-c[l].c);
}
} s;
void solve(int l, int r, int optl, int optr)
{
if (r<l) return;
int md=(l+r)/2;
pair<ll, ll> mx={-1e18, 0};
for (int i=optl; i<=min(md-m+1, (ll)optr); i++) mx=max(mx, {s.query(i, md), i});
ans=max(ans, mx.first);
solve(l, md-1, optl, mx.second);
solve(md+1, r, mx.second, optr);
}
int32_t main()
{
cin.tie(NULL)->sync_with_stdio(false);
cin>>n>>m;
for (int i=1; i<=n; i++) cin>>c[i].v>>c[i].c, v.push_back({c[i].v, i});
sort(v.begin(), v.end());
for (int i=0; i<n; i++) c[v[i].second].idx=i+1;
sort(c+1, c+n+1);
s.build(1, n, s.rt[0]);
for (int i=1; i<=n; i++) s.update(1, n, s.rt[i], s.rt[i-1], c[i].idx, c[i].v);
//for (int i=1; i<=n; i++) for (int j=i; j<=n; j++) cout<<"debug "<<i<<' '<<j<<' '<<s.query(i, j)<<'\n';
solve(m, n, 1, n);
cout<<ans;
}
/*
2 2
1 1
1 1
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
6492 KB |
Output is correct |
2 |
Correct |
2 ms |
6492 KB |
Output is correct |
3 |
Correct |
2 ms |
6492 KB |
Output is correct |
4 |
Correct |
2 ms |
6744 KB |
Output is correct |
5 |
Correct |
2 ms |
6492 KB |
Output is correct |
6 |
Correct |
2 ms |
6492 KB |
Output is correct |
7 |
Correct |
2 ms |
6492 KB |
Output is correct |
8 |
Correct |
2 ms |
6492 KB |
Output is correct |
9 |
Correct |
2 ms |
6492 KB |
Output is correct |
10 |
Correct |
2 ms |
6488 KB |
Output is correct |
11 |
Correct |
2 ms |
6492 KB |
Output is correct |
12 |
Correct |
2 ms |
6492 KB |
Output is correct |
13 |
Correct |
2 ms |
6492 KB |
Output is correct |
14 |
Correct |
2 ms |
6492 KB |
Output is correct |
15 |
Correct |
2 ms |
6492 KB |
Output is correct |
16 |
Correct |
2 ms |
6492 KB |
Output is correct |
17 |
Correct |
2 ms |
6492 KB |
Output is correct |
18 |
Correct |
2 ms |
6492 KB |
Output is correct |
19 |
Correct |
2 ms |
6492 KB |
Output is correct |
20 |
Correct |
2 ms |
6492 KB |
Output is correct |
21 |
Correct |
2 ms |
6492 KB |
Output is correct |
22 |
Correct |
2 ms |
6492 KB |
Output is correct |
23 |
Correct |
2 ms |
6488 KB |
Output is correct |
24 |
Correct |
2 ms |
6492 KB |
Output is correct |
25 |
Correct |
3 ms |
6488 KB |
Output is correct |
26 |
Correct |
2 ms |
6488 KB |
Output is correct |
27 |
Correct |
2 ms |
6488 KB |
Output is correct |
28 |
Correct |
2 ms |
6492 KB |
Output is correct |
29 |
Correct |
2 ms |
6492 KB |
Output is correct |
30 |
Correct |
2 ms |
6488 KB |
Output is correct |
31 |
Correct |
2 ms |
6492 KB |
Output is correct |
32 |
Correct |
2 ms |
6492 KB |
Output is correct |
33 |
Correct |
2 ms |
6588 KB |
Output is correct |
34 |
Correct |
2 ms |
6492 KB |
Output is correct |
35 |
Correct |
2 ms |
6492 KB |
Output is correct |
36 |
Correct |
2 ms |
6492 KB |
Output is correct |
37 |
Correct |
2 ms |
6492 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
6492 KB |
Output is correct |
2 |
Correct |
2 ms |
6492 KB |
Output is correct |
3 |
Correct |
2 ms |
6492 KB |
Output is correct |
4 |
Correct |
2 ms |
6744 KB |
Output is correct |
5 |
Correct |
2 ms |
6492 KB |
Output is correct |
6 |
Correct |
2 ms |
6492 KB |
Output is correct |
7 |
Correct |
2 ms |
6492 KB |
Output is correct |
8 |
Correct |
2 ms |
6492 KB |
Output is correct |
9 |
Correct |
2 ms |
6492 KB |
Output is correct |
10 |
Correct |
2 ms |
6488 KB |
Output is correct |
11 |
Correct |
2 ms |
6492 KB |
Output is correct |
12 |
Correct |
2 ms |
6492 KB |
Output is correct |
13 |
Correct |
2 ms |
6492 KB |
Output is correct |
14 |
Correct |
2 ms |
6492 KB |
Output is correct |
15 |
Correct |
2 ms |
6492 KB |
Output is correct |
16 |
Correct |
2 ms |
6492 KB |
Output is correct |
17 |
Correct |
2 ms |
6492 KB |
Output is correct |
18 |
Correct |
2 ms |
6492 KB |
Output is correct |
19 |
Correct |
2 ms |
6492 KB |
Output is correct |
20 |
Correct |
2 ms |
6492 KB |
Output is correct |
21 |
Correct |
2 ms |
6492 KB |
Output is correct |
22 |
Correct |
2 ms |
6492 KB |
Output is correct |
23 |
Correct |
2 ms |
6488 KB |
Output is correct |
24 |
Correct |
2 ms |
6492 KB |
Output is correct |
25 |
Correct |
3 ms |
6488 KB |
Output is correct |
26 |
Correct |
2 ms |
6488 KB |
Output is correct |
27 |
Correct |
2 ms |
6488 KB |
Output is correct |
28 |
Correct |
2 ms |
6492 KB |
Output is correct |
29 |
Correct |
2 ms |
6492 KB |
Output is correct |
30 |
Correct |
2 ms |
6488 KB |
Output is correct |
31 |
Correct |
2 ms |
6492 KB |
Output is correct |
32 |
Correct |
2 ms |
6492 KB |
Output is correct |
33 |
Correct |
2 ms |
6588 KB |
Output is correct |
34 |
Correct |
2 ms |
6492 KB |
Output is correct |
35 |
Correct |
2 ms |
6492 KB |
Output is correct |
36 |
Correct |
2 ms |
6492 KB |
Output is correct |
37 |
Correct |
2 ms |
6492 KB |
Output is correct |
38 |
Correct |
4 ms |
7772 KB |
Output is correct |
39 |
Correct |
4 ms |
7772 KB |
Output is correct |
40 |
Correct |
4 ms |
7772 KB |
Output is correct |
41 |
Correct |
4 ms |
7772 KB |
Output is correct |
42 |
Correct |
4 ms |
7772 KB |
Output is correct |
43 |
Correct |
4 ms |
7772 KB |
Output is correct |
44 |
Correct |
4 ms |
7772 KB |
Output is correct |
45 |
Correct |
4 ms |
7772 KB |
Output is correct |
46 |
Correct |
4 ms |
7772 KB |
Output is correct |
47 |
Correct |
4 ms |
7840 KB |
Output is correct |
48 |
Correct |
4 ms |
7772 KB |
Output is correct |
49 |
Correct |
4 ms |
7896 KB |
Output is correct |
50 |
Correct |
4 ms |
7772 KB |
Output is correct |
51 |
Correct |
4 ms |
7772 KB |
Output is correct |
52 |
Correct |
4 ms |
7772 KB |
Output is correct |
53 |
Correct |
3 ms |
7848 KB |
Output is correct |
54 |
Correct |
3 ms |
7772 KB |
Output is correct |
55 |
Correct |
3 ms |
7768 KB |
Output is correct |
56 |
Correct |
3 ms |
7772 KB |
Output is correct |
57 |
Correct |
3 ms |
7772 KB |
Output is correct |
58 |
Correct |
3 ms |
7772 KB |
Output is correct |
59 |
Correct |
3 ms |
7772 KB |
Output is correct |
60 |
Correct |
4 ms |
7772 KB |
Output is correct |
61 |
Correct |
3 ms |
7772 KB |
Output is correct |
62 |
Correct |
3 ms |
7772 KB |
Output is correct |
63 |
Correct |
4 ms |
7852 KB |
Output is correct |
64 |
Correct |
3 ms |
7772 KB |
Output is correct |
65 |
Correct |
4 ms |
7772 KB |
Output is correct |
66 |
Correct |
4 ms |
7772 KB |
Output is correct |
67 |
Correct |
4 ms |
7772 KB |
Output is correct |
68 |
Correct |
4 ms |
7772 KB |
Output is correct |
69 |
Correct |
4 ms |
7772 KB |
Output is correct |
70 |
Correct |
4 ms |
7836 KB |
Output is correct |
71 |
Correct |
3 ms |
7772 KB |
Output is correct |
72 |
Correct |
3 ms |
7772 KB |
Output is correct |
73 |
Correct |
4 ms |
7772 KB |
Output is correct |
74 |
Correct |
3 ms |
7772 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
6492 KB |
Output is correct |
2 |
Correct |
2 ms |
6492 KB |
Output is correct |
3 |
Correct |
2 ms |
6492 KB |
Output is correct |
4 |
Correct |
2 ms |
6744 KB |
Output is correct |
5 |
Correct |
2 ms |
6492 KB |
Output is correct |
6 |
Correct |
2 ms |
6492 KB |
Output is correct |
7 |
Correct |
2 ms |
6492 KB |
Output is correct |
8 |
Correct |
2 ms |
6492 KB |
Output is correct |
9 |
Correct |
2 ms |
6492 KB |
Output is correct |
10 |
Correct |
2 ms |
6488 KB |
Output is correct |
11 |
Correct |
2 ms |
6492 KB |
Output is correct |
12 |
Correct |
2 ms |
6492 KB |
Output is correct |
13 |
Correct |
2 ms |
6492 KB |
Output is correct |
14 |
Correct |
2 ms |
6492 KB |
Output is correct |
15 |
Correct |
2 ms |
6492 KB |
Output is correct |
16 |
Correct |
2 ms |
6492 KB |
Output is correct |
17 |
Correct |
2 ms |
6492 KB |
Output is correct |
18 |
Correct |
2 ms |
6492 KB |
Output is correct |
19 |
Correct |
2 ms |
6492 KB |
Output is correct |
20 |
Correct |
2 ms |
6492 KB |
Output is correct |
21 |
Correct |
2 ms |
6492 KB |
Output is correct |
22 |
Correct |
2 ms |
6492 KB |
Output is correct |
23 |
Correct |
2 ms |
6488 KB |
Output is correct |
24 |
Correct |
2 ms |
6492 KB |
Output is correct |
25 |
Correct |
3 ms |
6488 KB |
Output is correct |
26 |
Correct |
2 ms |
6488 KB |
Output is correct |
27 |
Correct |
2 ms |
6488 KB |
Output is correct |
28 |
Correct |
2 ms |
6492 KB |
Output is correct |
29 |
Correct |
2 ms |
6492 KB |
Output is correct |
30 |
Correct |
2 ms |
6488 KB |
Output is correct |
31 |
Correct |
2 ms |
6492 KB |
Output is correct |
32 |
Correct |
2 ms |
6492 KB |
Output is correct |
33 |
Correct |
2 ms |
6588 KB |
Output is correct |
34 |
Correct |
2 ms |
6492 KB |
Output is correct |
35 |
Correct |
2 ms |
6492 KB |
Output is correct |
36 |
Correct |
2 ms |
6492 KB |
Output is correct |
37 |
Correct |
2 ms |
6492 KB |
Output is correct |
38 |
Correct |
4 ms |
7772 KB |
Output is correct |
39 |
Correct |
4 ms |
7772 KB |
Output is correct |
40 |
Correct |
4 ms |
7772 KB |
Output is correct |
41 |
Correct |
4 ms |
7772 KB |
Output is correct |
42 |
Correct |
4 ms |
7772 KB |
Output is correct |
43 |
Correct |
4 ms |
7772 KB |
Output is correct |
44 |
Correct |
4 ms |
7772 KB |
Output is correct |
45 |
Correct |
4 ms |
7772 KB |
Output is correct |
46 |
Correct |
4 ms |
7772 KB |
Output is correct |
47 |
Correct |
4 ms |
7840 KB |
Output is correct |
48 |
Correct |
4 ms |
7772 KB |
Output is correct |
49 |
Correct |
4 ms |
7896 KB |
Output is correct |
50 |
Correct |
4 ms |
7772 KB |
Output is correct |
51 |
Correct |
4 ms |
7772 KB |
Output is correct |
52 |
Correct |
4 ms |
7772 KB |
Output is correct |
53 |
Correct |
3 ms |
7848 KB |
Output is correct |
54 |
Correct |
3 ms |
7772 KB |
Output is correct |
55 |
Correct |
3 ms |
7768 KB |
Output is correct |
56 |
Correct |
3 ms |
7772 KB |
Output is correct |
57 |
Correct |
3 ms |
7772 KB |
Output is correct |
58 |
Correct |
3 ms |
7772 KB |
Output is correct |
59 |
Correct |
3 ms |
7772 KB |
Output is correct |
60 |
Correct |
4 ms |
7772 KB |
Output is correct |
61 |
Correct |
3 ms |
7772 KB |
Output is correct |
62 |
Correct |
3 ms |
7772 KB |
Output is correct |
63 |
Correct |
4 ms |
7852 KB |
Output is correct |
64 |
Correct |
3 ms |
7772 KB |
Output is correct |
65 |
Correct |
4 ms |
7772 KB |
Output is correct |
66 |
Correct |
4 ms |
7772 KB |
Output is correct |
67 |
Correct |
4 ms |
7772 KB |
Output is correct |
68 |
Correct |
4 ms |
7772 KB |
Output is correct |
69 |
Correct |
4 ms |
7772 KB |
Output is correct |
70 |
Correct |
4 ms |
7836 KB |
Output is correct |
71 |
Correct |
3 ms |
7772 KB |
Output is correct |
72 |
Correct |
3 ms |
7772 KB |
Output is correct |
73 |
Correct |
4 ms |
7772 KB |
Output is correct |
74 |
Correct |
3 ms |
7772 KB |
Output is correct |
75 |
Correct |
789 ms |
194176 KB |
Output is correct |
76 |
Correct |
832 ms |
187924 KB |
Output is correct |
77 |
Correct |
689 ms |
193716 KB |
Output is correct |
78 |
Correct |
735 ms |
196968 KB |
Output is correct |
79 |
Correct |
298 ms |
198240 KB |
Output is correct |
80 |
Correct |
303 ms |
191740 KB |
Output is correct |
81 |
Correct |
570 ms |
194992 KB |
Output is correct |
82 |
Correct |
718 ms |
197652 KB |
Output is correct |
83 |
Correct |
663 ms |
203996 KB |
Output is correct |
84 |
Correct |
667 ms |
203552 KB |
Output is correct |
85 |
Correct |
656 ms |
197264 KB |
Output is correct |
86 |
Correct |
378 ms |
190660 KB |
Output is correct |
87 |
Correct |
429 ms |
187404 KB |
Output is correct |
88 |
Correct |
533 ms |
186872 KB |
Output is correct |
89 |
Correct |
495 ms |
196580 KB |
Output is correct |
90 |
Correct |
392 ms |
205880 KB |
Output is correct |
91 |
Correct |
334 ms |
190656 KB |
Output is correct |
92 |
Correct |
350 ms |
188880 KB |
Output is correct |
93 |
Correct |
351 ms |
197340 KB |
Output is correct |
94 |
Correct |
351 ms |
205468 KB |
Output is correct |
95 |
Correct |
428 ms |
205920 KB |
Output is correct |
96 |
Correct |
377 ms |
191592 KB |
Output is correct |
97 |
Correct |
418 ms |
206500 KB |
Output is correct |
98 |
Correct |
428 ms |
203540 KB |
Output is correct |
99 |
Correct |
428 ms |
203672 KB |
Output is correct |
100 |
Correct |
374 ms |
192932 KB |
Output is correct |
101 |
Correct |
349 ms |
192744 KB |
Output is correct |
102 |
Correct |
721 ms |
192060 KB |
Output is correct |
103 |
Correct |
592 ms |
189204 KB |
Output is correct |
104 |
Correct |
623 ms |
200696 KB |
Output is correct |
105 |
Correct |
495 ms |
199516 KB |
Output is correct |
106 |
Correct |
520 ms |
204880 KB |
Output is correct |
107 |
Correct |
479 ms |
197564 KB |
Output is correct |
108 |
Correct |
651 ms |
195640 KB |
Output is correct |
109 |
Correct |
572 ms |
207952 KB |
Output is correct |
110 |
Correct |
264 ms |
193168 KB |
Output is correct |
111 |
Correct |
316 ms |
195020 KB |
Output is correct |
112 |
Correct |
296 ms |
185644 KB |
Output is correct |
113 |
Correct |
309 ms |
208248 KB |
Output is correct |