# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
379031 |
2021-03-17T08:41:01 Z |
leinad2 |
Cake 3 (JOI19_cake3) |
C++17 |
|
1397 ms |
124268 KB |
#include<bits/stdc++.h>
using namespace std;
struct node
{
int l, r, v;
long long sum;
}nd;
node pst[5000010];
pair<int, int>A[200010];
map<int, int>x, y;
map<int, int>::iterator it;
int t, n, q, a, b, c, d, i, j, sz, m, rt, cnt, root[200010], opt[200010], X[200010], Y[200010];
long long dap=-1e18;
void make_node(){pst[sz++]={-1, -1, 0, 0};}
void init(int id, int s, int e)
{
if(s==e)return;
int m=s+e>>1;
if(pst[id].l==-1)
{
pst[id].l=sz;
make_node();
}
init(pst[id].l, s, m);
if(pst[id].r==-1)
{
pst[id].r=sz;
make_node();
}
init(pst[id].r, m+1, e);
}
void update(int prev, int id, int s, int e, int x)
{
pst[id].v=pst[prev].v+1;
pst[id].sum=pst[prev].sum+Y[x];
if(s==e)return;
int m=s+e>>1;
if(x<=m)
{
pst[id].l=sz;
make_node();
pst[id].r=pst[prev].r;
update(pst[prev].l, pst[id].l, s, m, x);
}
else
{
pst[id].r=sz;
make_node();
pst[id].l=pst[prev].l;
update(pst[prev].r, pst[id].r, m+1, e, x);
}
}
long long get(int prev, int id, int s, int e, int k)
{
if(s==e)return min(k, (int)(pst[id].sum-pst[prev].sum)/Y[s])*Y[s];
long long d=pst[pst[id].r].sum-pst[pst[prev].r].sum;
int ee=pst[pst[id].r].v-pst[pst[prev].r].v;
int m=s+e>>1;
if(k<=ee)return get(pst[prev].r, pst[id].r, m+1, e, k);
else return d+get(pst[prev].l, pst[id].l, s, m, k-ee);
}
void dnc(int s, int e, int l, int r)
{
if(s>e)return;
int mid=s+e>>1;
long long ans=-1e18;
int pos;
for(int i=max(l, mid+m-1);i<=r;i++)
{
long long res=get(root[mid], root[i-1], 1, cnt, m-2)+Y[A[mid].second]+Y[A[i].second]-(X[A[i].first]-X[A[mid].first]);
if(ans<res)
{
ans=res;
pos=i;
}
}
dap=max(dap, ans);
opt[mid]=pos;
dnc(s, mid-1, l, pos);
dnc(mid+1, e, pos, r);
}
main()
{
for(scanf("%d %d", &n, &m);i++<n;)
{
scanf("%d %d", &b, &a);
a*=2;
A[i].first=a,A[i].second=b;
x[a]++;y[b]++;
}
sort(A+1, A+n+1);
for(it=x.begin();it!=x.end();it++)it->second=++cnt,X[cnt]=it->first;cnt=0;
for(it=y.begin();it!=y.end();it++)it->second=++cnt,Y[cnt]=it->first;
make_node();
init(0, 1, cnt);
for(i=0;i++<n;)
{
A[i].first=x[A[i].first];
A[i].second=y[A[i].second];
root[i]=sz;
make_node();
update(root[i-1], root[i], 1, cnt, A[i].second);
}
dnc(1, n-m+1, 1, n);
cout<<dap;
}
Compilation message
cake3.cpp: In function 'void init(int, int, int)':
cake3.cpp:18:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
18 | int m=s+e>>1;
| ~^~
cake3.cpp: In function 'void update(int, int, int, int, int)':
cake3.cpp:37:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
37 | int m=s+e>>1;
| ~^~
cake3.cpp: In function 'long long int get(int, int, int, int, int)':
cake3.cpp:58:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
58 | int m=s+e>>1;
| ~^~
cake3.cpp: In function 'void dnc(int, int, int, int)':
cake3.cpp:65:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
65 | int mid=s+e>>1;
| ~^~
cake3.cpp: At global scope:
cake3.cpp:82:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
82 | main()
| ^
cake3.cpp: In function 'int main()':
cake3.cpp:92:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
92 | for(it=x.begin();it!=x.end();it++)it->second=++cnt,X[cnt]=it->first;cnt=0;
| ^~~
cake3.cpp:92:73: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
92 | for(it=x.begin();it!=x.end();it++)it->second=++cnt,X[cnt]=it->first;cnt=0;
| ^~~
cake3.cpp:84:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
84 | for(scanf("%d %d", &n, &m);i++<n;)
| ~~~~~^~~~~~~~~~~~~~~~~
cake3.cpp:86:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
86 | scanf("%d %d", &b, &a);
| ~~~~~^~~~~~~~~~~~~~~~~
cake3.cpp: In function 'void dnc(int, int, int, int)':
cake3.cpp:79:8: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
79 | dnc(s, mid-1, l, pos);
| ~~~^~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
1 ms |
364 KB |
Output is correct |
10 |
Correct |
1 ms |
364 KB |
Output is correct |
11 |
Correct |
1 ms |
504 KB |
Output is correct |
12 |
Correct |
1 ms |
364 KB |
Output is correct |
13 |
Correct |
1 ms |
364 KB |
Output is correct |
14 |
Correct |
1 ms |
364 KB |
Output is correct |
15 |
Correct |
1 ms |
364 KB |
Output is correct |
16 |
Correct |
1 ms |
364 KB |
Output is correct |
17 |
Correct |
1 ms |
364 KB |
Output is correct |
18 |
Correct |
1 ms |
364 KB |
Output is correct |
19 |
Correct |
1 ms |
364 KB |
Output is correct |
20 |
Correct |
1 ms |
364 KB |
Output is correct |
21 |
Correct |
1 ms |
364 KB |
Output is correct |
22 |
Correct |
1 ms |
364 KB |
Output is correct |
23 |
Correct |
1 ms |
364 KB |
Output is correct |
24 |
Correct |
1 ms |
364 KB |
Output is correct |
25 |
Correct |
1 ms |
364 KB |
Output is correct |
26 |
Correct |
1 ms |
364 KB |
Output is correct |
27 |
Correct |
1 ms |
364 KB |
Output is correct |
28 |
Correct |
1 ms |
364 KB |
Output is correct |
29 |
Correct |
1 ms |
364 KB |
Output is correct |
30 |
Correct |
1 ms |
364 KB |
Output is correct |
31 |
Correct |
1 ms |
364 KB |
Output is correct |
32 |
Correct |
1 ms |
364 KB |
Output is correct |
33 |
Correct |
1 ms |
364 KB |
Output is correct |
34 |
Correct |
1 ms |
384 KB |
Output is correct |
35 |
Correct |
1 ms |
364 KB |
Output is correct |
36 |
Correct |
1 ms |
364 KB |
Output is correct |
37 |
Correct |
1 ms |
364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
1 ms |
364 KB |
Output is correct |
10 |
Correct |
1 ms |
364 KB |
Output is correct |
11 |
Correct |
1 ms |
504 KB |
Output is correct |
12 |
Correct |
1 ms |
364 KB |
Output is correct |
13 |
Correct |
1 ms |
364 KB |
Output is correct |
14 |
Correct |
1 ms |
364 KB |
Output is correct |
15 |
Correct |
1 ms |
364 KB |
Output is correct |
16 |
Correct |
1 ms |
364 KB |
Output is correct |
17 |
Correct |
1 ms |
364 KB |
Output is correct |
18 |
Correct |
1 ms |
364 KB |
Output is correct |
19 |
Correct |
1 ms |
364 KB |
Output is correct |
20 |
Correct |
1 ms |
364 KB |
Output is correct |
21 |
Correct |
1 ms |
364 KB |
Output is correct |
22 |
Correct |
1 ms |
364 KB |
Output is correct |
23 |
Correct |
1 ms |
364 KB |
Output is correct |
24 |
Correct |
1 ms |
364 KB |
Output is correct |
25 |
Correct |
1 ms |
364 KB |
Output is correct |
26 |
Correct |
1 ms |
364 KB |
Output is correct |
27 |
Correct |
1 ms |
364 KB |
Output is correct |
28 |
Correct |
1 ms |
364 KB |
Output is correct |
29 |
Correct |
1 ms |
364 KB |
Output is correct |
30 |
Correct |
1 ms |
364 KB |
Output is correct |
31 |
Correct |
1 ms |
364 KB |
Output is correct |
32 |
Correct |
1 ms |
364 KB |
Output is correct |
33 |
Correct |
1 ms |
364 KB |
Output is correct |
34 |
Correct |
1 ms |
384 KB |
Output is correct |
35 |
Correct |
1 ms |
364 KB |
Output is correct |
36 |
Correct |
1 ms |
364 KB |
Output is correct |
37 |
Correct |
1 ms |
364 KB |
Output is correct |
38 |
Correct |
5 ms |
1260 KB |
Output is correct |
39 |
Correct |
5 ms |
1260 KB |
Output is correct |
40 |
Correct |
4 ms |
1260 KB |
Output is correct |
41 |
Correct |
4 ms |
1260 KB |
Output is correct |
42 |
Correct |
4 ms |
1388 KB |
Output is correct |
43 |
Correct |
4 ms |
1132 KB |
Output is correct |
44 |
Correct |
4 ms |
1132 KB |
Output is correct |
45 |
Correct |
4 ms |
1260 KB |
Output is correct |
46 |
Correct |
4 ms |
1260 KB |
Output is correct |
47 |
Correct |
4 ms |
1260 KB |
Output is correct |
48 |
Correct |
4 ms |
1132 KB |
Output is correct |
49 |
Correct |
4 ms |
1260 KB |
Output is correct |
50 |
Correct |
4 ms |
1260 KB |
Output is correct |
51 |
Correct |
4 ms |
1260 KB |
Output is correct |
52 |
Correct |
4 ms |
1260 KB |
Output is correct |
53 |
Correct |
4 ms |
1260 KB |
Output is correct |
54 |
Correct |
4 ms |
1260 KB |
Output is correct |
55 |
Correct |
4 ms |
1260 KB |
Output is correct |
56 |
Correct |
3 ms |
1260 KB |
Output is correct |
57 |
Correct |
3 ms |
1260 KB |
Output is correct |
58 |
Correct |
3 ms |
1260 KB |
Output is correct |
59 |
Correct |
2 ms |
492 KB |
Output is correct |
60 |
Correct |
2 ms |
492 KB |
Output is correct |
61 |
Correct |
1 ms |
492 KB |
Output is correct |
62 |
Correct |
2 ms |
620 KB |
Output is correct |
63 |
Correct |
2 ms |
492 KB |
Output is correct |
64 |
Correct |
1 ms |
492 KB |
Output is correct |
65 |
Correct |
4 ms |
1260 KB |
Output is correct |
66 |
Correct |
4 ms |
1132 KB |
Output is correct |
67 |
Correct |
4 ms |
1260 KB |
Output is correct |
68 |
Correct |
4 ms |
1260 KB |
Output is correct |
69 |
Correct |
4 ms |
1132 KB |
Output is correct |
70 |
Correct |
5 ms |
1260 KB |
Output is correct |
71 |
Correct |
2 ms |
748 KB |
Output is correct |
72 |
Correct |
2 ms |
748 KB |
Output is correct |
73 |
Correct |
4 ms |
1132 KB |
Output is correct |
74 |
Correct |
3 ms |
1260 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
1 ms |
364 KB |
Output is correct |
10 |
Correct |
1 ms |
364 KB |
Output is correct |
11 |
Correct |
1 ms |
504 KB |
Output is correct |
12 |
Correct |
1 ms |
364 KB |
Output is correct |
13 |
Correct |
1 ms |
364 KB |
Output is correct |
14 |
Correct |
1 ms |
364 KB |
Output is correct |
15 |
Correct |
1 ms |
364 KB |
Output is correct |
16 |
Correct |
1 ms |
364 KB |
Output is correct |
17 |
Correct |
1 ms |
364 KB |
Output is correct |
18 |
Correct |
1 ms |
364 KB |
Output is correct |
19 |
Correct |
1 ms |
364 KB |
Output is correct |
20 |
Correct |
1 ms |
364 KB |
Output is correct |
21 |
Correct |
1 ms |
364 KB |
Output is correct |
22 |
Correct |
1 ms |
364 KB |
Output is correct |
23 |
Correct |
1 ms |
364 KB |
Output is correct |
24 |
Correct |
1 ms |
364 KB |
Output is correct |
25 |
Correct |
1 ms |
364 KB |
Output is correct |
26 |
Correct |
1 ms |
364 KB |
Output is correct |
27 |
Correct |
1 ms |
364 KB |
Output is correct |
28 |
Correct |
1 ms |
364 KB |
Output is correct |
29 |
Correct |
1 ms |
364 KB |
Output is correct |
30 |
Correct |
1 ms |
364 KB |
Output is correct |
31 |
Correct |
1 ms |
364 KB |
Output is correct |
32 |
Correct |
1 ms |
364 KB |
Output is correct |
33 |
Correct |
1 ms |
364 KB |
Output is correct |
34 |
Correct |
1 ms |
384 KB |
Output is correct |
35 |
Correct |
1 ms |
364 KB |
Output is correct |
36 |
Correct |
1 ms |
364 KB |
Output is correct |
37 |
Correct |
1 ms |
364 KB |
Output is correct |
38 |
Correct |
5 ms |
1260 KB |
Output is correct |
39 |
Correct |
5 ms |
1260 KB |
Output is correct |
40 |
Correct |
4 ms |
1260 KB |
Output is correct |
41 |
Correct |
4 ms |
1260 KB |
Output is correct |
42 |
Correct |
4 ms |
1388 KB |
Output is correct |
43 |
Correct |
4 ms |
1132 KB |
Output is correct |
44 |
Correct |
4 ms |
1132 KB |
Output is correct |
45 |
Correct |
4 ms |
1260 KB |
Output is correct |
46 |
Correct |
4 ms |
1260 KB |
Output is correct |
47 |
Correct |
4 ms |
1260 KB |
Output is correct |
48 |
Correct |
4 ms |
1132 KB |
Output is correct |
49 |
Correct |
4 ms |
1260 KB |
Output is correct |
50 |
Correct |
4 ms |
1260 KB |
Output is correct |
51 |
Correct |
4 ms |
1260 KB |
Output is correct |
52 |
Correct |
4 ms |
1260 KB |
Output is correct |
53 |
Correct |
4 ms |
1260 KB |
Output is correct |
54 |
Correct |
4 ms |
1260 KB |
Output is correct |
55 |
Correct |
4 ms |
1260 KB |
Output is correct |
56 |
Correct |
3 ms |
1260 KB |
Output is correct |
57 |
Correct |
3 ms |
1260 KB |
Output is correct |
58 |
Correct |
3 ms |
1260 KB |
Output is correct |
59 |
Correct |
2 ms |
492 KB |
Output is correct |
60 |
Correct |
2 ms |
492 KB |
Output is correct |
61 |
Correct |
1 ms |
492 KB |
Output is correct |
62 |
Correct |
2 ms |
620 KB |
Output is correct |
63 |
Correct |
2 ms |
492 KB |
Output is correct |
64 |
Correct |
1 ms |
492 KB |
Output is correct |
65 |
Correct |
4 ms |
1260 KB |
Output is correct |
66 |
Correct |
4 ms |
1132 KB |
Output is correct |
67 |
Correct |
4 ms |
1260 KB |
Output is correct |
68 |
Correct |
4 ms |
1260 KB |
Output is correct |
69 |
Correct |
4 ms |
1132 KB |
Output is correct |
70 |
Correct |
5 ms |
1260 KB |
Output is correct |
71 |
Correct |
2 ms |
748 KB |
Output is correct |
72 |
Correct |
2 ms |
748 KB |
Output is correct |
73 |
Correct |
4 ms |
1132 KB |
Output is correct |
74 |
Correct |
3 ms |
1260 KB |
Output is correct |
75 |
Correct |
1353 ms |
112876 KB |
Output is correct |
76 |
Correct |
1353 ms |
112732 KB |
Output is correct |
77 |
Correct |
1243 ms |
115880 KB |
Output is correct |
78 |
Correct |
1397 ms |
117868 KB |
Output is correct |
79 |
Correct |
887 ms |
117740 KB |
Output is correct |
80 |
Correct |
928 ms |
114184 KB |
Output is correct |
81 |
Correct |
753 ms |
88228 KB |
Output is correct |
82 |
Correct |
1028 ms |
94764 KB |
Output is correct |
83 |
Correct |
853 ms |
93364 KB |
Output is correct |
84 |
Correct |
944 ms |
94188 KB |
Output is correct |
85 |
Correct |
810 ms |
88940 KB |
Output is correct |
86 |
Correct |
554 ms |
82668 KB |
Output is correct |
87 |
Correct |
558 ms |
82284 KB |
Output is correct |
88 |
Correct |
754 ms |
84076 KB |
Output is correct |
89 |
Correct |
690 ms |
87192 KB |
Output is correct |
90 |
Correct |
577 ms |
88320 KB |
Output is correct |
91 |
Correct |
511 ms |
80736 KB |
Output is correct |
92 |
Correct |
479 ms |
80236 KB |
Output is correct |
93 |
Correct |
526 ms |
84204 KB |
Output is correct |
94 |
Correct |
507 ms |
85816 KB |
Output is correct |
95 |
Correct |
631 ms |
87916 KB |
Output is correct |
96 |
Correct |
81 ms |
10092 KB |
Output is correct |
97 |
Correct |
87 ms |
10860 KB |
Output is correct |
98 |
Correct |
86 ms |
10732 KB |
Output is correct |
99 |
Correct |
84 ms |
10620 KB |
Output is correct |
100 |
Correct |
78 ms |
9940 KB |
Output is correct |
101 |
Correct |
80 ms |
9964 KB |
Output is correct |
102 |
Correct |
382 ms |
62964 KB |
Output is correct |
103 |
Correct |
369 ms |
61932 KB |
Output is correct |
104 |
Correct |
419 ms |
66796 KB |
Output is correct |
105 |
Correct |
321 ms |
62188 KB |
Output is correct |
106 |
Correct |
329 ms |
63468 KB |
Output is correct |
107 |
Correct |
296 ms |
60268 KB |
Output is correct |
108 |
Correct |
1271 ms |
116972 KB |
Output is correct |
109 |
Correct |
1229 ms |
124268 KB |
Output is correct |
110 |
Correct |
181 ms |
34028 KB |
Output is correct |
111 |
Correct |
181 ms |
34540 KB |
Output is correct |
112 |
Correct |
760 ms |
101484 KB |
Output is correct |
113 |
Correct |
892 ms |
124268 KB |
Output is correct |