#include <bits/stdc++.h>
#include <bits/extc++.h>
#define StarBurstStream ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define iter(a) a.begin(), a.end()
#define riter(a) a.rbegin(), a.rend()
#define lsort(a) sort(iter(a))
#define gsort(a) sort(riter(a))
#define pb(a) push_back(a)
#define eb(a) emplace_back(a)
#define pf(a) push_front(a)
#define ef(a) emplace_front(a)
#define pob pop_back()
#define pof pop_front()
#define mp(a, b) make_pair(a, b)
#define F first
#define S second
#define mt make_tuple
#define gt(t, i) get<i>(t)
#define tomax(a, b) ((a) = max((a), (b)))
#define tomin(a, b) ((a) = min((a), (b)))
#define topos(a) ((a) = (((a) % MOD + MOD) % MOD))
#define uni(a) a.resize(unique(iter(a)) - a.begin())
#define printv(a, b) {bool pvaspace=false; \
for(auto pva : a){ \
if(pvaspace) b << " "; pvaspace=true;\
b << pva;\
}\
b << "\n";}
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pdd = pair<ld, ld>;
using tiii = tuple<int, int, int>;
const ll MOD = 1000000007;
const ll MAX = 1LL << 60;
template<typename A, typename B>
ostream& operator<<(ostream& o, pair<A, B> p){
return o << '(' << p.F << ',' << p.S << ')';
}
ll ifloor(ll a, ll b){
if(b < 0) a *= -1, b *= -1;
if(a < 0) return (a - b + 1) / b;
else return a / b;
}
ll iceil(ll a, ll b){
if(b < 0) a *= -1, b *= -1;
if(a > 0) return (a + b - 1) / b;
else return a / b;
}
struct Node{
int l = -1, r = -1;
ll cnt = 0, sum = 0;
};
vector<Node> st(8e6);
int ts = 0;
int build(int l, int r){
int id = ts++;
if(l == r) return id;
int m = (l + r) / 2;
st[id].l = build(l, m);
st[id].r = build(m + 1, r);
return id;
}
int modify(int pos, ll v, int L, int R, int oid){
int id = ts++;
st[id] = st[oid];
// cerr << "modify " << pos << " " << v << " " << L << " " << R << " " << oid << " " << id << "\n";
if(L == R){
st[id].cnt++;
st[id].sum += v;
return id;
}
int M = (L + R) / 2;
if(pos <= M) st[id].l = modify(pos, v, L, M, st[id].l);
else st[id].r = modify(pos, v, M + 1, R, st[id].r);
st[id].sum = st[st[id].l].sum + st[st[id].r].sum;
st[id].cnt = st[st[id].l].cnt + st[st[id].r].cnt;
return id;
}
vector<int> discr(1, MAX);
ll findkth(int k, int l, int r, int id1, int id2){
// cerr << "findkth " << k << " " << id1 << " " << id2 << " " << l << " " << r << "\n";
if(st[id2].l == -1) return discr[l] * k;
int m = (l + r) / 2;
if(st[st[id2].l].cnt - st[st[id1].l].cnt >= k) return findkth(k, l, m, st[id1].l, st[id2].l);
return st[st[id2].l].sum - st[st[id1].l].sum + findkth(k - st[st[id2].l].cnt + st[st[id1].l].cnt, m + 1, r, st[id1].r, st[id2].r);
}
void _print(int l, int r, int id){
if(l == r){
cerr << st[id].cnt << "," << st[id].sum << " ";
return;
}
int m = (l + r) / 2;
_print(l, m, st[id].l);
_print(m + 1, r, st[id].r);
}
int n, M, tn;
void print(int rt){
_print(1, tn, rt);
cerr << "\n";
}
vector<ll> dp;
vector<pll> a;
vector<ll> c;
vector<int> rt;
ll calc(int l, int r){
if(r - l + 1 < M) return -MAX;
ll tmp = findkth(M, 1, tn, rt[l - 1], rt[r]);
// cerr << "calc " << l << " " << r << " " << tmp << " " << (c[r] - c[l]) << "\n";
return tmp - 2 * (c[r] - c[l]);
}
void dfs(int l, int r, int tl, int tr){
if(l > r) return;
int m = (l + r) / 2;
int pos = tl;
dp[m] = calc(pos, m);
for(int i = tl; i <= tr; i++){
ll tmp = calc(i, m);
// cerr << i << " " << m << " " << tmp << "\n";
if(tmp > dp[m]){
pos = i;
dp[m] = tmp;
}
}
// cerr << "test " << l << " " << r << " " << m << " " << tl << " " << tr << " " << pos << "\n";
dfs(l, m - 1, tl, pos);
dfs(m + 1, r, pos, tr);
}
int main(){
StarBurstStream
cin >> n >> M;
a.resize(n + 1);
dp.resize(n + 1, -MAX);
c.resize(n + 1);
rt.resize(n + 1);
for(int i = 1; i <= n; i++){
cin >> a[i].S >> a[i].F;
discr.eb(a[i].S);
}
sort(discr.begin() + 1, discr.end(), greater<>());
uni(discr);
sort(a.begin() + 1, a.end());
tn = discr.size() - 1;
// printv(a, cerr);
rt[0] = build(1, tn);
for(int i = 1; i <= n; i++){
c[i] = a[i].F;
int id = lower_bound(iter(discr), a[i].S, greater<>()) - discr.begin();
// cerr << id << " " << a[i] << "\n";
rt[i] = modify(id, a[i].S, 1, tn, rt[i - 1]);
// cerr << i << " ";
// print(rt[i]);
}
dfs(1, n, 1, n);
cout << *max_element(iter(dp)) << "\n";
return 0;
}
Compilation message
cake3.cpp:97:22: warning: overflow in conversion from 'long long int' to 'std::vector<int>::value_type' {aka 'int'} changes value from '1152921504606846976' to '0' [-Woverflow]
97 | vector<int> discr(1, MAX);
| ^~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
115 ms |
188140 KB |
Output is correct |
2 |
Correct |
124 ms |
188268 KB |
Output is correct |
3 |
Correct |
111 ms |
188140 KB |
Output is correct |
4 |
Correct |
115 ms |
188140 KB |
Output is correct |
5 |
Correct |
112 ms |
188268 KB |
Output is correct |
6 |
Correct |
113 ms |
188140 KB |
Output is correct |
7 |
Correct |
116 ms |
188268 KB |
Output is correct |
8 |
Correct |
112 ms |
188140 KB |
Output is correct |
9 |
Correct |
112 ms |
188140 KB |
Output is correct |
10 |
Correct |
114 ms |
188140 KB |
Output is correct |
11 |
Correct |
113 ms |
188140 KB |
Output is correct |
12 |
Correct |
113 ms |
188140 KB |
Output is correct |
13 |
Correct |
113 ms |
188248 KB |
Output is correct |
14 |
Correct |
113 ms |
188140 KB |
Output is correct |
15 |
Correct |
112 ms |
188140 KB |
Output is correct |
16 |
Correct |
112 ms |
188140 KB |
Output is correct |
17 |
Correct |
112 ms |
188228 KB |
Output is correct |
18 |
Correct |
112 ms |
188140 KB |
Output is correct |
19 |
Correct |
113 ms |
188300 KB |
Output is correct |
20 |
Correct |
116 ms |
188140 KB |
Output is correct |
21 |
Correct |
114 ms |
188140 KB |
Output is correct |
22 |
Correct |
113 ms |
188140 KB |
Output is correct |
23 |
Correct |
119 ms |
188140 KB |
Output is correct |
24 |
Correct |
113 ms |
188140 KB |
Output is correct |
25 |
Correct |
115 ms |
188140 KB |
Output is correct |
26 |
Correct |
113 ms |
188140 KB |
Output is correct |
27 |
Correct |
113 ms |
188268 KB |
Output is correct |
28 |
Correct |
114 ms |
188140 KB |
Output is correct |
29 |
Correct |
114 ms |
188140 KB |
Output is correct |
30 |
Correct |
114 ms |
188140 KB |
Output is correct |
31 |
Correct |
113 ms |
188324 KB |
Output is correct |
32 |
Correct |
114 ms |
188140 KB |
Output is correct |
33 |
Correct |
128 ms |
188268 KB |
Output is correct |
34 |
Correct |
112 ms |
188268 KB |
Output is correct |
35 |
Correct |
113 ms |
188140 KB |
Output is correct |
36 |
Correct |
113 ms |
188212 KB |
Output is correct |
37 |
Correct |
112 ms |
188140 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
115 ms |
188140 KB |
Output is correct |
2 |
Correct |
124 ms |
188268 KB |
Output is correct |
3 |
Correct |
111 ms |
188140 KB |
Output is correct |
4 |
Correct |
115 ms |
188140 KB |
Output is correct |
5 |
Correct |
112 ms |
188268 KB |
Output is correct |
6 |
Correct |
113 ms |
188140 KB |
Output is correct |
7 |
Correct |
116 ms |
188268 KB |
Output is correct |
8 |
Correct |
112 ms |
188140 KB |
Output is correct |
9 |
Correct |
112 ms |
188140 KB |
Output is correct |
10 |
Correct |
114 ms |
188140 KB |
Output is correct |
11 |
Correct |
113 ms |
188140 KB |
Output is correct |
12 |
Correct |
113 ms |
188140 KB |
Output is correct |
13 |
Correct |
113 ms |
188248 KB |
Output is correct |
14 |
Correct |
113 ms |
188140 KB |
Output is correct |
15 |
Correct |
112 ms |
188140 KB |
Output is correct |
16 |
Correct |
112 ms |
188140 KB |
Output is correct |
17 |
Correct |
112 ms |
188228 KB |
Output is correct |
18 |
Correct |
112 ms |
188140 KB |
Output is correct |
19 |
Correct |
113 ms |
188300 KB |
Output is correct |
20 |
Correct |
116 ms |
188140 KB |
Output is correct |
21 |
Correct |
114 ms |
188140 KB |
Output is correct |
22 |
Correct |
113 ms |
188140 KB |
Output is correct |
23 |
Correct |
119 ms |
188140 KB |
Output is correct |
24 |
Correct |
113 ms |
188140 KB |
Output is correct |
25 |
Correct |
115 ms |
188140 KB |
Output is correct |
26 |
Correct |
113 ms |
188140 KB |
Output is correct |
27 |
Correct |
113 ms |
188268 KB |
Output is correct |
28 |
Correct |
114 ms |
188140 KB |
Output is correct |
29 |
Correct |
114 ms |
188140 KB |
Output is correct |
30 |
Correct |
114 ms |
188140 KB |
Output is correct |
31 |
Correct |
113 ms |
188324 KB |
Output is correct |
32 |
Correct |
114 ms |
188140 KB |
Output is correct |
33 |
Correct |
128 ms |
188268 KB |
Output is correct |
34 |
Correct |
112 ms |
188268 KB |
Output is correct |
35 |
Correct |
113 ms |
188140 KB |
Output is correct |
36 |
Correct |
113 ms |
188212 KB |
Output is correct |
37 |
Correct |
112 ms |
188140 KB |
Output is correct |
38 |
Correct |
117 ms |
188272 KB |
Output is correct |
39 |
Correct |
118 ms |
188268 KB |
Output is correct |
40 |
Correct |
117 ms |
188268 KB |
Output is correct |
41 |
Correct |
115 ms |
188268 KB |
Output is correct |
42 |
Correct |
115 ms |
188268 KB |
Output is correct |
43 |
Correct |
118 ms |
188268 KB |
Output is correct |
44 |
Correct |
117 ms |
188268 KB |
Output is correct |
45 |
Correct |
117 ms |
188268 KB |
Output is correct |
46 |
Correct |
118 ms |
188268 KB |
Output is correct |
47 |
Correct |
118 ms |
188268 KB |
Output is correct |
48 |
Correct |
115 ms |
188268 KB |
Output is correct |
49 |
Correct |
117 ms |
188268 KB |
Output is correct |
50 |
Correct |
117 ms |
188268 KB |
Output is correct |
51 |
Correct |
116 ms |
188268 KB |
Output is correct |
52 |
Correct |
117 ms |
188396 KB |
Output is correct |
53 |
Correct |
117 ms |
188268 KB |
Output is correct |
54 |
Correct |
118 ms |
188268 KB |
Output is correct |
55 |
Correct |
114 ms |
188364 KB |
Output is correct |
56 |
Correct |
117 ms |
188268 KB |
Output is correct |
57 |
Correct |
115 ms |
188268 KB |
Output is correct |
58 |
Correct |
115 ms |
188268 KB |
Output is correct |
59 |
Correct |
114 ms |
188268 KB |
Output is correct |
60 |
Correct |
114 ms |
188268 KB |
Output is correct |
61 |
Correct |
113 ms |
188396 KB |
Output is correct |
62 |
Correct |
115 ms |
188268 KB |
Output is correct |
63 |
Correct |
115 ms |
188268 KB |
Output is correct |
64 |
Correct |
113 ms |
188268 KB |
Output is correct |
65 |
Correct |
116 ms |
188268 KB |
Output is correct |
66 |
Correct |
116 ms |
188268 KB |
Output is correct |
67 |
Correct |
115 ms |
188268 KB |
Output is correct |
68 |
Correct |
115 ms |
188268 KB |
Output is correct |
69 |
Correct |
116 ms |
188268 KB |
Output is correct |
70 |
Correct |
115 ms |
188268 KB |
Output is correct |
71 |
Correct |
115 ms |
188268 KB |
Output is correct |
72 |
Correct |
114 ms |
188268 KB |
Output is correct |
73 |
Correct |
116 ms |
188268 KB |
Output is correct |
74 |
Correct |
117 ms |
188268 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
115 ms |
188140 KB |
Output is correct |
2 |
Correct |
124 ms |
188268 KB |
Output is correct |
3 |
Correct |
111 ms |
188140 KB |
Output is correct |
4 |
Correct |
115 ms |
188140 KB |
Output is correct |
5 |
Correct |
112 ms |
188268 KB |
Output is correct |
6 |
Correct |
113 ms |
188140 KB |
Output is correct |
7 |
Correct |
116 ms |
188268 KB |
Output is correct |
8 |
Correct |
112 ms |
188140 KB |
Output is correct |
9 |
Correct |
112 ms |
188140 KB |
Output is correct |
10 |
Correct |
114 ms |
188140 KB |
Output is correct |
11 |
Correct |
113 ms |
188140 KB |
Output is correct |
12 |
Correct |
113 ms |
188140 KB |
Output is correct |
13 |
Correct |
113 ms |
188248 KB |
Output is correct |
14 |
Correct |
113 ms |
188140 KB |
Output is correct |
15 |
Correct |
112 ms |
188140 KB |
Output is correct |
16 |
Correct |
112 ms |
188140 KB |
Output is correct |
17 |
Correct |
112 ms |
188228 KB |
Output is correct |
18 |
Correct |
112 ms |
188140 KB |
Output is correct |
19 |
Correct |
113 ms |
188300 KB |
Output is correct |
20 |
Correct |
116 ms |
188140 KB |
Output is correct |
21 |
Correct |
114 ms |
188140 KB |
Output is correct |
22 |
Correct |
113 ms |
188140 KB |
Output is correct |
23 |
Correct |
119 ms |
188140 KB |
Output is correct |
24 |
Correct |
113 ms |
188140 KB |
Output is correct |
25 |
Correct |
115 ms |
188140 KB |
Output is correct |
26 |
Correct |
113 ms |
188140 KB |
Output is correct |
27 |
Correct |
113 ms |
188268 KB |
Output is correct |
28 |
Correct |
114 ms |
188140 KB |
Output is correct |
29 |
Correct |
114 ms |
188140 KB |
Output is correct |
30 |
Correct |
114 ms |
188140 KB |
Output is correct |
31 |
Correct |
113 ms |
188324 KB |
Output is correct |
32 |
Correct |
114 ms |
188140 KB |
Output is correct |
33 |
Correct |
128 ms |
188268 KB |
Output is correct |
34 |
Correct |
112 ms |
188268 KB |
Output is correct |
35 |
Correct |
113 ms |
188140 KB |
Output is correct |
36 |
Correct |
113 ms |
188212 KB |
Output is correct |
37 |
Correct |
112 ms |
188140 KB |
Output is correct |
38 |
Correct |
117 ms |
188272 KB |
Output is correct |
39 |
Correct |
118 ms |
188268 KB |
Output is correct |
40 |
Correct |
117 ms |
188268 KB |
Output is correct |
41 |
Correct |
115 ms |
188268 KB |
Output is correct |
42 |
Correct |
115 ms |
188268 KB |
Output is correct |
43 |
Correct |
118 ms |
188268 KB |
Output is correct |
44 |
Correct |
117 ms |
188268 KB |
Output is correct |
45 |
Correct |
117 ms |
188268 KB |
Output is correct |
46 |
Correct |
118 ms |
188268 KB |
Output is correct |
47 |
Correct |
118 ms |
188268 KB |
Output is correct |
48 |
Correct |
115 ms |
188268 KB |
Output is correct |
49 |
Correct |
117 ms |
188268 KB |
Output is correct |
50 |
Correct |
117 ms |
188268 KB |
Output is correct |
51 |
Correct |
116 ms |
188268 KB |
Output is correct |
52 |
Correct |
117 ms |
188396 KB |
Output is correct |
53 |
Correct |
117 ms |
188268 KB |
Output is correct |
54 |
Correct |
118 ms |
188268 KB |
Output is correct |
55 |
Correct |
114 ms |
188364 KB |
Output is correct |
56 |
Correct |
117 ms |
188268 KB |
Output is correct |
57 |
Correct |
115 ms |
188268 KB |
Output is correct |
58 |
Correct |
115 ms |
188268 KB |
Output is correct |
59 |
Correct |
114 ms |
188268 KB |
Output is correct |
60 |
Correct |
114 ms |
188268 KB |
Output is correct |
61 |
Correct |
113 ms |
188396 KB |
Output is correct |
62 |
Correct |
115 ms |
188268 KB |
Output is correct |
63 |
Correct |
115 ms |
188268 KB |
Output is correct |
64 |
Correct |
113 ms |
188268 KB |
Output is correct |
65 |
Correct |
116 ms |
188268 KB |
Output is correct |
66 |
Correct |
116 ms |
188268 KB |
Output is correct |
67 |
Correct |
115 ms |
188268 KB |
Output is correct |
68 |
Correct |
115 ms |
188268 KB |
Output is correct |
69 |
Correct |
116 ms |
188268 KB |
Output is correct |
70 |
Correct |
115 ms |
188268 KB |
Output is correct |
71 |
Correct |
115 ms |
188268 KB |
Output is correct |
72 |
Correct |
114 ms |
188268 KB |
Output is correct |
73 |
Correct |
116 ms |
188268 KB |
Output is correct |
74 |
Correct |
117 ms |
188268 KB |
Output is correct |
75 |
Correct |
957 ms |
196460 KB |
Output is correct |
76 |
Correct |
1006 ms |
196076 KB |
Output is correct |
77 |
Correct |
859 ms |
196460 KB |
Output is correct |
78 |
Correct |
890 ms |
196460 KB |
Output is correct |
79 |
Correct |
389 ms |
196460 KB |
Output is correct |
80 |
Correct |
441 ms |
196332 KB |
Output is correct |
81 |
Correct |
558 ms |
196460 KB |
Output is correct |
82 |
Correct |
737 ms |
196460 KB |
Output is correct |
83 |
Correct |
620 ms |
196844 KB |
Output is correct |
84 |
Correct |
665 ms |
196844 KB |
Output is correct |
85 |
Correct |
569 ms |
196460 KB |
Output is correct |
86 |
Correct |
398 ms |
196264 KB |
Output is correct |
87 |
Correct |
422 ms |
196204 KB |
Output is correct |
88 |
Correct |
520 ms |
196076 KB |
Output is correct |
89 |
Correct |
493 ms |
196460 KB |
Output is correct |
90 |
Correct |
422 ms |
196884 KB |
Output is correct |
91 |
Correct |
348 ms |
196204 KB |
Output is correct |
92 |
Correct |
355 ms |
196204 KB |
Output is correct |
93 |
Correct |
390 ms |
196460 KB |
Output is correct |
94 |
Correct |
342 ms |
196716 KB |
Output is correct |
95 |
Correct |
407 ms |
196716 KB |
Output is correct |
96 |
Correct |
196 ms |
196332 KB |
Output is correct |
97 |
Correct |
199 ms |
196844 KB |
Output is correct |
98 |
Correct |
206 ms |
196716 KB |
Output is correct |
99 |
Correct |
203 ms |
196716 KB |
Output is correct |
100 |
Correct |
192 ms |
196332 KB |
Output is correct |
101 |
Correct |
192 ms |
196332 KB |
Output is correct |
102 |
Correct |
441 ms |
196308 KB |
Output is correct |
103 |
Correct |
424 ms |
196204 KB |
Output is correct |
104 |
Correct |
479 ms |
196588 KB |
Output is correct |
105 |
Correct |
370 ms |
196588 KB |
Output is correct |
106 |
Correct |
378 ms |
196716 KB |
Output is correct |
107 |
Correct |
354 ms |
196484 KB |
Output is correct |
108 |
Correct |
844 ms |
196460 KB |
Output is correct |
109 |
Correct |
754 ms |
196844 KB |
Output is correct |
110 |
Correct |
210 ms |
197864 KB |
Output is correct |
111 |
Correct |
224 ms |
197992 KB |
Output is correct |
112 |
Correct |
610 ms |
197736 KB |
Output is correct |
113 |
Correct |
423 ms |
200168 KB |
Output is correct |