#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, m;
ll ans = -1e15;
pair<ll, ll> a[200010];
struct Node
{
ll val, am, left, right;
};
Node rangetree[10000000];
int upto;
int roots[200010];
void update(ll node, int curr, int oldcurr, int cstart = 0, int cend = 1e9+1)
{
if (cstart == cend)
{
rangetree[curr].val = rangetree[oldcurr].val + node;
rangetree[curr].am = rangetree[oldcurr].am + 1;
return;
}
int mid = (cstart+cend)/2;
if (node <= mid)
{
rangetree[curr].right = rangetree[oldcurr].right;
rangetree[curr].left = ++upto;
update(node, rangetree[curr].left, rangetree[oldcurr].left, cstart, mid);
}
else
{
rangetree[curr].left = rangetree[oldcurr].left;
rangetree[curr].right = ++upto;
update(node, rangetree[curr].right, rangetree[oldcurr].right, mid+1, cend);
}
rangetree[curr].val = rangetree[rangetree[curr].left].val + rangetree[rangetree[curr].right].val;
rangetree[curr].am = rangetree[rangetree[curr].left].am + rangetree[rangetree[curr].right].am;
}
ll treewalk(ll am, int curr, int oldcurr, int cstart = 0, int cend = 1e9+1)
{
if (cstart == cend)
{
return am * (ll)cstart;
}
int mid = (cstart+cend)/2;
if (rangetree[rangetree[curr].right].am-rangetree[rangetree[oldcurr].right].am >= am)
{
return treewalk(am, rangetree[curr].right, rangetree[oldcurr].right, mid+1, cend);
}
else
{
am -= rangetree[rangetree[curr].right].am-rangetree[rangetree[oldcurr].right].am;
return treewalk(am, rangetree[curr].left, rangetree[oldcurr].left, cstart, mid) + rangetree[rangetree[curr].right].val-rangetree[rangetree[oldcurr].right].val;
}
}
void dank(int s, int e, int ks, int ke)
{
if (e < s) return;
int b = (s+e)/2;
ll bestans = -1e15;
ll best = ke;
// printf("%d - %d %d\n", b, ks, ke);
for (int i = ks; i <= ke; i++)
{
ll am = -1e15;
if (i-b+1 >= m)
{
int oldroot = b == 0 ? 0 : roots[b-1];
am = treewalk(m, roots[i], oldroot);
am -= 2*a[i].first;
am += 2*a[b].first;
if (am > bestans)
{
bestans = am;
best = i;
}
}
}
// printf("best %lld (%lld)\n", best, bestans);
ans = max(ans, bestans);
dank(s, b-1, ks, best);
dank(b+1, e, best, ke);
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i++)
{
scanf("%lld%lld", &a[i].second, &a[i].first);
}
sort(a, a+n);
for (int i = 0; i < n; i++)
{
int oldroot = i == 0 ? 0 : roots[i-1];
roots[i] = ++upto;
update(a[i].second, roots[i], oldroot);
}
dank(0, n-1, 0, n-1);
printf("%lld\n", ans);
}
Compilation message
cake3.cpp: In function 'int main()':
cake3.cpp:85:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &n, &m);
~~~~~^~~~~~~~~~~~~~~~
cake3.cpp:88:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld", &a[i].second, &a[i].first);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
512 KB |
Output is correct |
2 |
Correct |
2 ms |
484 KB |
Output is correct |
3 |
Correct |
2 ms |
512 KB |
Output is correct |
4 |
Correct |
3 ms |
384 KB |
Output is correct |
5 |
Correct |
2 ms |
384 KB |
Output is correct |
6 |
Correct |
2 ms |
512 KB |
Output is correct |
7 |
Correct |
3 ms |
512 KB |
Output is correct |
8 |
Correct |
2 ms |
384 KB |
Output is correct |
9 |
Correct |
2 ms |
512 KB |
Output is correct |
10 |
Correct |
2 ms |
384 KB |
Output is correct |
11 |
Correct |
2 ms |
484 KB |
Output is correct |
12 |
Correct |
3 ms |
512 KB |
Output is correct |
13 |
Correct |
2 ms |
512 KB |
Output is correct |
14 |
Correct |
2 ms |
384 KB |
Output is correct |
15 |
Correct |
2 ms |
512 KB |
Output is correct |
16 |
Correct |
3 ms |
384 KB |
Output is correct |
17 |
Correct |
2 ms |
512 KB |
Output is correct |
18 |
Correct |
2 ms |
512 KB |
Output is correct |
19 |
Correct |
2 ms |
512 KB |
Output is correct |
20 |
Correct |
2 ms |
384 KB |
Output is correct |
21 |
Correct |
2 ms |
384 KB |
Output is correct |
22 |
Correct |
2 ms |
512 KB |
Output is correct |
23 |
Correct |
2 ms |
512 KB |
Output is correct |
24 |
Correct |
2 ms |
512 KB |
Output is correct |
25 |
Correct |
3 ms |
512 KB |
Output is correct |
26 |
Correct |
2 ms |
384 KB |
Output is correct |
27 |
Correct |
3 ms |
512 KB |
Output is correct |
28 |
Correct |
2 ms |
384 KB |
Output is correct |
29 |
Correct |
2 ms |
384 KB |
Output is correct |
30 |
Correct |
3 ms |
512 KB |
Output is correct |
31 |
Correct |
2 ms |
384 KB |
Output is correct |
32 |
Correct |
3 ms |
384 KB |
Output is correct |
33 |
Correct |
3 ms |
384 KB |
Output is correct |
34 |
Correct |
2 ms |
512 KB |
Output is correct |
35 |
Correct |
3 ms |
384 KB |
Output is correct |
36 |
Correct |
3 ms |
512 KB |
Output is correct |
37 |
Correct |
3 ms |
512 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
512 KB |
Output is correct |
2 |
Correct |
2 ms |
484 KB |
Output is correct |
3 |
Correct |
2 ms |
512 KB |
Output is correct |
4 |
Correct |
3 ms |
384 KB |
Output is correct |
5 |
Correct |
2 ms |
384 KB |
Output is correct |
6 |
Correct |
2 ms |
512 KB |
Output is correct |
7 |
Correct |
3 ms |
512 KB |
Output is correct |
8 |
Correct |
2 ms |
384 KB |
Output is correct |
9 |
Correct |
2 ms |
512 KB |
Output is correct |
10 |
Correct |
2 ms |
384 KB |
Output is correct |
11 |
Correct |
2 ms |
484 KB |
Output is correct |
12 |
Correct |
3 ms |
512 KB |
Output is correct |
13 |
Correct |
2 ms |
512 KB |
Output is correct |
14 |
Correct |
2 ms |
384 KB |
Output is correct |
15 |
Correct |
2 ms |
512 KB |
Output is correct |
16 |
Correct |
3 ms |
384 KB |
Output is correct |
17 |
Correct |
2 ms |
512 KB |
Output is correct |
18 |
Correct |
2 ms |
512 KB |
Output is correct |
19 |
Correct |
2 ms |
512 KB |
Output is correct |
20 |
Correct |
2 ms |
384 KB |
Output is correct |
21 |
Correct |
2 ms |
384 KB |
Output is correct |
22 |
Correct |
2 ms |
512 KB |
Output is correct |
23 |
Correct |
2 ms |
512 KB |
Output is correct |
24 |
Correct |
2 ms |
512 KB |
Output is correct |
25 |
Correct |
3 ms |
512 KB |
Output is correct |
26 |
Correct |
2 ms |
384 KB |
Output is correct |
27 |
Correct |
3 ms |
512 KB |
Output is correct |
28 |
Correct |
2 ms |
384 KB |
Output is correct |
29 |
Correct |
2 ms |
384 KB |
Output is correct |
30 |
Correct |
3 ms |
512 KB |
Output is correct |
31 |
Correct |
2 ms |
384 KB |
Output is correct |
32 |
Correct |
3 ms |
384 KB |
Output is correct |
33 |
Correct |
3 ms |
384 KB |
Output is correct |
34 |
Correct |
2 ms |
512 KB |
Output is correct |
35 |
Correct |
3 ms |
384 KB |
Output is correct |
36 |
Correct |
3 ms |
512 KB |
Output is correct |
37 |
Correct |
3 ms |
512 KB |
Output is correct |
38 |
Correct |
10 ms |
2176 KB |
Output is correct |
39 |
Correct |
11 ms |
2180 KB |
Output is correct |
40 |
Correct |
8 ms |
2176 KB |
Output is correct |
41 |
Correct |
8 ms |
2176 KB |
Output is correct |
42 |
Correct |
8 ms |
2304 KB |
Output is correct |
43 |
Correct |
10 ms |
2176 KB |
Output is correct |
44 |
Correct |
10 ms |
2176 KB |
Output is correct |
45 |
Correct |
8 ms |
2276 KB |
Output is correct |
46 |
Correct |
11 ms |
2304 KB |
Output is correct |
47 |
Correct |
9 ms |
2304 KB |
Output is correct |
48 |
Correct |
10 ms |
2176 KB |
Output is correct |
49 |
Correct |
8 ms |
2304 KB |
Output is correct |
50 |
Correct |
9 ms |
2304 KB |
Output is correct |
51 |
Correct |
8 ms |
2304 KB |
Output is correct |
52 |
Correct |
9 ms |
2176 KB |
Output is correct |
53 |
Correct |
6 ms |
2176 KB |
Output is correct |
54 |
Correct |
8 ms |
2304 KB |
Output is correct |
55 |
Correct |
7 ms |
2276 KB |
Output is correct |
56 |
Correct |
6 ms |
2176 KB |
Output is correct |
57 |
Correct |
6 ms |
2176 KB |
Output is correct |
58 |
Correct |
8 ms |
2176 KB |
Output is correct |
59 |
Correct |
5 ms |
2176 KB |
Output is correct |
60 |
Correct |
7 ms |
2304 KB |
Output is correct |
61 |
Correct |
6 ms |
2176 KB |
Output is correct |
62 |
Correct |
6 ms |
2304 KB |
Output is correct |
63 |
Correct |
6 ms |
2304 KB |
Output is correct |
64 |
Correct |
7 ms |
2304 KB |
Output is correct |
65 |
Correct |
6 ms |
2176 KB |
Output is correct |
66 |
Correct |
7 ms |
2224 KB |
Output is correct |
67 |
Correct |
10 ms |
2176 KB |
Output is correct |
68 |
Correct |
8 ms |
2304 KB |
Output is correct |
69 |
Correct |
7 ms |
2220 KB |
Output is correct |
70 |
Correct |
7 ms |
2176 KB |
Output is correct |
71 |
Correct |
4 ms |
2164 KB |
Output is correct |
72 |
Correct |
6 ms |
2304 KB |
Output is correct |
73 |
Correct |
10 ms |
2176 KB |
Output is correct |
74 |
Correct |
6 ms |
2304 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
512 KB |
Output is correct |
2 |
Correct |
2 ms |
484 KB |
Output is correct |
3 |
Correct |
2 ms |
512 KB |
Output is correct |
4 |
Correct |
3 ms |
384 KB |
Output is correct |
5 |
Correct |
2 ms |
384 KB |
Output is correct |
6 |
Correct |
2 ms |
512 KB |
Output is correct |
7 |
Correct |
3 ms |
512 KB |
Output is correct |
8 |
Correct |
2 ms |
384 KB |
Output is correct |
9 |
Correct |
2 ms |
512 KB |
Output is correct |
10 |
Correct |
2 ms |
384 KB |
Output is correct |
11 |
Correct |
2 ms |
484 KB |
Output is correct |
12 |
Correct |
3 ms |
512 KB |
Output is correct |
13 |
Correct |
2 ms |
512 KB |
Output is correct |
14 |
Correct |
2 ms |
384 KB |
Output is correct |
15 |
Correct |
2 ms |
512 KB |
Output is correct |
16 |
Correct |
3 ms |
384 KB |
Output is correct |
17 |
Correct |
2 ms |
512 KB |
Output is correct |
18 |
Correct |
2 ms |
512 KB |
Output is correct |
19 |
Correct |
2 ms |
512 KB |
Output is correct |
20 |
Correct |
2 ms |
384 KB |
Output is correct |
21 |
Correct |
2 ms |
384 KB |
Output is correct |
22 |
Correct |
2 ms |
512 KB |
Output is correct |
23 |
Correct |
2 ms |
512 KB |
Output is correct |
24 |
Correct |
2 ms |
512 KB |
Output is correct |
25 |
Correct |
3 ms |
512 KB |
Output is correct |
26 |
Correct |
2 ms |
384 KB |
Output is correct |
27 |
Correct |
3 ms |
512 KB |
Output is correct |
28 |
Correct |
2 ms |
384 KB |
Output is correct |
29 |
Correct |
2 ms |
384 KB |
Output is correct |
30 |
Correct |
3 ms |
512 KB |
Output is correct |
31 |
Correct |
2 ms |
384 KB |
Output is correct |
32 |
Correct |
3 ms |
384 KB |
Output is correct |
33 |
Correct |
3 ms |
384 KB |
Output is correct |
34 |
Correct |
2 ms |
512 KB |
Output is correct |
35 |
Correct |
3 ms |
384 KB |
Output is correct |
36 |
Correct |
3 ms |
512 KB |
Output is correct |
37 |
Correct |
3 ms |
512 KB |
Output is correct |
38 |
Correct |
10 ms |
2176 KB |
Output is correct |
39 |
Correct |
11 ms |
2180 KB |
Output is correct |
40 |
Correct |
8 ms |
2176 KB |
Output is correct |
41 |
Correct |
8 ms |
2176 KB |
Output is correct |
42 |
Correct |
8 ms |
2304 KB |
Output is correct |
43 |
Correct |
10 ms |
2176 KB |
Output is correct |
44 |
Correct |
10 ms |
2176 KB |
Output is correct |
45 |
Correct |
8 ms |
2276 KB |
Output is correct |
46 |
Correct |
11 ms |
2304 KB |
Output is correct |
47 |
Correct |
9 ms |
2304 KB |
Output is correct |
48 |
Correct |
10 ms |
2176 KB |
Output is correct |
49 |
Correct |
8 ms |
2304 KB |
Output is correct |
50 |
Correct |
9 ms |
2304 KB |
Output is correct |
51 |
Correct |
8 ms |
2304 KB |
Output is correct |
52 |
Correct |
9 ms |
2176 KB |
Output is correct |
53 |
Correct |
6 ms |
2176 KB |
Output is correct |
54 |
Correct |
8 ms |
2304 KB |
Output is correct |
55 |
Correct |
7 ms |
2276 KB |
Output is correct |
56 |
Correct |
6 ms |
2176 KB |
Output is correct |
57 |
Correct |
6 ms |
2176 KB |
Output is correct |
58 |
Correct |
8 ms |
2176 KB |
Output is correct |
59 |
Correct |
5 ms |
2176 KB |
Output is correct |
60 |
Correct |
7 ms |
2304 KB |
Output is correct |
61 |
Correct |
6 ms |
2176 KB |
Output is correct |
62 |
Correct |
6 ms |
2304 KB |
Output is correct |
63 |
Correct |
6 ms |
2304 KB |
Output is correct |
64 |
Correct |
7 ms |
2304 KB |
Output is correct |
65 |
Correct |
6 ms |
2176 KB |
Output is correct |
66 |
Correct |
7 ms |
2224 KB |
Output is correct |
67 |
Correct |
10 ms |
2176 KB |
Output is correct |
68 |
Correct |
8 ms |
2304 KB |
Output is correct |
69 |
Correct |
7 ms |
2220 KB |
Output is correct |
70 |
Correct |
7 ms |
2176 KB |
Output is correct |
71 |
Correct |
4 ms |
2164 KB |
Output is correct |
72 |
Correct |
6 ms |
2304 KB |
Output is correct |
73 |
Correct |
10 ms |
2176 KB |
Output is correct |
74 |
Correct |
6 ms |
2304 KB |
Output is correct |
75 |
Correct |
2214 ms |
184460 KB |
Output is correct |
76 |
Correct |
2252 ms |
179440 KB |
Output is correct |
77 |
Correct |
2036 ms |
184904 KB |
Output is correct |
78 |
Correct |
2124 ms |
187640 KB |
Output is correct |
79 |
Correct |
491 ms |
188384 KB |
Output is correct |
80 |
Correct |
639 ms |
182904 KB |
Output is correct |
81 |
Correct |
1048 ms |
186592 KB |
Output is correct |
82 |
Correct |
1318 ms |
188920 KB |
Output is correct |
83 |
Correct |
1032 ms |
195192 KB |
Output is correct |
84 |
Correct |
1176 ms |
194604 KB |
Output is correct |
85 |
Correct |
1110 ms |
188152 KB |
Output is correct |
86 |
Correct |
570 ms |
181880 KB |
Output is correct |
87 |
Correct |
649 ms |
179448 KB |
Output is correct |
88 |
Correct |
898 ms |
178168 KB |
Output is correct |
89 |
Correct |
821 ms |
188192 KB |
Output is correct |
90 |
Correct |
632 ms |
196704 KB |
Output is correct |
91 |
Correct |
446 ms |
182060 KB |
Output is correct |
92 |
Correct |
487 ms |
180856 KB |
Output is correct |
93 |
Correct |
545 ms |
188264 KB |
Output is correct |
94 |
Correct |
493 ms |
196592 KB |
Output is correct |
95 |
Correct |
574 ms |
196992 KB |
Output is correct |
96 |
Correct |
466 ms |
183448 KB |
Output is correct |
97 |
Correct |
489 ms |
197872 KB |
Output is correct |
98 |
Correct |
481 ms |
195084 KB |
Output is correct |
99 |
Correct |
490 ms |
195588 KB |
Output is correct |
100 |
Correct |
426 ms |
184244 KB |
Output is correct |
101 |
Correct |
420 ms |
184440 KB |
Output is correct |
102 |
Correct |
795 ms |
183920 KB |
Output is correct |
103 |
Correct |
855 ms |
181536 KB |
Output is correct |
104 |
Correct |
1076 ms |
191432 KB |
Output is correct |
105 |
Correct |
761 ms |
190656 KB |
Output is correct |
106 |
Correct |
723 ms |
195732 KB |
Output is correct |
107 |
Correct |
643 ms |
188884 KB |
Output is correct |
108 |
Correct |
1961 ms |
186772 KB |
Output is correct |
109 |
Correct |
1615 ms |
197944 KB |
Output is correct |
110 |
Correct |
479 ms |
185436 KB |
Output is correct |
111 |
Correct |
562 ms |
187768 KB |
Output is correct |
112 |
Correct |
1544 ms |
178720 KB |
Output is correct |
113 |
Correct |
498 ms |
197880 KB |
Output is correct |