#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcount
const int N = 2e5 + 7, INF = 1e18 + 7;
int n, m;
struct El { int v, c; } a[N];
struct Node { int cnt, sum; Node *l, *r; Node () { cnt = sum = 0; l = r = NULL; } };
vector <int> c;
Node *build(int tl, int tr) {
Node *ans = new Node();
if (tl == tr) return ans;
int tm = (tl + tr) >> 1;
ans->l = build(tl, tm); ans->r = build(tm + 1, tr);
return ans;
}
void relax(Node *t) { t->cnt = t->l->cnt + t->r->cnt; t->sum = t->l->sum + t->r->sum; }
Node *add(Node *t, int tl, int tr, int p) {
Node *ans = new Node();
if (tl == tr) { ans->cnt = t->cnt + 1; ans->sum = t->sum + c[p]; return ans; }
int tm = (tl + tr) >> 1;
if (p <= tm) { ans->l = add(t->l, tl, tm, p); ans->r = t->r; }
else { ans->l = t->l; ans->r = add(t->r, tm + 1, tr, p); }
relax(ans); return ans;
}
int get(Node *l, Node *r, int tl, int tr, int k) {
if (tl == tr) return c[tl] * k;
int tm = (tl + tr) >> 1;
int t = r->r->cnt - l->r->cnt;
if (k <= t) return get(l->r, r->r, tm + 1, tr, k);
else return get(l->l, r->l, tl, tm, k - t) + (r->r->sum - l->r->sum);
}
Node *t[N];
int get(int l, int r) {
return get(t[l - 1], t[r], 0, N, m) - 2 * (a[r].c - a[l].c);
}
int ans = -INF;
int get(int i, int l, int r) {
int best = -INF, pos = l;
for (int j = l; j <= r && m <= i - j + 1; ++j) {
int nn = get(j, i);
if (best < nn) { best = nn; pos = j; }
}
ans = max(ans, best);
return pos;
}
void solve(int l, int r, int ll, int rr) {
if (r < l) return;
int m = (l + r) >> 1; int mm = get(m, ll, rr);
if (l == r) return;
solve(l, m - 1, ll, mm); solve(m + 1, r, mm, rr);
}
bool comp(El a, El b) { return a.c < b.c; }
signed main() {
#ifdef HOME
freopen("input.txt", "r", stdin);
#else
ios_base::sync_with_stdio(0); cin.tie(0);
#endif
cin >> n >> m;
for (int i = 1; i <= n; ++i) { cin >> a[i].v >> a[i].c; c.app(a[i].v); }
sort(c.begin(), c.end()); c.resize(unique(all(c)) - c.begin());
sort(a + 1, a + n + 1, comp);
t[0] = build(0, N);
for (int i = 1; i <= n; ++i) {
t[i] = add(t[i - 1], 0, N, lower_bound(c.begin(), c.end(), a[i].v) - c.begin());
}
solve(1, n, 1, n); cout << ans << '\n';
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
29 ms |
19192 KB |
Output is correct |
2 |
Correct |
29 ms |
19192 KB |
Output is correct |
3 |
Correct |
29 ms |
19192 KB |
Output is correct |
4 |
Correct |
29 ms |
19192 KB |
Output is correct |
5 |
Correct |
29 ms |
19192 KB |
Output is correct |
6 |
Correct |
29 ms |
19192 KB |
Output is correct |
7 |
Correct |
29 ms |
19240 KB |
Output is correct |
8 |
Correct |
29 ms |
19192 KB |
Output is correct |
9 |
Correct |
29 ms |
19192 KB |
Output is correct |
10 |
Correct |
29 ms |
19308 KB |
Output is correct |
11 |
Correct |
29 ms |
19192 KB |
Output is correct |
12 |
Correct |
29 ms |
19448 KB |
Output is correct |
13 |
Correct |
29 ms |
19320 KB |
Output is correct |
14 |
Correct |
29 ms |
19192 KB |
Output is correct |
15 |
Correct |
29 ms |
19192 KB |
Output is correct |
16 |
Correct |
28 ms |
19192 KB |
Output is correct |
17 |
Correct |
29 ms |
19192 KB |
Output is correct |
18 |
Correct |
29 ms |
19220 KB |
Output is correct |
19 |
Correct |
29 ms |
19192 KB |
Output is correct |
20 |
Correct |
29 ms |
19192 KB |
Output is correct |
21 |
Correct |
29 ms |
19192 KB |
Output is correct |
22 |
Correct |
29 ms |
19192 KB |
Output is correct |
23 |
Correct |
29 ms |
19192 KB |
Output is correct |
24 |
Correct |
29 ms |
19192 KB |
Output is correct |
25 |
Correct |
29 ms |
19192 KB |
Output is correct |
26 |
Correct |
33 ms |
19192 KB |
Output is correct |
27 |
Correct |
29 ms |
19192 KB |
Output is correct |
28 |
Correct |
32 ms |
19192 KB |
Output is correct |
29 |
Correct |
29 ms |
19192 KB |
Output is correct |
30 |
Correct |
28 ms |
19192 KB |
Output is correct |
31 |
Correct |
29 ms |
19192 KB |
Output is correct |
32 |
Correct |
29 ms |
19192 KB |
Output is correct |
33 |
Correct |
29 ms |
19192 KB |
Output is correct |
34 |
Correct |
29 ms |
19192 KB |
Output is correct |
35 |
Correct |
29 ms |
19192 KB |
Output is correct |
36 |
Correct |
29 ms |
19192 KB |
Output is correct |
37 |
Correct |
29 ms |
19176 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
29 ms |
19192 KB |
Output is correct |
2 |
Correct |
29 ms |
19192 KB |
Output is correct |
3 |
Correct |
29 ms |
19192 KB |
Output is correct |
4 |
Correct |
29 ms |
19192 KB |
Output is correct |
5 |
Correct |
29 ms |
19192 KB |
Output is correct |
6 |
Correct |
29 ms |
19192 KB |
Output is correct |
7 |
Correct |
29 ms |
19240 KB |
Output is correct |
8 |
Correct |
29 ms |
19192 KB |
Output is correct |
9 |
Correct |
29 ms |
19192 KB |
Output is correct |
10 |
Correct |
29 ms |
19308 KB |
Output is correct |
11 |
Correct |
29 ms |
19192 KB |
Output is correct |
12 |
Correct |
29 ms |
19448 KB |
Output is correct |
13 |
Correct |
29 ms |
19320 KB |
Output is correct |
14 |
Correct |
29 ms |
19192 KB |
Output is correct |
15 |
Correct |
29 ms |
19192 KB |
Output is correct |
16 |
Correct |
28 ms |
19192 KB |
Output is correct |
17 |
Correct |
29 ms |
19192 KB |
Output is correct |
18 |
Correct |
29 ms |
19220 KB |
Output is correct |
19 |
Correct |
29 ms |
19192 KB |
Output is correct |
20 |
Correct |
29 ms |
19192 KB |
Output is correct |
21 |
Correct |
29 ms |
19192 KB |
Output is correct |
22 |
Correct |
29 ms |
19192 KB |
Output is correct |
23 |
Correct |
29 ms |
19192 KB |
Output is correct |
24 |
Correct |
29 ms |
19192 KB |
Output is correct |
25 |
Correct |
29 ms |
19192 KB |
Output is correct |
26 |
Correct |
33 ms |
19192 KB |
Output is correct |
27 |
Correct |
29 ms |
19192 KB |
Output is correct |
28 |
Correct |
32 ms |
19192 KB |
Output is correct |
29 |
Correct |
29 ms |
19192 KB |
Output is correct |
30 |
Correct |
28 ms |
19192 KB |
Output is correct |
31 |
Correct |
29 ms |
19192 KB |
Output is correct |
32 |
Correct |
29 ms |
19192 KB |
Output is correct |
33 |
Correct |
29 ms |
19192 KB |
Output is correct |
34 |
Correct |
29 ms |
19192 KB |
Output is correct |
35 |
Correct |
29 ms |
19192 KB |
Output is correct |
36 |
Correct |
29 ms |
19192 KB |
Output is correct |
37 |
Correct |
29 ms |
19176 KB |
Output is correct |
38 |
Correct |
34 ms |
20860 KB |
Output is correct |
39 |
Correct |
34 ms |
20956 KB |
Output is correct |
40 |
Correct |
34 ms |
20984 KB |
Output is correct |
41 |
Correct |
34 ms |
20984 KB |
Output is correct |
42 |
Correct |
34 ms |
20984 KB |
Output is correct |
43 |
Correct |
34 ms |
20792 KB |
Output is correct |
44 |
Correct |
34 ms |
20856 KB |
Output is correct |
45 |
Correct |
35 ms |
20984 KB |
Output is correct |
46 |
Correct |
34 ms |
20984 KB |
Output is correct |
47 |
Correct |
35 ms |
20984 KB |
Output is correct |
48 |
Correct |
34 ms |
20856 KB |
Output is correct |
49 |
Correct |
33 ms |
20984 KB |
Output is correct |
50 |
Correct |
34 ms |
20984 KB |
Output is correct |
51 |
Correct |
34 ms |
20896 KB |
Output is correct |
52 |
Correct |
34 ms |
20856 KB |
Output is correct |
53 |
Correct |
34 ms |
20932 KB |
Output is correct |
54 |
Correct |
34 ms |
20984 KB |
Output is correct |
55 |
Correct |
33 ms |
20892 KB |
Output is correct |
56 |
Correct |
33 ms |
20856 KB |
Output is correct |
57 |
Correct |
33 ms |
20856 KB |
Output is correct |
58 |
Correct |
33 ms |
21036 KB |
Output is correct |
59 |
Correct |
32 ms |
20856 KB |
Output is correct |
60 |
Correct |
38 ms |
20988 KB |
Output is correct |
61 |
Correct |
45 ms |
21180 KB |
Output is correct |
62 |
Correct |
43 ms |
20984 KB |
Output is correct |
63 |
Correct |
33 ms |
20956 KB |
Output is correct |
64 |
Correct |
33 ms |
21052 KB |
Output is correct |
65 |
Correct |
34 ms |
20984 KB |
Output is correct |
66 |
Correct |
36 ms |
20860 KB |
Output is correct |
67 |
Correct |
34 ms |
20856 KB |
Output is correct |
68 |
Correct |
39 ms |
20988 KB |
Output is correct |
69 |
Correct |
33 ms |
20856 KB |
Output is correct |
70 |
Correct |
34 ms |
21112 KB |
Output is correct |
71 |
Correct |
33 ms |
20856 KB |
Output is correct |
72 |
Correct |
32 ms |
20944 KB |
Output is correct |
73 |
Correct |
34 ms |
20860 KB |
Output is correct |
74 |
Correct |
32 ms |
20984 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
29 ms |
19192 KB |
Output is correct |
2 |
Correct |
29 ms |
19192 KB |
Output is correct |
3 |
Correct |
29 ms |
19192 KB |
Output is correct |
4 |
Correct |
29 ms |
19192 KB |
Output is correct |
5 |
Correct |
29 ms |
19192 KB |
Output is correct |
6 |
Correct |
29 ms |
19192 KB |
Output is correct |
7 |
Correct |
29 ms |
19240 KB |
Output is correct |
8 |
Correct |
29 ms |
19192 KB |
Output is correct |
9 |
Correct |
29 ms |
19192 KB |
Output is correct |
10 |
Correct |
29 ms |
19308 KB |
Output is correct |
11 |
Correct |
29 ms |
19192 KB |
Output is correct |
12 |
Correct |
29 ms |
19448 KB |
Output is correct |
13 |
Correct |
29 ms |
19320 KB |
Output is correct |
14 |
Correct |
29 ms |
19192 KB |
Output is correct |
15 |
Correct |
29 ms |
19192 KB |
Output is correct |
16 |
Correct |
28 ms |
19192 KB |
Output is correct |
17 |
Correct |
29 ms |
19192 KB |
Output is correct |
18 |
Correct |
29 ms |
19220 KB |
Output is correct |
19 |
Correct |
29 ms |
19192 KB |
Output is correct |
20 |
Correct |
29 ms |
19192 KB |
Output is correct |
21 |
Correct |
29 ms |
19192 KB |
Output is correct |
22 |
Correct |
29 ms |
19192 KB |
Output is correct |
23 |
Correct |
29 ms |
19192 KB |
Output is correct |
24 |
Correct |
29 ms |
19192 KB |
Output is correct |
25 |
Correct |
29 ms |
19192 KB |
Output is correct |
26 |
Correct |
33 ms |
19192 KB |
Output is correct |
27 |
Correct |
29 ms |
19192 KB |
Output is correct |
28 |
Correct |
32 ms |
19192 KB |
Output is correct |
29 |
Correct |
29 ms |
19192 KB |
Output is correct |
30 |
Correct |
28 ms |
19192 KB |
Output is correct |
31 |
Correct |
29 ms |
19192 KB |
Output is correct |
32 |
Correct |
29 ms |
19192 KB |
Output is correct |
33 |
Correct |
29 ms |
19192 KB |
Output is correct |
34 |
Correct |
29 ms |
19192 KB |
Output is correct |
35 |
Correct |
29 ms |
19192 KB |
Output is correct |
36 |
Correct |
29 ms |
19192 KB |
Output is correct |
37 |
Correct |
29 ms |
19176 KB |
Output is correct |
38 |
Correct |
34 ms |
20860 KB |
Output is correct |
39 |
Correct |
34 ms |
20956 KB |
Output is correct |
40 |
Correct |
34 ms |
20984 KB |
Output is correct |
41 |
Correct |
34 ms |
20984 KB |
Output is correct |
42 |
Correct |
34 ms |
20984 KB |
Output is correct |
43 |
Correct |
34 ms |
20792 KB |
Output is correct |
44 |
Correct |
34 ms |
20856 KB |
Output is correct |
45 |
Correct |
35 ms |
20984 KB |
Output is correct |
46 |
Correct |
34 ms |
20984 KB |
Output is correct |
47 |
Correct |
35 ms |
20984 KB |
Output is correct |
48 |
Correct |
34 ms |
20856 KB |
Output is correct |
49 |
Correct |
33 ms |
20984 KB |
Output is correct |
50 |
Correct |
34 ms |
20984 KB |
Output is correct |
51 |
Correct |
34 ms |
20896 KB |
Output is correct |
52 |
Correct |
34 ms |
20856 KB |
Output is correct |
53 |
Correct |
34 ms |
20932 KB |
Output is correct |
54 |
Correct |
34 ms |
20984 KB |
Output is correct |
55 |
Correct |
33 ms |
20892 KB |
Output is correct |
56 |
Correct |
33 ms |
20856 KB |
Output is correct |
57 |
Correct |
33 ms |
20856 KB |
Output is correct |
58 |
Correct |
33 ms |
21036 KB |
Output is correct |
59 |
Correct |
32 ms |
20856 KB |
Output is correct |
60 |
Correct |
38 ms |
20988 KB |
Output is correct |
61 |
Correct |
45 ms |
21180 KB |
Output is correct |
62 |
Correct |
43 ms |
20984 KB |
Output is correct |
63 |
Correct |
33 ms |
20956 KB |
Output is correct |
64 |
Correct |
33 ms |
21052 KB |
Output is correct |
65 |
Correct |
34 ms |
20984 KB |
Output is correct |
66 |
Correct |
36 ms |
20860 KB |
Output is correct |
67 |
Correct |
34 ms |
20856 KB |
Output is correct |
68 |
Correct |
39 ms |
20988 KB |
Output is correct |
69 |
Correct |
33 ms |
20856 KB |
Output is correct |
70 |
Correct |
34 ms |
21112 KB |
Output is correct |
71 |
Correct |
33 ms |
20856 KB |
Output is correct |
72 |
Correct |
32 ms |
20944 KB |
Output is correct |
73 |
Correct |
34 ms |
20860 KB |
Output is correct |
74 |
Correct |
32 ms |
20984 KB |
Output is correct |
75 |
Correct |
1356 ms |
192220 KB |
Output is correct |
76 |
Correct |
1460 ms |
187444 KB |
Output is correct |
77 |
Correct |
1275 ms |
192576 KB |
Output is correct |
78 |
Correct |
1400 ms |
195092 KB |
Output is correct |
79 |
Correct |
577 ms |
195760 KB |
Output is correct |
80 |
Correct |
601 ms |
190776 KB |
Output is correct |
81 |
Correct |
966 ms |
193384 KB |
Output is correct |
82 |
Correct |
1153 ms |
195688 KB |
Output is correct |
83 |
Correct |
1046 ms |
201588 KB |
Output is correct |
84 |
Correct |
1065 ms |
200936 KB |
Output is correct |
85 |
Correct |
915 ms |
194752 KB |
Output is correct |
86 |
Correct |
603 ms |
188904 KB |
Output is correct |
87 |
Correct |
634 ms |
186700 KB |
Output is correct |
88 |
Correct |
826 ms |
185784 KB |
Output is correct |
89 |
Correct |
832 ms |
194948 KB |
Output is correct |
90 |
Correct |
655 ms |
202912 KB |
Output is correct |
91 |
Correct |
600 ms |
189124 KB |
Output is correct |
92 |
Correct |
539 ms |
187852 KB |
Output is correct |
93 |
Correct |
581 ms |
194916 KB |
Output is correct |
94 |
Correct |
534 ms |
202856 KB |
Output is correct |
95 |
Correct |
659 ms |
203112 KB |
Output is correct |
96 |
Correct |
563 ms |
192604 KB |
Output is correct |
97 |
Correct |
606 ms |
206304 KB |
Output is correct |
98 |
Correct |
619 ms |
203712 KB |
Output is correct |
99 |
Correct |
579 ms |
204136 KB |
Output is correct |
100 |
Correct |
536 ms |
193564 KB |
Output is correct |
101 |
Correct |
525 ms |
193500 KB |
Output is correct |
102 |
Correct |
813 ms |
191116 KB |
Output is correct |
103 |
Correct |
748 ms |
188532 KB |
Output is correct |
104 |
Correct |
880 ms |
197740 KB |
Output is correct |
105 |
Correct |
655 ms |
197084 KB |
Output is correct |
106 |
Correct |
667 ms |
201704 KB |
Output is correct |
107 |
Correct |
679 ms |
195320 KB |
Output is correct |
108 |
Correct |
1225 ms |
194128 KB |
Output is correct |
109 |
Correct |
1099 ms |
204704 KB |
Output is correct |
110 |
Correct |
471 ms |
192376 KB |
Output is correct |
111 |
Correct |
533 ms |
194284 KB |
Output is correct |
112 |
Correct |
1287 ms |
185336 KB |
Output is correct |
113 |
Correct |
604 ms |
204860 KB |
Output is correct |