#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define ii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define INF 100000000000000000ll
#define modulo 1000000007
#define mod 998244353
//#define int long long int
using namespace std;
struct Node{
int left, right;
long long int sum;
int cnt;
void set(int a, int b, int c, int d, long long int e, int f){
left = a;
right = b;
sum = e;
cnt = f;
}
Node(){}
};
Node seg[8000000];
vector<int> root(200005);
vector<ii> arr;
vector<ii> util;
vector<int> ptr(200005);
int ind = 0;
int S;
int new_node(){
return ind++;
}
long long int getsum(int i, int j){
return seg[j].sum - seg[i].sum;
}
int getcnt(int i, int j){
return seg[j].cnt - seg[i].cnt;
}
void build(int curr, int l, int r){
if(r == l){
seg[curr].set(-1, -1, l, r, 0, 0);
return;
}
seg[curr].set(new_node(), new_node(), l, r, 0, 0);
build(seg[curr].left, l, (l + r) / 2);
build(seg[curr].right, (l + r) / 2 + 1, r);
}
int pers(int j, int l, int r, int x){
int curr = new_node();
if(l != r){
int mid = (l + r) / 2;
int q, w;
if(x <= mid) {
q = pers(seg[j].left ,l, mid, x);
w = seg[j].right;
}
else{
q = seg[j].left;
w = pers(seg[j].right ,mid + 1, r, x);
}
seg[curr].set(q, w, l, r, seg[q].sum + seg[w].sum, seg[q].cnt + seg[w].cnt);
}
else{
seg[curr].set(-1, -1, l, r, util[l].first, 1);
}
return curr;
}
long long int query(int j1, int l, int r, int x, int j2){
if(getcnt(j1, j2) == 0 || x == 0)return 0;
if(l == r) return getsum(j1, j2);
int q = seg[j1].left;
int w = seg[j1].right;
int Q = seg[j2].left;
int W = seg[j2].right;
if(x == getcnt(j1, j2)){
return getsum(j1, j2);
}
if(x <= getcnt(q, Q)){
return query(q, l, (l + r) / 2, x, Q);
}
return getsum(q, Q) + query(w, (l + r) / 2 + 1, r, max(x - getcnt(q, Q), 0), W);
}
void print(int j, int l, int r){
cout << "("<<l<<","<<r<<") = "<< seg[j].sum << " " << seg[j].cnt << "\n";
if(l == r){
return;
}
print(seg[j].left, l, (l + r) / 2);
print(seg[j].right, (l + r) / 2 + 1, r);
}
long long int compute(int l, int r, int optl, int optr, int m){
if(l > r) return -INF;
int mid = (l + r) / 2;
long long int w = -INF;
int opt = optl;
for(int k = optl; k <= min(optr, mid); k++){
long long int q = -INF;
if(mid - k + 1 >= m){
q = query((k > 0 ? root[k - 1] : 0), 0, S - 1, m - 1, root[mid - 1]) - 2ll * (arr[mid].first - arr[k].first) + 1ll * arr[mid].second;
}
if(q > w){
w = q;
opt = k;
}
}
return max(w, max(compute(l, mid - 1, optl, opt, m), compute(mid + 1, r, opt, optr, m)));
}
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, m;
cin >> n >> m;
for(int i = 0; i < n; i++){
int x, y;
cin >> x >> y;
arr.pb({y, x});
}
sort(all(arr));
for(int i = 0; i < n; i++){
util.pb({arr[i].second, i});
}
sort(all(util), greater<ii>());
for(int i = 0; i < n; i++) ptr[util[i].second] = i;
S = (1 << (int)ceil(log2(n)));
build(new_node(), 0, S - 1);
for(int i = 0; i < n; i++){
root[i] = pers((i > 0 ? root[i - 1] : 0), 0, S - 1, ptr[i]);
}
cout << compute(0, n - 1, 0, n - 1, m);
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
1912 KB |
Output is correct |
2 |
Correct |
6 ms |
1912 KB |
Output is correct |
3 |
Correct |
6 ms |
1912 KB |
Output is correct |
4 |
Correct |
6 ms |
1912 KB |
Output is correct |
5 |
Correct |
5 ms |
1912 KB |
Output is correct |
6 |
Correct |
6 ms |
1912 KB |
Output is correct |
7 |
Correct |
6 ms |
1912 KB |
Output is correct |
8 |
Correct |
6 ms |
1912 KB |
Output is correct |
9 |
Correct |
6 ms |
1912 KB |
Output is correct |
10 |
Correct |
5 ms |
1912 KB |
Output is correct |
11 |
Correct |
6 ms |
1916 KB |
Output is correct |
12 |
Correct |
6 ms |
1912 KB |
Output is correct |
13 |
Correct |
5 ms |
1912 KB |
Output is correct |
14 |
Correct |
5 ms |
1912 KB |
Output is correct |
15 |
Correct |
6 ms |
1912 KB |
Output is correct |
16 |
Correct |
6 ms |
1912 KB |
Output is correct |
17 |
Correct |
6 ms |
1912 KB |
Output is correct |
18 |
Correct |
6 ms |
1912 KB |
Output is correct |
19 |
Correct |
6 ms |
1916 KB |
Output is correct |
20 |
Correct |
6 ms |
1912 KB |
Output is correct |
21 |
Correct |
5 ms |
1912 KB |
Output is correct |
22 |
Correct |
6 ms |
1912 KB |
Output is correct |
23 |
Correct |
6 ms |
1912 KB |
Output is correct |
24 |
Correct |
6 ms |
1912 KB |
Output is correct |
25 |
Correct |
6 ms |
1912 KB |
Output is correct |
26 |
Correct |
6 ms |
1912 KB |
Output is correct |
27 |
Correct |
6 ms |
1912 KB |
Output is correct |
28 |
Correct |
5 ms |
1912 KB |
Output is correct |
29 |
Correct |
6 ms |
1912 KB |
Output is correct |
30 |
Correct |
6 ms |
1912 KB |
Output is correct |
31 |
Correct |
6 ms |
1916 KB |
Output is correct |
32 |
Correct |
5 ms |
1916 KB |
Output is correct |
33 |
Correct |
6 ms |
1912 KB |
Output is correct |
34 |
Correct |
6 ms |
1912 KB |
Output is correct |
35 |
Correct |
6 ms |
1912 KB |
Output is correct |
36 |
Correct |
6 ms |
1912 KB |
Output is correct |
37 |
Correct |
6 ms |
1912 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
1912 KB |
Output is correct |
2 |
Correct |
6 ms |
1912 KB |
Output is correct |
3 |
Correct |
6 ms |
1912 KB |
Output is correct |
4 |
Correct |
6 ms |
1912 KB |
Output is correct |
5 |
Correct |
5 ms |
1912 KB |
Output is correct |
6 |
Correct |
6 ms |
1912 KB |
Output is correct |
7 |
Correct |
6 ms |
1912 KB |
Output is correct |
8 |
Correct |
6 ms |
1912 KB |
Output is correct |
9 |
Correct |
6 ms |
1912 KB |
Output is correct |
10 |
Correct |
5 ms |
1912 KB |
Output is correct |
11 |
Correct |
6 ms |
1916 KB |
Output is correct |
12 |
Correct |
6 ms |
1912 KB |
Output is correct |
13 |
Correct |
5 ms |
1912 KB |
Output is correct |
14 |
Correct |
5 ms |
1912 KB |
Output is correct |
15 |
Correct |
6 ms |
1912 KB |
Output is correct |
16 |
Correct |
6 ms |
1912 KB |
Output is correct |
17 |
Correct |
6 ms |
1912 KB |
Output is correct |
18 |
Correct |
6 ms |
1912 KB |
Output is correct |
19 |
Correct |
6 ms |
1916 KB |
Output is correct |
20 |
Correct |
6 ms |
1912 KB |
Output is correct |
21 |
Correct |
5 ms |
1912 KB |
Output is correct |
22 |
Correct |
6 ms |
1912 KB |
Output is correct |
23 |
Correct |
6 ms |
1912 KB |
Output is correct |
24 |
Correct |
6 ms |
1912 KB |
Output is correct |
25 |
Correct |
6 ms |
1912 KB |
Output is correct |
26 |
Correct |
6 ms |
1912 KB |
Output is correct |
27 |
Correct |
6 ms |
1912 KB |
Output is correct |
28 |
Correct |
5 ms |
1912 KB |
Output is correct |
29 |
Correct |
6 ms |
1912 KB |
Output is correct |
30 |
Correct |
6 ms |
1912 KB |
Output is correct |
31 |
Correct |
6 ms |
1916 KB |
Output is correct |
32 |
Correct |
5 ms |
1916 KB |
Output is correct |
33 |
Correct |
6 ms |
1912 KB |
Output is correct |
34 |
Correct |
6 ms |
1912 KB |
Output is correct |
35 |
Correct |
6 ms |
1912 KB |
Output is correct |
36 |
Correct |
6 ms |
1912 KB |
Output is correct |
37 |
Correct |
6 ms |
1912 KB |
Output is correct |
38 |
Correct |
10 ms |
2680 KB |
Output is correct |
39 |
Correct |
9 ms |
2680 KB |
Output is correct |
40 |
Correct |
8 ms |
2552 KB |
Output is correct |
41 |
Correct |
9 ms |
2552 KB |
Output is correct |
42 |
Correct |
8 ms |
2552 KB |
Output is correct |
43 |
Correct |
8 ms |
2552 KB |
Output is correct |
44 |
Correct |
9 ms |
2552 KB |
Output is correct |
45 |
Correct |
8 ms |
2552 KB |
Output is correct |
46 |
Correct |
8 ms |
2552 KB |
Output is correct |
47 |
Correct |
8 ms |
2680 KB |
Output is correct |
48 |
Correct |
8 ms |
2552 KB |
Output is correct |
49 |
Correct |
8 ms |
2680 KB |
Output is correct |
50 |
Correct |
8 ms |
2552 KB |
Output is correct |
51 |
Correct |
8 ms |
2552 KB |
Output is correct |
52 |
Correct |
8 ms |
2552 KB |
Output is correct |
53 |
Correct |
8 ms |
2552 KB |
Output is correct |
54 |
Correct |
7 ms |
2680 KB |
Output is correct |
55 |
Correct |
7 ms |
2552 KB |
Output is correct |
56 |
Correct |
7 ms |
2552 KB |
Output is correct |
57 |
Correct |
7 ms |
2552 KB |
Output is correct |
58 |
Correct |
8 ms |
2552 KB |
Output is correct |
59 |
Correct |
7 ms |
2552 KB |
Output is correct |
60 |
Correct |
8 ms |
2552 KB |
Output is correct |
61 |
Correct |
7 ms |
2552 KB |
Output is correct |
62 |
Correct |
8 ms |
2552 KB |
Output is correct |
63 |
Correct |
8 ms |
2680 KB |
Output is correct |
64 |
Correct |
8 ms |
2680 KB |
Output is correct |
65 |
Correct |
8 ms |
2680 KB |
Output is correct |
66 |
Correct |
8 ms |
2552 KB |
Output is correct |
67 |
Correct |
8 ms |
2552 KB |
Output is correct |
68 |
Correct |
8 ms |
2552 KB |
Output is correct |
69 |
Correct |
8 ms |
2680 KB |
Output is correct |
70 |
Correct |
8 ms |
2680 KB |
Output is correct |
71 |
Correct |
7 ms |
2552 KB |
Output is correct |
72 |
Correct |
7 ms |
2552 KB |
Output is correct |
73 |
Correct |
8 ms |
2552 KB |
Output is correct |
74 |
Correct |
7 ms |
2680 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
1912 KB |
Output is correct |
2 |
Correct |
6 ms |
1912 KB |
Output is correct |
3 |
Correct |
6 ms |
1912 KB |
Output is correct |
4 |
Correct |
6 ms |
1912 KB |
Output is correct |
5 |
Correct |
5 ms |
1912 KB |
Output is correct |
6 |
Correct |
6 ms |
1912 KB |
Output is correct |
7 |
Correct |
6 ms |
1912 KB |
Output is correct |
8 |
Correct |
6 ms |
1912 KB |
Output is correct |
9 |
Correct |
6 ms |
1912 KB |
Output is correct |
10 |
Correct |
5 ms |
1912 KB |
Output is correct |
11 |
Correct |
6 ms |
1916 KB |
Output is correct |
12 |
Correct |
6 ms |
1912 KB |
Output is correct |
13 |
Correct |
5 ms |
1912 KB |
Output is correct |
14 |
Correct |
5 ms |
1912 KB |
Output is correct |
15 |
Correct |
6 ms |
1912 KB |
Output is correct |
16 |
Correct |
6 ms |
1912 KB |
Output is correct |
17 |
Correct |
6 ms |
1912 KB |
Output is correct |
18 |
Correct |
6 ms |
1912 KB |
Output is correct |
19 |
Correct |
6 ms |
1916 KB |
Output is correct |
20 |
Correct |
6 ms |
1912 KB |
Output is correct |
21 |
Correct |
5 ms |
1912 KB |
Output is correct |
22 |
Correct |
6 ms |
1912 KB |
Output is correct |
23 |
Correct |
6 ms |
1912 KB |
Output is correct |
24 |
Correct |
6 ms |
1912 KB |
Output is correct |
25 |
Correct |
6 ms |
1912 KB |
Output is correct |
26 |
Correct |
6 ms |
1912 KB |
Output is correct |
27 |
Correct |
6 ms |
1912 KB |
Output is correct |
28 |
Correct |
5 ms |
1912 KB |
Output is correct |
29 |
Correct |
6 ms |
1912 KB |
Output is correct |
30 |
Correct |
6 ms |
1912 KB |
Output is correct |
31 |
Correct |
6 ms |
1916 KB |
Output is correct |
32 |
Correct |
5 ms |
1916 KB |
Output is correct |
33 |
Correct |
6 ms |
1912 KB |
Output is correct |
34 |
Correct |
6 ms |
1912 KB |
Output is correct |
35 |
Correct |
6 ms |
1912 KB |
Output is correct |
36 |
Correct |
6 ms |
1912 KB |
Output is correct |
37 |
Correct |
6 ms |
1912 KB |
Output is correct |
38 |
Correct |
10 ms |
2680 KB |
Output is correct |
39 |
Correct |
9 ms |
2680 KB |
Output is correct |
40 |
Correct |
8 ms |
2552 KB |
Output is correct |
41 |
Correct |
9 ms |
2552 KB |
Output is correct |
42 |
Correct |
8 ms |
2552 KB |
Output is correct |
43 |
Correct |
8 ms |
2552 KB |
Output is correct |
44 |
Correct |
9 ms |
2552 KB |
Output is correct |
45 |
Correct |
8 ms |
2552 KB |
Output is correct |
46 |
Correct |
8 ms |
2552 KB |
Output is correct |
47 |
Correct |
8 ms |
2680 KB |
Output is correct |
48 |
Correct |
8 ms |
2552 KB |
Output is correct |
49 |
Correct |
8 ms |
2680 KB |
Output is correct |
50 |
Correct |
8 ms |
2552 KB |
Output is correct |
51 |
Correct |
8 ms |
2552 KB |
Output is correct |
52 |
Correct |
8 ms |
2552 KB |
Output is correct |
53 |
Correct |
8 ms |
2552 KB |
Output is correct |
54 |
Correct |
7 ms |
2680 KB |
Output is correct |
55 |
Correct |
7 ms |
2552 KB |
Output is correct |
56 |
Correct |
7 ms |
2552 KB |
Output is correct |
57 |
Correct |
7 ms |
2552 KB |
Output is correct |
58 |
Correct |
8 ms |
2552 KB |
Output is correct |
59 |
Correct |
7 ms |
2552 KB |
Output is correct |
60 |
Correct |
8 ms |
2552 KB |
Output is correct |
61 |
Correct |
7 ms |
2552 KB |
Output is correct |
62 |
Correct |
8 ms |
2552 KB |
Output is correct |
63 |
Correct |
8 ms |
2680 KB |
Output is correct |
64 |
Correct |
8 ms |
2680 KB |
Output is correct |
65 |
Correct |
8 ms |
2680 KB |
Output is correct |
66 |
Correct |
8 ms |
2552 KB |
Output is correct |
67 |
Correct |
8 ms |
2552 KB |
Output is correct |
68 |
Correct |
8 ms |
2552 KB |
Output is correct |
69 |
Correct |
8 ms |
2680 KB |
Output is correct |
70 |
Correct |
8 ms |
2680 KB |
Output is correct |
71 |
Correct |
7 ms |
2552 KB |
Output is correct |
72 |
Correct |
7 ms |
2552 KB |
Output is correct |
73 |
Correct |
8 ms |
2552 KB |
Output is correct |
74 |
Correct |
7 ms |
2680 KB |
Output is correct |
75 |
Correct |
772 ms |
100456 KB |
Output is correct |
76 |
Correct |
842 ms |
101736 KB |
Output is correct |
77 |
Correct |
690 ms |
104296 KB |
Output is correct |
78 |
Correct |
734 ms |
105644 KB |
Output is correct |
79 |
Correct |
255 ms |
105960 KB |
Output is correct |
80 |
Correct |
310 ms |
103492 KB |
Output is correct |
81 |
Correct |
600 ms |
104292 KB |
Output is correct |
82 |
Correct |
786 ms |
105544 KB |
Output is correct |
83 |
Correct |
682 ms |
108492 KB |
Output is correct |
84 |
Correct |
713 ms |
108408 KB |
Output is correct |
85 |
Correct |
623 ms |
105064 KB |
Output is correct |
86 |
Correct |
372 ms |
101992 KB |
Output is correct |
87 |
Correct |
396 ms |
100840 KB |
Output is correct |
88 |
Correct |
535 ms |
100328 KB |
Output is correct |
89 |
Correct |
516 ms |
105192 KB |
Output is correct |
90 |
Correct |
396 ms |
109436 KB |
Output is correct |
91 |
Correct |
314 ms |
102120 KB |
Output is correct |
92 |
Correct |
312 ms |
101352 KB |
Output is correct |
93 |
Correct |
365 ms |
105064 KB |
Output is correct |
94 |
Correct |
322 ms |
109092 KB |
Output is correct |
95 |
Correct |
397 ms |
109292 KB |
Output is correct |
96 |
Correct |
364 ms |
102504 KB |
Output is correct |
97 |
Correct |
397 ms |
109628 KB |
Output is correct |
98 |
Correct |
401 ms |
108008 KB |
Output is correct |
99 |
Correct |
379 ms |
108388 KB |
Output is correct |
100 |
Correct |
315 ms |
102888 KB |
Output is correct |
101 |
Correct |
329 ms |
103016 KB |
Output is correct |
102 |
Correct |
647 ms |
103016 KB |
Output is correct |
103 |
Correct |
604 ms |
101844 KB |
Output is correct |
104 |
Correct |
777 ms |
106576 KB |
Output is correct |
105 |
Correct |
572 ms |
106344 KB |
Output is correct |
106 |
Correct |
618 ms |
108672 KB |
Output is correct |
107 |
Correct |
509 ms |
105192 KB |
Output is correct |
108 |
Correct |
716 ms |
105044 KB |
Output is correct |
109 |
Correct |
614 ms |
110568 KB |
Output is correct |
110 |
Correct |
294 ms |
103016 KB |
Output is correct |
111 |
Correct |
370 ms |
103912 KB |
Output is correct |
112 |
Correct |
545 ms |
99944 KB |
Output is correct |
113 |
Correct |
289 ms |
110864 KB |
Output is correct |