#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
#define pb push_back
#define f first
#define s second
namespace debug {
const int DEBUG = true;
template<class T1, class T2>
void pr(const pair<T1, T2> &x);
template<class T, size_t SZ>
void pr(const array<T, SZ> &x);
template<class T>
void pr(const vector<T> &x);
template<class T>
void pr(const set<T> &x);
template<class T1, class T2>
void pr(const map<T1, T2> &x);
template<class T>
void pr(const T &x) { if (DEBUG) cout << x; }
template<class T, class... Ts>
void pr(const T &first, const Ts &... rest) { pr(first), pr(rest...); }
template<class T1, class T2>
void pr(const pair<T1, T2> &x) { pr("{", x.f, ", ", x.s, "}"); }
template<class T>
void prIn(const T &x) {
pr("{");
bool fst = 1;
for (auto &a : x) {
pr(fst ? "" : ", ", a), fst = 0;
}
pr("}");
}
template<class T, size_t SZ>
void pr(const array<T, SZ> &x) { prIn(x); }
template<class T>
void pr(const vector<T> &x) { prIn(x); }
template<class T>
void pr(const set<T> &x) { prIn(x); }
template<class T1, class T2>
void pr(const map<T1, T2> &x) { prIn(x); }
void ps() { pr("\n"), cout << flush; }
template<class Arg, class... Args>
void ps(const Arg &first, const Args &... rest) {
pr(first, " ");
ps(rest...);
}
}
using namespace debug;
const int MAXN = 2e5 + 100;
const int LOGN = 20;
const ll INF = 1e15;
int N, K;
ll v[MAXN], c[MAXN];
ll bTotal = -INF;
template<class Compare = less<pl>>
struct lazyQueue {
priority_queue<pl, vector<pl>, Compare> q;
priority_queue<pl, vector<pl>, Compare> r;
void add(pl x) {
q.push(x);
}
void erase(pl x) {
r.push(x);
}
void clear() {
while (q.size() && r.size() && q.top() == r.top()) {
q.pop();
r.pop();
}
}
pl top() {
clear();
return q.top();
}
void pop() {
clear();
q.pop();
}
int size() {
return q.size() - r.size();
}
};
pi sRange[LOGN];
ll sSum[LOGN];
lazyQueue<greater<pl>> sel[LOGN];
lazyQueue<> extq[LOGN];
int grp[LOGN][MAXN];
void reRange(int level, pi nRange) {
auto &cSelect = sel[level];
auto &cExt = extq[level];
auto &cGrp = grp[level];
pi &cRange = sRange[level];
ll &cSum = sSum[level];
while (cRange.s < nRange.s) {
cExt.add({v[cRange.s + 1], cRange.s + 1});
cGrp[cRange.s + 1] = 1;
cRange.s++;
}
while (cRange.f < nRange.f) {
if (cGrp[cRange.f] == 0) {
cSelect.erase({v[cRange.f], cRange.f});
cSum -= v[cRange.f];
} else {
cExt.erase({v[cRange.f], cRange.f});
}
cRange.f++;
}
while (cSelect.size() < K && cExt.size()) {
cSum += cExt.top().f;
cGrp[cExt.top().s] = 0;
cSelect.add(cExt.top());
cExt.pop();
}
while (cExt.size() && cSelect.top().f < cExt.top().f) {
cSum -= cSelect.top().f;
cSum += cExt.top().f;
cGrp[cSelect.top().s] = 1;
cGrp[cExt.top().s] = 0;
cExt.add(cSelect.top());
cSelect.add(cExt.top());
cSelect.pop();
cExt.pop();
}
// assert(cRange == nRange);
// assert(cSet.size() == min(K, cRange.s - cRange.f + 1));
}
ll getTotal(int setI) {
auto &cSelect = sel[setI];
// assert(cSet.size() <= K);
if (cSelect.size() == K) {
return sSum[setI];
} else {
return -INF;
}
}
int call = 0;
void compute(int level, int l1, int l2, int r1, int r2) {
int cL = (l1 + l2) / 2;
// cout << call++ << endl;
ll maxTotal = -INF;
int maxR = -1;
// assert(0 <= l1 && 0 <= r1);
for (int cR = max(cL + K - 1, r1); cR <= r2; cR++) {
reRange(level, {cL, cR});
ll cTotal = getTotal(level) + c[cL] - c[cR];
if (cTotal > maxTotal) {
maxTotal = cTotal;
maxR = cR;
}
}
// assert(maxR != -1);
bTotal = max(bTotal, maxTotal);
if (l1 < cL) {
compute(level + 1, l1, cL - 1, r1, maxR);
}
if (cL < l2) {
compute(level + 1, cL + 1, l2, maxR, r2);
}
}
pi items[MAXN];
int main() {
// freopen("cake3.in", "r", stdin);
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> N >> K;
// cout << "start" << endl;
for (int i = 0; i < N; i++) {
int x, y;
cin >> x >> y;
items[i] = {y, x};
}
sort(items, items + N);
for (int i = 0; i < N; i++) {
v[i] = items[i].s;
c[i] = items[i].f;
c[i] *= 2;
}
fill(sSum, sSum + LOGN, 0);
fill(sRange, sRange + LOGN, make_pair(0, -1));
// cout << "computing" << endl;
compute(0, 0, N - K, 0, N - 1);
cout << bTotal << endl;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
376 KB |
Output is correct |
2 |
Correct |
5 ms |
376 KB |
Output is correct |
3 |
Correct |
5 ms |
376 KB |
Output is correct |
4 |
Correct |
5 ms |
376 KB |
Output is correct |
5 |
Correct |
5 ms |
376 KB |
Output is correct |
6 |
Correct |
4 ms |
376 KB |
Output is correct |
7 |
Correct |
5 ms |
376 KB |
Output is correct |
8 |
Correct |
5 ms |
376 KB |
Output is correct |
9 |
Correct |
5 ms |
376 KB |
Output is correct |
10 |
Correct |
5 ms |
376 KB |
Output is correct |
11 |
Correct |
5 ms |
376 KB |
Output is correct |
12 |
Correct |
5 ms |
376 KB |
Output is correct |
13 |
Correct |
5 ms |
376 KB |
Output is correct |
14 |
Correct |
5 ms |
376 KB |
Output is correct |
15 |
Correct |
5 ms |
376 KB |
Output is correct |
16 |
Correct |
5 ms |
376 KB |
Output is correct |
17 |
Correct |
5 ms |
376 KB |
Output is correct |
18 |
Correct |
5 ms |
376 KB |
Output is correct |
19 |
Correct |
5 ms |
376 KB |
Output is correct |
20 |
Correct |
5 ms |
376 KB |
Output is correct |
21 |
Correct |
5 ms |
376 KB |
Output is correct |
22 |
Correct |
5 ms |
376 KB |
Output is correct |
23 |
Correct |
5 ms |
376 KB |
Output is correct |
24 |
Correct |
5 ms |
376 KB |
Output is correct |
25 |
Correct |
5 ms |
376 KB |
Output is correct |
26 |
Correct |
6 ms |
376 KB |
Output is correct |
27 |
Correct |
5 ms |
376 KB |
Output is correct |
28 |
Correct |
5 ms |
376 KB |
Output is correct |
29 |
Correct |
5 ms |
376 KB |
Output is correct |
30 |
Correct |
5 ms |
376 KB |
Output is correct |
31 |
Correct |
5 ms |
376 KB |
Output is correct |
32 |
Correct |
5 ms |
376 KB |
Output is correct |
33 |
Correct |
5 ms |
376 KB |
Output is correct |
34 |
Correct |
5 ms |
376 KB |
Output is correct |
35 |
Correct |
5 ms |
376 KB |
Output is correct |
36 |
Correct |
5 ms |
376 KB |
Output is correct |
37 |
Correct |
5 ms |
380 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
376 KB |
Output is correct |
2 |
Correct |
5 ms |
376 KB |
Output is correct |
3 |
Correct |
5 ms |
376 KB |
Output is correct |
4 |
Correct |
5 ms |
376 KB |
Output is correct |
5 |
Correct |
5 ms |
376 KB |
Output is correct |
6 |
Correct |
4 ms |
376 KB |
Output is correct |
7 |
Correct |
5 ms |
376 KB |
Output is correct |
8 |
Correct |
5 ms |
376 KB |
Output is correct |
9 |
Correct |
5 ms |
376 KB |
Output is correct |
10 |
Correct |
5 ms |
376 KB |
Output is correct |
11 |
Correct |
5 ms |
376 KB |
Output is correct |
12 |
Correct |
5 ms |
376 KB |
Output is correct |
13 |
Correct |
5 ms |
376 KB |
Output is correct |
14 |
Correct |
5 ms |
376 KB |
Output is correct |
15 |
Correct |
5 ms |
376 KB |
Output is correct |
16 |
Correct |
5 ms |
376 KB |
Output is correct |
17 |
Correct |
5 ms |
376 KB |
Output is correct |
18 |
Correct |
5 ms |
376 KB |
Output is correct |
19 |
Correct |
5 ms |
376 KB |
Output is correct |
20 |
Correct |
5 ms |
376 KB |
Output is correct |
21 |
Correct |
5 ms |
376 KB |
Output is correct |
22 |
Correct |
5 ms |
376 KB |
Output is correct |
23 |
Correct |
5 ms |
376 KB |
Output is correct |
24 |
Correct |
5 ms |
376 KB |
Output is correct |
25 |
Correct |
5 ms |
376 KB |
Output is correct |
26 |
Correct |
6 ms |
376 KB |
Output is correct |
27 |
Correct |
5 ms |
376 KB |
Output is correct |
28 |
Correct |
5 ms |
376 KB |
Output is correct |
29 |
Correct |
5 ms |
376 KB |
Output is correct |
30 |
Correct |
5 ms |
376 KB |
Output is correct |
31 |
Correct |
5 ms |
376 KB |
Output is correct |
32 |
Correct |
5 ms |
376 KB |
Output is correct |
33 |
Correct |
5 ms |
376 KB |
Output is correct |
34 |
Correct |
5 ms |
376 KB |
Output is correct |
35 |
Correct |
5 ms |
376 KB |
Output is correct |
36 |
Correct |
5 ms |
376 KB |
Output is correct |
37 |
Correct |
5 ms |
380 KB |
Output is correct |
38 |
Correct |
10 ms |
1400 KB |
Output is correct |
39 |
Correct |
11 ms |
1400 KB |
Output is correct |
40 |
Correct |
10 ms |
1272 KB |
Output is correct |
41 |
Correct |
10 ms |
1144 KB |
Output is correct |
42 |
Correct |
9 ms |
1144 KB |
Output is correct |
43 |
Correct |
9 ms |
1144 KB |
Output is correct |
44 |
Correct |
11 ms |
1272 KB |
Output is correct |
45 |
Correct |
12 ms |
1272 KB |
Output is correct |
46 |
Correct |
11 ms |
1272 KB |
Output is correct |
47 |
Correct |
12 ms |
1272 KB |
Output is correct |
48 |
Correct |
12 ms |
1272 KB |
Output is correct |
49 |
Correct |
11 ms |
1276 KB |
Output is correct |
50 |
Correct |
11 ms |
1272 KB |
Output is correct |
51 |
Correct |
11 ms |
1272 KB |
Output is correct |
52 |
Correct |
10 ms |
1144 KB |
Output is correct |
53 |
Correct |
10 ms |
1144 KB |
Output is correct |
54 |
Correct |
9 ms |
1272 KB |
Output is correct |
55 |
Correct |
9 ms |
1272 KB |
Output is correct |
56 |
Correct |
8 ms |
1144 KB |
Output is correct |
57 |
Correct |
9 ms |
1272 KB |
Output is correct |
58 |
Correct |
9 ms |
1148 KB |
Output is correct |
59 |
Correct |
8 ms |
1016 KB |
Output is correct |
60 |
Correct |
10 ms |
1016 KB |
Output is correct |
61 |
Correct |
9 ms |
1016 KB |
Output is correct |
62 |
Correct |
8 ms |
1016 KB |
Output is correct |
63 |
Correct |
10 ms |
1144 KB |
Output is correct |
64 |
Correct |
9 ms |
888 KB |
Output is correct |
65 |
Correct |
11 ms |
1144 KB |
Output is correct |
66 |
Correct |
10 ms |
1272 KB |
Output is correct |
67 |
Correct |
11 ms |
1400 KB |
Output is correct |
68 |
Correct |
10 ms |
1272 KB |
Output is correct |
69 |
Correct |
10 ms |
1272 KB |
Output is correct |
70 |
Correct |
11 ms |
1272 KB |
Output is correct |
71 |
Correct |
11 ms |
1272 KB |
Output is correct |
72 |
Correct |
10 ms |
1272 KB |
Output is correct |
73 |
Correct |
9 ms |
1272 KB |
Output is correct |
74 |
Correct |
6 ms |
504 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
376 KB |
Output is correct |
2 |
Correct |
5 ms |
376 KB |
Output is correct |
3 |
Correct |
5 ms |
376 KB |
Output is correct |
4 |
Correct |
5 ms |
376 KB |
Output is correct |
5 |
Correct |
5 ms |
376 KB |
Output is correct |
6 |
Correct |
4 ms |
376 KB |
Output is correct |
7 |
Correct |
5 ms |
376 KB |
Output is correct |
8 |
Correct |
5 ms |
376 KB |
Output is correct |
9 |
Correct |
5 ms |
376 KB |
Output is correct |
10 |
Correct |
5 ms |
376 KB |
Output is correct |
11 |
Correct |
5 ms |
376 KB |
Output is correct |
12 |
Correct |
5 ms |
376 KB |
Output is correct |
13 |
Correct |
5 ms |
376 KB |
Output is correct |
14 |
Correct |
5 ms |
376 KB |
Output is correct |
15 |
Correct |
5 ms |
376 KB |
Output is correct |
16 |
Correct |
5 ms |
376 KB |
Output is correct |
17 |
Correct |
5 ms |
376 KB |
Output is correct |
18 |
Correct |
5 ms |
376 KB |
Output is correct |
19 |
Correct |
5 ms |
376 KB |
Output is correct |
20 |
Correct |
5 ms |
376 KB |
Output is correct |
21 |
Correct |
5 ms |
376 KB |
Output is correct |
22 |
Correct |
5 ms |
376 KB |
Output is correct |
23 |
Correct |
5 ms |
376 KB |
Output is correct |
24 |
Correct |
5 ms |
376 KB |
Output is correct |
25 |
Correct |
5 ms |
376 KB |
Output is correct |
26 |
Correct |
6 ms |
376 KB |
Output is correct |
27 |
Correct |
5 ms |
376 KB |
Output is correct |
28 |
Correct |
5 ms |
376 KB |
Output is correct |
29 |
Correct |
5 ms |
376 KB |
Output is correct |
30 |
Correct |
5 ms |
376 KB |
Output is correct |
31 |
Correct |
5 ms |
376 KB |
Output is correct |
32 |
Correct |
5 ms |
376 KB |
Output is correct |
33 |
Correct |
5 ms |
376 KB |
Output is correct |
34 |
Correct |
5 ms |
376 KB |
Output is correct |
35 |
Correct |
5 ms |
376 KB |
Output is correct |
36 |
Correct |
5 ms |
376 KB |
Output is correct |
37 |
Correct |
5 ms |
380 KB |
Output is correct |
38 |
Correct |
10 ms |
1400 KB |
Output is correct |
39 |
Correct |
11 ms |
1400 KB |
Output is correct |
40 |
Correct |
10 ms |
1272 KB |
Output is correct |
41 |
Correct |
10 ms |
1144 KB |
Output is correct |
42 |
Correct |
9 ms |
1144 KB |
Output is correct |
43 |
Correct |
9 ms |
1144 KB |
Output is correct |
44 |
Correct |
11 ms |
1272 KB |
Output is correct |
45 |
Correct |
12 ms |
1272 KB |
Output is correct |
46 |
Correct |
11 ms |
1272 KB |
Output is correct |
47 |
Correct |
12 ms |
1272 KB |
Output is correct |
48 |
Correct |
12 ms |
1272 KB |
Output is correct |
49 |
Correct |
11 ms |
1276 KB |
Output is correct |
50 |
Correct |
11 ms |
1272 KB |
Output is correct |
51 |
Correct |
11 ms |
1272 KB |
Output is correct |
52 |
Correct |
10 ms |
1144 KB |
Output is correct |
53 |
Correct |
10 ms |
1144 KB |
Output is correct |
54 |
Correct |
9 ms |
1272 KB |
Output is correct |
55 |
Correct |
9 ms |
1272 KB |
Output is correct |
56 |
Correct |
8 ms |
1144 KB |
Output is correct |
57 |
Correct |
9 ms |
1272 KB |
Output is correct |
58 |
Correct |
9 ms |
1148 KB |
Output is correct |
59 |
Correct |
8 ms |
1016 KB |
Output is correct |
60 |
Correct |
10 ms |
1016 KB |
Output is correct |
61 |
Correct |
9 ms |
1016 KB |
Output is correct |
62 |
Correct |
8 ms |
1016 KB |
Output is correct |
63 |
Correct |
10 ms |
1144 KB |
Output is correct |
64 |
Correct |
9 ms |
888 KB |
Output is correct |
65 |
Correct |
11 ms |
1144 KB |
Output is correct |
66 |
Correct |
10 ms |
1272 KB |
Output is correct |
67 |
Correct |
11 ms |
1400 KB |
Output is correct |
68 |
Correct |
10 ms |
1272 KB |
Output is correct |
69 |
Correct |
10 ms |
1272 KB |
Output is correct |
70 |
Correct |
11 ms |
1272 KB |
Output is correct |
71 |
Correct |
11 ms |
1272 KB |
Output is correct |
72 |
Correct |
10 ms |
1272 KB |
Output is correct |
73 |
Correct |
9 ms |
1272 KB |
Output is correct |
74 |
Correct |
6 ms |
504 KB |
Output is correct |
75 |
Correct |
1398 ms |
135832 KB |
Output is correct |
76 |
Correct |
1506 ms |
126048 KB |
Output is correct |
77 |
Correct |
1278 ms |
141792 KB |
Output is correct |
78 |
Correct |
1358 ms |
142304 KB |
Output is correct |
79 |
Correct |
546 ms |
72040 KB |
Output is correct |
80 |
Correct |
758 ms |
100960 KB |
Output is correct |
81 |
Correct |
1445 ms |
118468 KB |
Output is correct |
82 |
Correct |
1610 ms |
124048 KB |
Output is correct |
83 |
Correct |
1619 ms |
134664 KB |
Output is correct |
84 |
Correct |
1651 ms |
130696 KB |
Output is correct |
85 |
Correct |
1494 ms |
119620 KB |
Output is correct |
86 |
Correct |
1071 ms |
139748 KB |
Output is correct |
87 |
Correct |
1087 ms |
134496 KB |
Output is correct |
88 |
Correct |
1355 ms |
115776 KB |
Output is correct |
89 |
Correct |
1344 ms |
136672 KB |
Output is correct |
90 |
Correct |
1147 ms |
141784 KB |
Output is correct |
91 |
Correct |
981 ms |
113676 KB |
Output is correct |
92 |
Correct |
939 ms |
127840 KB |
Output is correct |
93 |
Correct |
1054 ms |
140500 KB |
Output is correct |
94 |
Correct |
1071 ms |
123792 KB |
Output is correct |
95 |
Correct |
1140 ms |
143968 KB |
Output is correct |
96 |
Correct |
806 ms |
63868 KB |
Output is correct |
97 |
Correct |
849 ms |
72288 KB |
Output is correct |
98 |
Correct |
895 ms |
74588 KB |
Output is correct |
99 |
Correct |
836 ms |
75872 KB |
Output is correct |
100 |
Correct |
777 ms |
80488 KB |
Output is correct |
101 |
Correct |
778 ms |
78048 KB |
Output is correct |
102 |
Correct |
1468 ms |
127732 KB |
Output is correct |
103 |
Correct |
1379 ms |
114472 KB |
Output is correct |
104 |
Correct |
1607 ms |
123624 KB |
Output is correct |
105 |
Correct |
1370 ms |
135272 KB |
Output is correct |
106 |
Correct |
1356 ms |
140128 KB |
Output is correct |
107 |
Correct |
1281 ms |
134496 KB |
Output is correct |
108 |
Correct |
1272 ms |
142432 KB |
Output is correct |
109 |
Correct |
1216 ms |
137968 KB |
Output is correct |
110 |
Correct |
998 ms |
139744 KB |
Output is correct |
111 |
Correct |
1132 ms |
132348 KB |
Output is correct |
112 |
Correct |
799 ms |
105188 KB |
Output is correct |
113 |
Correct |
133 ms |
18912 KB |
Output is correct |