# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
243836 |
2020-07-02T01:28:13 Z |
mhy908 |
Cake 3 (JOI19_cake3) |
C++14 |
|
1098 ms |
205672 KB |
#include <bits/stdc++.h>
#define eb emplace_back
#define mp make_pair
#define F first
#define S second
#define svec(x) sort(x.begin(), x.end())
#define press(x) x.erase(unique(x.begin(), x.end()), x.end())
#define lb(x, v) lower_bound(x.begin(), x.end(), v)
using namespace std;
typedef long long LL;
typedef pair<LL, LL> pll;
typedef pair<LL, int> pli;
const LL llinf=4e18;
int n, m;
pll arr[200010];
vector<int> id;
LL ans=-llinf;
struct PST{
struct NODE{
LL qu; int qu2;
NODE *l, *r;
NODE(){qu=0, qu2=0, l=r=nullptr;}
};
NODE* root[200010];
void init(NODE* here, int s, int e){
if(s==e)return;
here->l=new NODE;
here->r=new NODE;
init(here->l, s, (s+e)/2);
init(here->r, (s+e)/2+1, e);
}
PST(){
root[0]=new NODE;
init(root[0], 1, 200000);
}
void in(NODE* lv, NODE* lvpr, int s, int e, int num){
lv->qu=lvpr->qu;
lv->qu2=lvpr->qu2;
if(s==e){
lv->qu+=(LL)id[s-1];
lv->qu2++;
return;
}
if(num<=(s+e)/2){
lv->l=new NODE;
lv->r=lvpr->r;
in(lv->l, lvpr->l, s, (s+e)/2, num);
}
else{
lv->r=new NODE;
lv->l=lvpr->l;
in(lv->r, lvpr->r, (s+e)/2+1, e, num);
}
lv->qu=lv->l->qu+lv->r->qu;
lv->qu2=lv->l->qu2+lv->r->qu2;
}
void in(int lv, int num){
root[lv]=new NODE;
num=lb(id, num)-id.begin()+1;
in(root[lv], root[lv-1], 1, 200000, num);
}
pli query(NODE* fr, NODE* re, int s, int e, int k){
if(re->qu2-fr->qu2<=k)return mp(re->qu-fr->qu, re->qu2-fr->qu2);
if(s==e&&re->qu2-fr->qu2>k)return mp((LL)id[s-1]*k, k);
pli tmp=query(fr->r, re->r, (s+e)/2+1, e, k);
if(tmp.S==k)return tmp;
pli tmp2=query(fr->l, re->l, s, (s+e)/2, k-tmp.S);
return mp(tmp.F+tmp2.F, tmp.S+tmp2.S);
}
LL query(int lv1, int lv2, int k){
pli tmp=query(root[lv1-1], root[lv2], 1, 200000, k);
if(tmp.S<k)return -llinf;
return tmp.F;
}
}pst;
void DNC(int s, int e, int a, int b){
if(s>e)return;
int mid=(s+e)/2, maxnum;
LL maxx=-llinf;
for(int i=max(mid, a); i<=b; i++){
LL tmp=pst.query(mid, i, m);
if(tmp==-llinf)continue;
tmp-=2ll*(arr[i].F-arr[mid].F);
if(maxx<tmp){
maxx=tmp;
maxnum=i;
}
}
ans=max(ans, maxx);
DNC(s, mid-1, a, maxnum);
DNC(mid+1, e, maxnum, b);
}
int main(){
scanf("%d %d", &n, &m);
for(int i=1; i<=n; i++){
scanf("%lld %lld", &arr[i].S, &arr[i].F);
id.eb((int)arr[i].S);
}
svec(id); press(id);
sort(arr+1, arr+n+1);
for(int i=1; i<=n; i++)pst.in(i, (int)arr[i].S);
DNC(1, n-m+1, m, n);
printf("%lld", ans);
}
Compilation message
cake3.cpp: In function 'int main()':
cake3.cpp:98:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &n, &m);
~~~~~^~~~~~~~~~~~~~~~~
cake3.cpp:100:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld %lld", &arr[i].S, &arr[i].F);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
cake3.cpp: In function 'void DNC(int, int, int, int)':
cake3.cpp:93:8: warning: 'maxnum' may be used uninitialized in this function [-Wmaybe-uninitialized]
DNC(s, mid-1, a, maxnum);
~~~^~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
22 ms |
19200 KB |
Output is correct |
2 |
Correct |
24 ms |
19320 KB |
Output is correct |
3 |
Correct |
23 ms |
19200 KB |
Output is correct |
4 |
Correct |
23 ms |
19200 KB |
Output is correct |
5 |
Correct |
23 ms |
19200 KB |
Output is correct |
6 |
Correct |
24 ms |
19200 KB |
Output is correct |
7 |
Correct |
22 ms |
19200 KB |
Output is correct |
8 |
Correct |
22 ms |
19200 KB |
Output is correct |
9 |
Correct |
23 ms |
19196 KB |
Output is correct |
10 |
Correct |
23 ms |
19192 KB |
Output is correct |
11 |
Correct |
25 ms |
19200 KB |
Output is correct |
12 |
Correct |
24 ms |
19200 KB |
Output is correct |
13 |
Correct |
23 ms |
19200 KB |
Output is correct |
14 |
Correct |
22 ms |
19200 KB |
Output is correct |
15 |
Correct |
23 ms |
19200 KB |
Output is correct |
16 |
Correct |
24 ms |
19200 KB |
Output is correct |
17 |
Correct |
25 ms |
19200 KB |
Output is correct |
18 |
Correct |
24 ms |
19200 KB |
Output is correct |
19 |
Correct |
24 ms |
19200 KB |
Output is correct |
20 |
Correct |
23 ms |
19200 KB |
Output is correct |
21 |
Correct |
23 ms |
19200 KB |
Output is correct |
22 |
Correct |
22 ms |
19200 KB |
Output is correct |
23 |
Correct |
23 ms |
19200 KB |
Output is correct |
24 |
Correct |
23 ms |
19192 KB |
Output is correct |
25 |
Correct |
23 ms |
19200 KB |
Output is correct |
26 |
Correct |
23 ms |
19192 KB |
Output is correct |
27 |
Correct |
26 ms |
19200 KB |
Output is correct |
28 |
Correct |
23 ms |
19192 KB |
Output is correct |
29 |
Correct |
23 ms |
19200 KB |
Output is correct |
30 |
Correct |
24 ms |
19192 KB |
Output is correct |
31 |
Correct |
22 ms |
19200 KB |
Output is correct |
32 |
Correct |
23 ms |
19200 KB |
Output is correct |
33 |
Correct |
24 ms |
19200 KB |
Output is correct |
34 |
Correct |
24 ms |
19200 KB |
Output is correct |
35 |
Correct |
23 ms |
19200 KB |
Output is correct |
36 |
Correct |
24 ms |
19192 KB |
Output is correct |
37 |
Correct |
24 ms |
19200 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
22 ms |
19200 KB |
Output is correct |
2 |
Correct |
24 ms |
19320 KB |
Output is correct |
3 |
Correct |
23 ms |
19200 KB |
Output is correct |
4 |
Correct |
23 ms |
19200 KB |
Output is correct |
5 |
Correct |
23 ms |
19200 KB |
Output is correct |
6 |
Correct |
24 ms |
19200 KB |
Output is correct |
7 |
Correct |
22 ms |
19200 KB |
Output is correct |
8 |
Correct |
22 ms |
19200 KB |
Output is correct |
9 |
Correct |
23 ms |
19196 KB |
Output is correct |
10 |
Correct |
23 ms |
19192 KB |
Output is correct |
11 |
Correct |
25 ms |
19200 KB |
Output is correct |
12 |
Correct |
24 ms |
19200 KB |
Output is correct |
13 |
Correct |
23 ms |
19200 KB |
Output is correct |
14 |
Correct |
22 ms |
19200 KB |
Output is correct |
15 |
Correct |
23 ms |
19200 KB |
Output is correct |
16 |
Correct |
24 ms |
19200 KB |
Output is correct |
17 |
Correct |
25 ms |
19200 KB |
Output is correct |
18 |
Correct |
24 ms |
19200 KB |
Output is correct |
19 |
Correct |
24 ms |
19200 KB |
Output is correct |
20 |
Correct |
23 ms |
19200 KB |
Output is correct |
21 |
Correct |
23 ms |
19200 KB |
Output is correct |
22 |
Correct |
22 ms |
19200 KB |
Output is correct |
23 |
Correct |
23 ms |
19200 KB |
Output is correct |
24 |
Correct |
23 ms |
19192 KB |
Output is correct |
25 |
Correct |
23 ms |
19200 KB |
Output is correct |
26 |
Correct |
23 ms |
19192 KB |
Output is correct |
27 |
Correct |
26 ms |
19200 KB |
Output is correct |
28 |
Correct |
23 ms |
19192 KB |
Output is correct |
29 |
Correct |
23 ms |
19200 KB |
Output is correct |
30 |
Correct |
24 ms |
19192 KB |
Output is correct |
31 |
Correct |
22 ms |
19200 KB |
Output is correct |
32 |
Correct |
23 ms |
19200 KB |
Output is correct |
33 |
Correct |
24 ms |
19200 KB |
Output is correct |
34 |
Correct |
24 ms |
19200 KB |
Output is correct |
35 |
Correct |
23 ms |
19200 KB |
Output is correct |
36 |
Correct |
24 ms |
19192 KB |
Output is correct |
37 |
Correct |
24 ms |
19200 KB |
Output is correct |
38 |
Correct |
28 ms |
20864 KB |
Output is correct |
39 |
Correct |
29 ms |
20992 KB |
Output is correct |
40 |
Correct |
28 ms |
20856 KB |
Output is correct |
41 |
Correct |
29 ms |
20864 KB |
Output is correct |
42 |
Correct |
26 ms |
20864 KB |
Output is correct |
43 |
Correct |
26 ms |
20864 KB |
Output is correct |
44 |
Correct |
29 ms |
20864 KB |
Output is correct |
45 |
Correct |
28 ms |
20864 KB |
Output is correct |
46 |
Correct |
29 ms |
20988 KB |
Output is correct |
47 |
Correct |
29 ms |
20864 KB |
Output is correct |
48 |
Correct |
27 ms |
20856 KB |
Output is correct |
49 |
Correct |
29 ms |
20992 KB |
Output is correct |
50 |
Correct |
27 ms |
20864 KB |
Output is correct |
51 |
Correct |
26 ms |
20992 KB |
Output is correct |
52 |
Correct |
27 ms |
20864 KB |
Output is correct |
53 |
Correct |
28 ms |
20864 KB |
Output is correct |
54 |
Correct |
28 ms |
20992 KB |
Output is correct |
55 |
Correct |
26 ms |
20992 KB |
Output is correct |
56 |
Correct |
28 ms |
20864 KB |
Output is correct |
57 |
Correct |
27 ms |
20864 KB |
Output is correct |
58 |
Correct |
26 ms |
20864 KB |
Output is correct |
59 |
Correct |
26 ms |
20856 KB |
Output is correct |
60 |
Correct |
27 ms |
20864 KB |
Output is correct |
61 |
Correct |
28 ms |
20984 KB |
Output is correct |
62 |
Correct |
29 ms |
20992 KB |
Output is correct |
63 |
Correct |
27 ms |
20992 KB |
Output is correct |
64 |
Correct |
26 ms |
20992 KB |
Output is correct |
65 |
Correct |
29 ms |
20864 KB |
Output is correct |
66 |
Correct |
28 ms |
20984 KB |
Output is correct |
67 |
Correct |
29 ms |
20864 KB |
Output is correct |
68 |
Correct |
28 ms |
20992 KB |
Output is correct |
69 |
Correct |
28 ms |
20864 KB |
Output is correct |
70 |
Correct |
28 ms |
20864 KB |
Output is correct |
71 |
Correct |
26 ms |
20864 KB |
Output is correct |
72 |
Correct |
27 ms |
20992 KB |
Output is correct |
73 |
Correct |
28 ms |
20864 KB |
Output is correct |
74 |
Correct |
25 ms |
20992 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
22 ms |
19200 KB |
Output is correct |
2 |
Correct |
24 ms |
19320 KB |
Output is correct |
3 |
Correct |
23 ms |
19200 KB |
Output is correct |
4 |
Correct |
23 ms |
19200 KB |
Output is correct |
5 |
Correct |
23 ms |
19200 KB |
Output is correct |
6 |
Correct |
24 ms |
19200 KB |
Output is correct |
7 |
Correct |
22 ms |
19200 KB |
Output is correct |
8 |
Correct |
22 ms |
19200 KB |
Output is correct |
9 |
Correct |
23 ms |
19196 KB |
Output is correct |
10 |
Correct |
23 ms |
19192 KB |
Output is correct |
11 |
Correct |
25 ms |
19200 KB |
Output is correct |
12 |
Correct |
24 ms |
19200 KB |
Output is correct |
13 |
Correct |
23 ms |
19200 KB |
Output is correct |
14 |
Correct |
22 ms |
19200 KB |
Output is correct |
15 |
Correct |
23 ms |
19200 KB |
Output is correct |
16 |
Correct |
24 ms |
19200 KB |
Output is correct |
17 |
Correct |
25 ms |
19200 KB |
Output is correct |
18 |
Correct |
24 ms |
19200 KB |
Output is correct |
19 |
Correct |
24 ms |
19200 KB |
Output is correct |
20 |
Correct |
23 ms |
19200 KB |
Output is correct |
21 |
Correct |
23 ms |
19200 KB |
Output is correct |
22 |
Correct |
22 ms |
19200 KB |
Output is correct |
23 |
Correct |
23 ms |
19200 KB |
Output is correct |
24 |
Correct |
23 ms |
19192 KB |
Output is correct |
25 |
Correct |
23 ms |
19200 KB |
Output is correct |
26 |
Correct |
23 ms |
19192 KB |
Output is correct |
27 |
Correct |
26 ms |
19200 KB |
Output is correct |
28 |
Correct |
23 ms |
19192 KB |
Output is correct |
29 |
Correct |
23 ms |
19200 KB |
Output is correct |
30 |
Correct |
24 ms |
19192 KB |
Output is correct |
31 |
Correct |
22 ms |
19200 KB |
Output is correct |
32 |
Correct |
23 ms |
19200 KB |
Output is correct |
33 |
Correct |
24 ms |
19200 KB |
Output is correct |
34 |
Correct |
24 ms |
19200 KB |
Output is correct |
35 |
Correct |
23 ms |
19200 KB |
Output is correct |
36 |
Correct |
24 ms |
19192 KB |
Output is correct |
37 |
Correct |
24 ms |
19200 KB |
Output is correct |
38 |
Correct |
28 ms |
20864 KB |
Output is correct |
39 |
Correct |
29 ms |
20992 KB |
Output is correct |
40 |
Correct |
28 ms |
20856 KB |
Output is correct |
41 |
Correct |
29 ms |
20864 KB |
Output is correct |
42 |
Correct |
26 ms |
20864 KB |
Output is correct |
43 |
Correct |
26 ms |
20864 KB |
Output is correct |
44 |
Correct |
29 ms |
20864 KB |
Output is correct |
45 |
Correct |
28 ms |
20864 KB |
Output is correct |
46 |
Correct |
29 ms |
20988 KB |
Output is correct |
47 |
Correct |
29 ms |
20864 KB |
Output is correct |
48 |
Correct |
27 ms |
20856 KB |
Output is correct |
49 |
Correct |
29 ms |
20992 KB |
Output is correct |
50 |
Correct |
27 ms |
20864 KB |
Output is correct |
51 |
Correct |
26 ms |
20992 KB |
Output is correct |
52 |
Correct |
27 ms |
20864 KB |
Output is correct |
53 |
Correct |
28 ms |
20864 KB |
Output is correct |
54 |
Correct |
28 ms |
20992 KB |
Output is correct |
55 |
Correct |
26 ms |
20992 KB |
Output is correct |
56 |
Correct |
28 ms |
20864 KB |
Output is correct |
57 |
Correct |
27 ms |
20864 KB |
Output is correct |
58 |
Correct |
26 ms |
20864 KB |
Output is correct |
59 |
Correct |
26 ms |
20856 KB |
Output is correct |
60 |
Correct |
27 ms |
20864 KB |
Output is correct |
61 |
Correct |
28 ms |
20984 KB |
Output is correct |
62 |
Correct |
29 ms |
20992 KB |
Output is correct |
63 |
Correct |
27 ms |
20992 KB |
Output is correct |
64 |
Correct |
26 ms |
20992 KB |
Output is correct |
65 |
Correct |
29 ms |
20864 KB |
Output is correct |
66 |
Correct |
28 ms |
20984 KB |
Output is correct |
67 |
Correct |
29 ms |
20864 KB |
Output is correct |
68 |
Correct |
28 ms |
20992 KB |
Output is correct |
69 |
Correct |
28 ms |
20864 KB |
Output is correct |
70 |
Correct |
28 ms |
20864 KB |
Output is correct |
71 |
Correct |
26 ms |
20864 KB |
Output is correct |
72 |
Correct |
27 ms |
20992 KB |
Output is correct |
73 |
Correct |
28 ms |
20864 KB |
Output is correct |
74 |
Correct |
25 ms |
20992 KB |
Output is correct |
75 |
Correct |
1053 ms |
191348 KB |
Output is correct |
76 |
Correct |
1098 ms |
186708 KB |
Output is correct |
77 |
Correct |
966 ms |
191720 KB |
Output is correct |
78 |
Correct |
1004 ms |
194412 KB |
Output is correct |
79 |
Correct |
470 ms |
195048 KB |
Output is correct |
80 |
Correct |
523 ms |
190108 KB |
Output is correct |
81 |
Correct |
768 ms |
192616 KB |
Output is correct |
82 |
Correct |
961 ms |
195048 KB |
Output is correct |
83 |
Correct |
868 ms |
200680 KB |
Output is correct |
84 |
Correct |
940 ms |
200300 KB |
Output is correct |
85 |
Correct |
769 ms |
194280 KB |
Output is correct |
86 |
Correct |
521 ms |
188136 KB |
Output is correct |
87 |
Correct |
554 ms |
186088 KB |
Output is correct |
88 |
Correct |
707 ms |
184980 KB |
Output is correct |
89 |
Correct |
665 ms |
194160 KB |
Output is correct |
90 |
Correct |
560 ms |
202092 KB |
Output is correct |
91 |
Correct |
455 ms |
188392 KB |
Output is correct |
92 |
Correct |
452 ms |
187112 KB |
Output is correct |
93 |
Correct |
492 ms |
194280 KB |
Output is correct |
94 |
Correct |
457 ms |
201960 KB |
Output is correct |
95 |
Correct |
547 ms |
202216 KB |
Output is correct |
96 |
Correct |
414 ms |
191980 KB |
Output is correct |
97 |
Correct |
451 ms |
205672 KB |
Output is correct |
98 |
Correct |
424 ms |
202732 KB |
Output is correct |
99 |
Correct |
410 ms |
203244 KB |
Output is correct |
100 |
Correct |
364 ms |
192744 KB |
Output is correct |
101 |
Correct |
369 ms |
192876 KB |
Output is correct |
102 |
Correct |
760 ms |
190312 KB |
Output is correct |
103 |
Correct |
738 ms |
187756 KB |
Output is correct |
104 |
Correct |
848 ms |
196968 KB |
Output is correct |
105 |
Correct |
652 ms |
196588 KB |
Output is correct |
106 |
Correct |
670 ms |
200936 KB |
Output is correct |
107 |
Correct |
553 ms |
194664 KB |
Output is correct |
108 |
Correct |
947 ms |
193644 KB |
Output is correct |
109 |
Correct |
874 ms |
203756 KB |
Output is correct |
110 |
Correct |
382 ms |
191720 KB |
Output is correct |
111 |
Correct |
454 ms |
193516 KB |
Output is correct |
112 |
Correct |
783 ms |
184812 KB |
Output is correct |
113 |
Correct |
527 ms |
204136 KB |
Output is correct |