# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
105389 |
2019-04-11T18:54:35 Z |
reality |
Cake 3 (JOI19_cake3) |
C++17 |
|
1689 ms |
206328 KB |
#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
#define ll long long
#define dbg(v) cerr<<#v<<" = "<<v<<'\n'
#define vi vector<int>
#define vl vector <ll>
#define pii pair<int,int>
#define vii vector < pii >
#define mp make_pair
#define db long double
#define pb push_back
#define all(s) s.begin(),s.end()
template < class P , class Q > ostream& operator<<(ostream& stream, pair < P , Q > v){ stream << "(" << v.fi << ',' << v.se << ")"; return stream;}
template < class T > ostream& operator<<(ostream& stream, const vector<T> v){ stream << "[ "; for (int i=0; i<(int)v.size(); i++) stream << v[i] << " "; stream << "]"; return stream;}
template < class T > T smin(T &a,T b) {if (a > b) a = b;return a;}
template < class T > T smax(T &a,T b) {if (a < b) a = b;return a;}
const int N = 1e6 + 5;
pair < ll , ll > s[N];
ll v[N];
ll ans = -1e18;
struct Nod {
Nod * l, * r;
int cnt;
ll sum;
Nod(void) {
l = r = 0;
cnt = 0;
sum = 0;
}
Nod(int pos) {
cnt = 1;
sum = v[pos];
l = r = 0;
}
Nod(Nod *L,Nod *R) {
l = L;
r = R;
cnt = l->cnt + r->cnt;
sum = l->sum + r->sum;
}
};
typedef Nod * Node;
Node T[N];
Node build(int l,int r) {
if (l == r)
return new Nod();
int m = (l + r) / 2;
return new Nod(build(l,m),build(m+1,r));
}
Node update(int l,int r,int pos,Node Root) {
if (l == r)
return new Nod(pos);
int m = (l + r) / 2;
if (pos <= m)
return new Nod(update(l,m,pos,Root->l),Root->r);
else
return new Nod(Root->l,update(m+1,r,pos,Root->r));
}
ll query(int need,Node Root1,Node Root2) {
if (Root1->cnt - Root2->cnt == need)
return Root1->sum - Root2->sum;
if (Root1->l->cnt - Root2->l->cnt >= need)
return query(need,Root1->l,Root2->l);
else
return query(need - (Root1->l->cnt - Root2->l->cnt),Root1->r,Root2->r) + Root1->l->sum - Root2->l->sum;
}
int m;
void Go(int l1,int r1,int l2,int r2) {
if (l1 > r1 || l2 > r2)
return;
int m1 = (l1 + r1) / 2;
pair < ll , int > bst = mp((ll)(-1e18),r2);
for (int i = max(l2,m1 + m - 1);i <= r2;++i)
smax(bst,mp(query(m,T[i],T[m1 - 1]) + s[m1].se - s[i].se,i));
smax(ans,bst.fi);
Go(l1,m1 - 1,l2,bst.se);
Go(m1 + 1,r1,bst.se,r2);
}
int p[N];
int q[N];
int main(void) {
int n;
cin>>n>>m;
for (int i = 1;i <= n;++i)
cin>>s[i].fi>>s[i].se,s[i].se *= 2,p[i] = i,v[i] = s[i].fi;
sort(s + 1,s + 1 + n,[&](auto a,auto b) {
return a.se < b.se;
});
sort(p + 1,p + 1 + n,[&](int x,int y) {
return s[x].fi > s[y].fi;
});
sort(v + 1,v + 1 + n,greater < ll > ());
for (int i = 1;i <= n;++i)
q[p[i]] = i;
T[0] = build(1,n);
for (int i = 1;i <= n;++i) {
T[i] = update(1,n,q[i],T[i - 1]);
}
Go(1,n,1,n);
cout << ans << '\n';
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
3 ms |
384 KB |
Output is correct |
3 |
Correct |
2 ms |
384 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 |
384 KB |
Output is correct |
7 |
Correct |
2 ms |
384 KB |
Output is correct |
8 |
Correct |
2 ms |
384 KB |
Output is correct |
9 |
Correct |
2 ms |
384 KB |
Output is correct |
10 |
Correct |
2 ms |
384 KB |
Output is correct |
11 |
Correct |
3 ms |
384 KB |
Output is correct |
12 |
Correct |
2 ms |
384 KB |
Output is correct |
13 |
Correct |
3 ms |
384 KB |
Output is correct |
14 |
Correct |
2 ms |
384 KB |
Output is correct |
15 |
Correct |
2 ms |
384 KB |
Output is correct |
16 |
Correct |
3 ms |
384 KB |
Output is correct |
17 |
Correct |
3 ms |
384 KB |
Output is correct |
18 |
Correct |
2 ms |
384 KB |
Output is correct |
19 |
Correct |
2 ms |
384 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 |
384 KB |
Output is correct |
23 |
Correct |
3 ms |
384 KB |
Output is correct |
24 |
Correct |
2 ms |
384 KB |
Output is correct |
25 |
Correct |
2 ms |
384 KB |
Output is correct |
26 |
Correct |
2 ms |
384 KB |
Output is correct |
27 |
Correct |
3 ms |
384 KB |
Output is correct |
28 |
Correct |
2 ms |
384 KB |
Output is correct |
29 |
Correct |
2 ms |
384 KB |
Output is correct |
30 |
Correct |
2 ms |
384 KB |
Output is correct |
31 |
Correct |
2 ms |
384 KB |
Output is correct |
32 |
Correct |
2 ms |
384 KB |
Output is correct |
33 |
Correct |
2 ms |
384 KB |
Output is correct |
34 |
Correct |
3 ms |
384 KB |
Output is correct |
35 |
Correct |
2 ms |
384 KB |
Output is correct |
36 |
Correct |
2 ms |
384 KB |
Output is correct |
37 |
Correct |
2 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
3 ms |
384 KB |
Output is correct |
3 |
Correct |
2 ms |
384 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 |
384 KB |
Output is correct |
7 |
Correct |
2 ms |
384 KB |
Output is correct |
8 |
Correct |
2 ms |
384 KB |
Output is correct |
9 |
Correct |
2 ms |
384 KB |
Output is correct |
10 |
Correct |
2 ms |
384 KB |
Output is correct |
11 |
Correct |
3 ms |
384 KB |
Output is correct |
12 |
Correct |
2 ms |
384 KB |
Output is correct |
13 |
Correct |
3 ms |
384 KB |
Output is correct |
14 |
Correct |
2 ms |
384 KB |
Output is correct |
15 |
Correct |
2 ms |
384 KB |
Output is correct |
16 |
Correct |
3 ms |
384 KB |
Output is correct |
17 |
Correct |
3 ms |
384 KB |
Output is correct |
18 |
Correct |
2 ms |
384 KB |
Output is correct |
19 |
Correct |
2 ms |
384 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 |
384 KB |
Output is correct |
23 |
Correct |
3 ms |
384 KB |
Output is correct |
24 |
Correct |
2 ms |
384 KB |
Output is correct |
25 |
Correct |
2 ms |
384 KB |
Output is correct |
26 |
Correct |
2 ms |
384 KB |
Output is correct |
27 |
Correct |
3 ms |
384 KB |
Output is correct |
28 |
Correct |
2 ms |
384 KB |
Output is correct |
29 |
Correct |
2 ms |
384 KB |
Output is correct |
30 |
Correct |
2 ms |
384 KB |
Output is correct |
31 |
Correct |
2 ms |
384 KB |
Output is correct |
32 |
Correct |
2 ms |
384 KB |
Output is correct |
33 |
Correct |
2 ms |
384 KB |
Output is correct |
34 |
Correct |
3 ms |
384 KB |
Output is correct |
35 |
Correct |
2 ms |
384 KB |
Output is correct |
36 |
Correct |
2 ms |
384 KB |
Output is correct |
37 |
Correct |
2 ms |
384 KB |
Output is correct |
38 |
Correct |
10 ms |
1664 KB |
Output is correct |
39 |
Correct |
9 ms |
1792 KB |
Output is correct |
40 |
Correct |
8 ms |
1664 KB |
Output is correct |
41 |
Correct |
7 ms |
1792 KB |
Output is correct |
42 |
Correct |
6 ms |
1664 KB |
Output is correct |
43 |
Correct |
8 ms |
1664 KB |
Output is correct |
44 |
Correct |
7 ms |
1664 KB |
Output is correct |
45 |
Correct |
7 ms |
1664 KB |
Output is correct |
46 |
Correct |
6 ms |
1792 KB |
Output is correct |
47 |
Correct |
7 ms |
1664 KB |
Output is correct |
48 |
Correct |
7 ms |
1664 KB |
Output is correct |
49 |
Correct |
8 ms |
1792 KB |
Output is correct |
50 |
Correct |
6 ms |
1664 KB |
Output is correct |
51 |
Correct |
9 ms |
1664 KB |
Output is correct |
52 |
Correct |
6 ms |
1664 KB |
Output is correct |
53 |
Correct |
9 ms |
1664 KB |
Output is correct |
54 |
Correct |
6 ms |
1792 KB |
Output is correct |
55 |
Correct |
6 ms |
1664 KB |
Output is correct |
56 |
Correct |
6 ms |
1608 KB |
Output is correct |
57 |
Correct |
6 ms |
1664 KB |
Output is correct |
58 |
Correct |
6 ms |
1688 KB |
Output is correct |
59 |
Correct |
8 ms |
1664 KB |
Output is correct |
60 |
Correct |
8 ms |
1664 KB |
Output is correct |
61 |
Correct |
8 ms |
1664 KB |
Output is correct |
62 |
Correct |
7 ms |
1764 KB |
Output is correct |
63 |
Correct |
7 ms |
1792 KB |
Output is correct |
64 |
Correct |
7 ms |
1656 KB |
Output is correct |
65 |
Correct |
7 ms |
1664 KB |
Output is correct |
66 |
Correct |
7 ms |
1664 KB |
Output is correct |
67 |
Correct |
7 ms |
1792 KB |
Output is correct |
68 |
Correct |
8 ms |
1792 KB |
Output is correct |
69 |
Correct |
8 ms |
1664 KB |
Output is correct |
70 |
Correct |
6 ms |
1664 KB |
Output is correct |
71 |
Correct |
5 ms |
1664 KB |
Output is correct |
72 |
Correct |
5 ms |
1792 KB |
Output is correct |
73 |
Correct |
30 ms |
1664 KB |
Output is correct |
74 |
Correct |
7 ms |
1792 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
3 ms |
384 KB |
Output is correct |
3 |
Correct |
2 ms |
384 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 |
384 KB |
Output is correct |
7 |
Correct |
2 ms |
384 KB |
Output is correct |
8 |
Correct |
2 ms |
384 KB |
Output is correct |
9 |
Correct |
2 ms |
384 KB |
Output is correct |
10 |
Correct |
2 ms |
384 KB |
Output is correct |
11 |
Correct |
3 ms |
384 KB |
Output is correct |
12 |
Correct |
2 ms |
384 KB |
Output is correct |
13 |
Correct |
3 ms |
384 KB |
Output is correct |
14 |
Correct |
2 ms |
384 KB |
Output is correct |
15 |
Correct |
2 ms |
384 KB |
Output is correct |
16 |
Correct |
3 ms |
384 KB |
Output is correct |
17 |
Correct |
3 ms |
384 KB |
Output is correct |
18 |
Correct |
2 ms |
384 KB |
Output is correct |
19 |
Correct |
2 ms |
384 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 |
384 KB |
Output is correct |
23 |
Correct |
3 ms |
384 KB |
Output is correct |
24 |
Correct |
2 ms |
384 KB |
Output is correct |
25 |
Correct |
2 ms |
384 KB |
Output is correct |
26 |
Correct |
2 ms |
384 KB |
Output is correct |
27 |
Correct |
3 ms |
384 KB |
Output is correct |
28 |
Correct |
2 ms |
384 KB |
Output is correct |
29 |
Correct |
2 ms |
384 KB |
Output is correct |
30 |
Correct |
2 ms |
384 KB |
Output is correct |
31 |
Correct |
2 ms |
384 KB |
Output is correct |
32 |
Correct |
2 ms |
384 KB |
Output is correct |
33 |
Correct |
2 ms |
384 KB |
Output is correct |
34 |
Correct |
3 ms |
384 KB |
Output is correct |
35 |
Correct |
2 ms |
384 KB |
Output is correct |
36 |
Correct |
2 ms |
384 KB |
Output is correct |
37 |
Correct |
2 ms |
384 KB |
Output is correct |
38 |
Correct |
10 ms |
1664 KB |
Output is correct |
39 |
Correct |
9 ms |
1792 KB |
Output is correct |
40 |
Correct |
8 ms |
1664 KB |
Output is correct |
41 |
Correct |
7 ms |
1792 KB |
Output is correct |
42 |
Correct |
6 ms |
1664 KB |
Output is correct |
43 |
Correct |
8 ms |
1664 KB |
Output is correct |
44 |
Correct |
7 ms |
1664 KB |
Output is correct |
45 |
Correct |
7 ms |
1664 KB |
Output is correct |
46 |
Correct |
6 ms |
1792 KB |
Output is correct |
47 |
Correct |
7 ms |
1664 KB |
Output is correct |
48 |
Correct |
7 ms |
1664 KB |
Output is correct |
49 |
Correct |
8 ms |
1792 KB |
Output is correct |
50 |
Correct |
6 ms |
1664 KB |
Output is correct |
51 |
Correct |
9 ms |
1664 KB |
Output is correct |
52 |
Correct |
6 ms |
1664 KB |
Output is correct |
53 |
Correct |
9 ms |
1664 KB |
Output is correct |
54 |
Correct |
6 ms |
1792 KB |
Output is correct |
55 |
Correct |
6 ms |
1664 KB |
Output is correct |
56 |
Correct |
6 ms |
1608 KB |
Output is correct |
57 |
Correct |
6 ms |
1664 KB |
Output is correct |
58 |
Correct |
6 ms |
1688 KB |
Output is correct |
59 |
Correct |
8 ms |
1664 KB |
Output is correct |
60 |
Correct |
8 ms |
1664 KB |
Output is correct |
61 |
Correct |
8 ms |
1664 KB |
Output is correct |
62 |
Correct |
7 ms |
1764 KB |
Output is correct |
63 |
Correct |
7 ms |
1792 KB |
Output is correct |
64 |
Correct |
7 ms |
1656 KB |
Output is correct |
65 |
Correct |
7 ms |
1664 KB |
Output is correct |
66 |
Correct |
7 ms |
1664 KB |
Output is correct |
67 |
Correct |
7 ms |
1792 KB |
Output is correct |
68 |
Correct |
8 ms |
1792 KB |
Output is correct |
69 |
Correct |
8 ms |
1664 KB |
Output is correct |
70 |
Correct |
6 ms |
1664 KB |
Output is correct |
71 |
Correct |
5 ms |
1664 KB |
Output is correct |
72 |
Correct |
5 ms |
1792 KB |
Output is correct |
73 |
Correct |
30 ms |
1664 KB |
Output is correct |
74 |
Correct |
7 ms |
1792 KB |
Output is correct |
75 |
Correct |
1621 ms |
191484 KB |
Output is correct |
76 |
Correct |
1689 ms |
186060 KB |
Output is correct |
77 |
Correct |
1439 ms |
191864 KB |
Output is correct |
78 |
Correct |
1511 ms |
195084 KB |
Output is correct |
79 |
Correct |
769 ms |
195964 KB |
Output is correct |
80 |
Correct |
835 ms |
189788 KB |
Output is correct |
81 |
Correct |
1364 ms |
193092 KB |
Output is correct |
82 |
Correct |
1510 ms |
195804 KB |
Output is correct |
83 |
Correct |
1326 ms |
202616 KB |
Output is correct |
84 |
Correct |
1454 ms |
202104 KB |
Output is correct |
85 |
Correct |
1481 ms |
194700 KB |
Output is correct |
86 |
Correct |
1032 ms |
187768 KB |
Output is correct |
87 |
Correct |
1006 ms |
185284 KB |
Output is correct |
88 |
Correct |
1223 ms |
183840 KB |
Output is correct |
89 |
Correct |
1246 ms |
194832 KB |
Output is correct |
90 |
Correct |
941 ms |
204296 KB |
Output is correct |
91 |
Correct |
860 ms |
188152 KB |
Output is correct |
92 |
Correct |
857 ms |
186488 KB |
Output is correct |
93 |
Correct |
1038 ms |
194936 KB |
Output is correct |
94 |
Correct |
1025 ms |
204000 KB |
Output is correct |
95 |
Correct |
1077 ms |
204536 KB |
Output is correct |
96 |
Correct |
925 ms |
189176 KB |
Output is correct |
97 |
Correct |
899 ms |
205020 KB |
Output is correct |
98 |
Correct |
995 ms |
201976 KB |
Output is correct |
99 |
Correct |
864 ms |
202424 KB |
Output is correct |
100 |
Correct |
684 ms |
189944 KB |
Output is correct |
101 |
Correct |
744 ms |
189916 KB |
Output is correct |
102 |
Correct |
1327 ms |
190200 KB |
Output is correct |
103 |
Correct |
1312 ms |
187504 KB |
Output is correct |
104 |
Correct |
1500 ms |
198264 KB |
Output is correct |
105 |
Correct |
1370 ms |
197676 KB |
Output is correct |
106 |
Correct |
1269 ms |
202944 KB |
Output is correct |
107 |
Correct |
933 ms |
195428 KB |
Output is correct |
108 |
Correct |
1333 ms |
193916 KB |
Output is correct |
109 |
Correct |
1413 ms |
206156 KB |
Output is correct |
110 |
Correct |
746 ms |
190840 KB |
Output is correct |
111 |
Correct |
971 ms |
193092 KB |
Output is correct |
112 |
Correct |
1588 ms |
183880 KB |
Output is correct |
113 |
Correct |
829 ms |
206328 KB |
Output is correct |