# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
135679 |
2019-07-24T09:41:24 Z |
E869120 |
Cake 3 (JOI19_cake3) |
C++14 |
|
3480 ms |
35380 KB |
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#pragma warning (disable: 4996)
class SegmentTree {
public:
vector<long long> dat1, dat2; int size_ = 1;
void init(int sz) {
while (size_ <= sz) size_ *= 2;
dat1.resize(size_ * 2, 0);
dat2.resize(size_ * 2, 0);
}
void add(int pos,long long x) {
pos += size_;
while (pos >= 1) {
dat1[pos]++; dat2[pos] += x;
pos >>= 1;
}
}
void lose(int pos, long long x) {
pos += size_;
while (pos >= 1) {
dat1[pos]--; dat2[pos] -= x;
pos >>= 1;
}
}
long long getmax(long long M) {
int u = 1; long long cx = 0;
while (u < size_) {
if (dat1[u * 2 + 1] <= M) {
M -= dat1[u * 2 + 1];
cx += dat2[u * 2 + 1];
u = u * 2;
}
else {
u = u * 2 + 1;
}
}
if (M > 0) {
M -= dat1[u];
cx += dat2[u];
if (M > 0) return -(1LL << 60);
}
return cx;
}
};
long long N, M, C[1 << 18], V[1 << 18], ans[1 << 18], id[1 << 18], SIZE_ = 1;
vector<pair<long long, long long>>A, B;
int main() {
// --------------------------- 入力・ソート ----------------------
scanf("%lld%lld", &N, &M);
for (int i = 0; i < N; i++) {
scanf("%lld%lld", &V[i], &C[i]);
A.push_back(make_pair(C[i], V[i]));
}
sort(A.begin(), A.end());
for (int i = 1; i <= N; i++) {
C[i] = A[i - 1].first; V[i] = A[i - 1].second;
B.push_back(make_pair(V[i], i));
}
sort(B.begin(), B.end());
// ---------------------------- ただの分割 -----------------------
while (SIZE_ <= N) SIZE_ *= 2;
ans[SIZE_] = -(1LL << 60); id[SIZE_] = N;
ans[0] = -(1LL << 60); id[0] = 1;
for (int i = (SIZE_ >> 1); i >= 1; i >>= 1) {
vector<int> vec;
for (int j = i; j < SIZE_; j += i * 2) vec.push_back(j);
SegmentTree Z; Z.init(SIZE_ + 1);
int cx = N + 1;
for (int j = vec.size() - 1; j >= 0; j--) {
// 新たに追加する
for (int k = vec[j]; k < min((int)id[vec[j] + i] + 1, cx); k++) {
if (k <= N) {
int pos1 = lower_bound(B.begin(), B.end(), make_pair(V[k], 1LL * k)) - B.begin();
Z.add(pos1, V[k]);
}
}
// 答えを求める
pair<long long, int> maxid = make_pair(-(1LL << 59), N);
for (int k = id[vec[j] + i]; k >= id[vec[j] - i]; k--) {
long long v = Z.getmax(M) - 2LL * (C[k] - C[vec[j]]);
maxid = max(maxid, make_pair(v, k));
if (k >= vec[j] && k != id[vec[j] - i]) {
int pos1 = lower_bound(B.begin(), B.end(), make_pair(V[k], 1LL * k)) - B.begin();
Z.lose(pos1, V[k]);
}
}
ans[vec[j]] = maxid.first;
id[vec[j]] = maxid.second;
cx = vec[j];
}
}
// --------------------------- 答えを求める ----------------------
long long FinalAns = -(1LL << 60);
for (int i = 1; i <= N; i++) FinalAns = max(FinalAns, ans[i]);
cout << FinalAns << endl;
return 0;
}
Compilation message
cake3.cpp:5:0: warning: ignoring #pragma warning [-Wunknown-pragmas]
#pragma warning (disable: 4996)
cake3.cpp: In function 'int main()':
cake3.cpp:56:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld", &N, &M);
~~~~~^~~~~~~~~~~~~~~~~~~~
cake3.cpp:58:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld", &V[i], &C[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Correct |
2 ms |
376 KB |
Output is correct |
9 |
Correct |
2 ms |
376 KB |
Output is correct |
10 |
Correct |
2 ms |
380 KB |
Output is correct |
11 |
Correct |
2 ms |
376 KB |
Output is correct |
12 |
Correct |
2 ms |
376 KB |
Output is correct |
13 |
Correct |
3 ms |
376 KB |
Output is correct |
14 |
Correct |
2 ms |
376 KB |
Output is correct |
15 |
Correct |
2 ms |
376 KB |
Output is correct |
16 |
Correct |
2 ms |
376 KB |
Output is correct |
17 |
Correct |
2 ms |
376 KB |
Output is correct |
18 |
Correct |
2 ms |
376 KB |
Output is correct |
19 |
Correct |
2 ms |
376 KB |
Output is correct |
20 |
Correct |
2 ms |
376 KB |
Output is correct |
21 |
Correct |
2 ms |
504 KB |
Output is correct |
22 |
Correct |
2 ms |
376 KB |
Output is correct |
23 |
Correct |
2 ms |
376 KB |
Output is correct |
24 |
Correct |
2 ms |
376 KB |
Output is correct |
25 |
Correct |
2 ms |
376 KB |
Output is correct |
26 |
Correct |
2 ms |
376 KB |
Output is correct |
27 |
Correct |
2 ms |
380 KB |
Output is correct |
28 |
Correct |
2 ms |
376 KB |
Output is correct |
29 |
Correct |
2 ms |
376 KB |
Output is correct |
30 |
Correct |
2 ms |
376 KB |
Output is correct |
31 |
Correct |
2 ms |
376 KB |
Output is correct |
32 |
Correct |
2 ms |
376 KB |
Output is correct |
33 |
Correct |
2 ms |
376 KB |
Output is correct |
34 |
Correct |
2 ms |
376 KB |
Output is correct |
35 |
Correct |
2 ms |
376 KB |
Output is correct |
36 |
Correct |
2 ms |
376 KB |
Output is correct |
37 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Correct |
2 ms |
376 KB |
Output is correct |
9 |
Correct |
2 ms |
376 KB |
Output is correct |
10 |
Correct |
2 ms |
380 KB |
Output is correct |
11 |
Correct |
2 ms |
376 KB |
Output is correct |
12 |
Correct |
2 ms |
376 KB |
Output is correct |
13 |
Correct |
3 ms |
376 KB |
Output is correct |
14 |
Correct |
2 ms |
376 KB |
Output is correct |
15 |
Correct |
2 ms |
376 KB |
Output is correct |
16 |
Correct |
2 ms |
376 KB |
Output is correct |
17 |
Correct |
2 ms |
376 KB |
Output is correct |
18 |
Correct |
2 ms |
376 KB |
Output is correct |
19 |
Correct |
2 ms |
376 KB |
Output is correct |
20 |
Correct |
2 ms |
376 KB |
Output is correct |
21 |
Correct |
2 ms |
504 KB |
Output is correct |
22 |
Correct |
2 ms |
376 KB |
Output is correct |
23 |
Correct |
2 ms |
376 KB |
Output is correct |
24 |
Correct |
2 ms |
376 KB |
Output is correct |
25 |
Correct |
2 ms |
376 KB |
Output is correct |
26 |
Correct |
2 ms |
376 KB |
Output is correct |
27 |
Correct |
2 ms |
380 KB |
Output is correct |
28 |
Correct |
2 ms |
376 KB |
Output is correct |
29 |
Correct |
2 ms |
376 KB |
Output is correct |
30 |
Correct |
2 ms |
376 KB |
Output is correct |
31 |
Correct |
2 ms |
376 KB |
Output is correct |
32 |
Correct |
2 ms |
376 KB |
Output is correct |
33 |
Correct |
2 ms |
376 KB |
Output is correct |
34 |
Correct |
2 ms |
376 KB |
Output is correct |
35 |
Correct |
2 ms |
376 KB |
Output is correct |
36 |
Correct |
2 ms |
376 KB |
Output is correct |
37 |
Correct |
2 ms |
376 KB |
Output is correct |
38 |
Correct |
9 ms |
632 KB |
Output is correct |
39 |
Correct |
9 ms |
632 KB |
Output is correct |
40 |
Correct |
9 ms |
632 KB |
Output is correct |
41 |
Correct |
9 ms |
632 KB |
Output is correct |
42 |
Correct |
10 ms |
604 KB |
Output is correct |
43 |
Correct |
9 ms |
632 KB |
Output is correct |
44 |
Correct |
9 ms |
632 KB |
Output is correct |
45 |
Correct |
10 ms |
632 KB |
Output is correct |
46 |
Correct |
10 ms |
632 KB |
Output is correct |
47 |
Correct |
10 ms |
636 KB |
Output is correct |
48 |
Correct |
9 ms |
632 KB |
Output is correct |
49 |
Correct |
10 ms |
632 KB |
Output is correct |
50 |
Correct |
10 ms |
632 KB |
Output is correct |
51 |
Correct |
10 ms |
632 KB |
Output is correct |
52 |
Correct |
10 ms |
632 KB |
Output is correct |
53 |
Correct |
9 ms |
632 KB |
Output is correct |
54 |
Correct |
9 ms |
668 KB |
Output is correct |
55 |
Correct |
9 ms |
632 KB |
Output is correct |
56 |
Correct |
9 ms |
636 KB |
Output is correct |
57 |
Correct |
9 ms |
632 KB |
Output is correct |
58 |
Correct |
9 ms |
676 KB |
Output is correct |
59 |
Correct |
7 ms |
632 KB |
Output is correct |
60 |
Correct |
7 ms |
632 KB |
Output is correct |
61 |
Correct |
8 ms |
632 KB |
Output is correct |
62 |
Correct |
7 ms |
632 KB |
Output is correct |
63 |
Correct |
7 ms |
632 KB |
Output is correct |
64 |
Correct |
7 ms |
632 KB |
Output is correct |
65 |
Correct |
8 ms |
632 KB |
Output is correct |
66 |
Correct |
8 ms |
632 KB |
Output is correct |
67 |
Correct |
8 ms |
632 KB |
Output is correct |
68 |
Correct |
8 ms |
632 KB |
Output is correct |
69 |
Correct |
8 ms |
632 KB |
Output is correct |
70 |
Correct |
8 ms |
636 KB |
Output is correct |
71 |
Correct |
8 ms |
632 KB |
Output is correct |
72 |
Correct |
8 ms |
672 KB |
Output is correct |
73 |
Correct |
7 ms |
636 KB |
Output is correct |
74 |
Correct |
9 ms |
632 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Correct |
2 ms |
376 KB |
Output is correct |
9 |
Correct |
2 ms |
376 KB |
Output is correct |
10 |
Correct |
2 ms |
380 KB |
Output is correct |
11 |
Correct |
2 ms |
376 KB |
Output is correct |
12 |
Correct |
2 ms |
376 KB |
Output is correct |
13 |
Correct |
3 ms |
376 KB |
Output is correct |
14 |
Correct |
2 ms |
376 KB |
Output is correct |
15 |
Correct |
2 ms |
376 KB |
Output is correct |
16 |
Correct |
2 ms |
376 KB |
Output is correct |
17 |
Correct |
2 ms |
376 KB |
Output is correct |
18 |
Correct |
2 ms |
376 KB |
Output is correct |
19 |
Correct |
2 ms |
376 KB |
Output is correct |
20 |
Correct |
2 ms |
376 KB |
Output is correct |
21 |
Correct |
2 ms |
504 KB |
Output is correct |
22 |
Correct |
2 ms |
376 KB |
Output is correct |
23 |
Correct |
2 ms |
376 KB |
Output is correct |
24 |
Correct |
2 ms |
376 KB |
Output is correct |
25 |
Correct |
2 ms |
376 KB |
Output is correct |
26 |
Correct |
2 ms |
376 KB |
Output is correct |
27 |
Correct |
2 ms |
380 KB |
Output is correct |
28 |
Correct |
2 ms |
376 KB |
Output is correct |
29 |
Correct |
2 ms |
376 KB |
Output is correct |
30 |
Correct |
2 ms |
376 KB |
Output is correct |
31 |
Correct |
2 ms |
376 KB |
Output is correct |
32 |
Correct |
2 ms |
376 KB |
Output is correct |
33 |
Correct |
2 ms |
376 KB |
Output is correct |
34 |
Correct |
2 ms |
376 KB |
Output is correct |
35 |
Correct |
2 ms |
376 KB |
Output is correct |
36 |
Correct |
2 ms |
376 KB |
Output is correct |
37 |
Correct |
2 ms |
376 KB |
Output is correct |
38 |
Correct |
9 ms |
632 KB |
Output is correct |
39 |
Correct |
9 ms |
632 KB |
Output is correct |
40 |
Correct |
9 ms |
632 KB |
Output is correct |
41 |
Correct |
9 ms |
632 KB |
Output is correct |
42 |
Correct |
10 ms |
604 KB |
Output is correct |
43 |
Correct |
9 ms |
632 KB |
Output is correct |
44 |
Correct |
9 ms |
632 KB |
Output is correct |
45 |
Correct |
10 ms |
632 KB |
Output is correct |
46 |
Correct |
10 ms |
632 KB |
Output is correct |
47 |
Correct |
10 ms |
636 KB |
Output is correct |
48 |
Correct |
9 ms |
632 KB |
Output is correct |
49 |
Correct |
10 ms |
632 KB |
Output is correct |
50 |
Correct |
10 ms |
632 KB |
Output is correct |
51 |
Correct |
10 ms |
632 KB |
Output is correct |
52 |
Correct |
10 ms |
632 KB |
Output is correct |
53 |
Correct |
9 ms |
632 KB |
Output is correct |
54 |
Correct |
9 ms |
668 KB |
Output is correct |
55 |
Correct |
9 ms |
632 KB |
Output is correct |
56 |
Correct |
9 ms |
636 KB |
Output is correct |
57 |
Correct |
9 ms |
632 KB |
Output is correct |
58 |
Correct |
9 ms |
676 KB |
Output is correct |
59 |
Correct |
7 ms |
632 KB |
Output is correct |
60 |
Correct |
7 ms |
632 KB |
Output is correct |
61 |
Correct |
8 ms |
632 KB |
Output is correct |
62 |
Correct |
7 ms |
632 KB |
Output is correct |
63 |
Correct |
7 ms |
632 KB |
Output is correct |
64 |
Correct |
7 ms |
632 KB |
Output is correct |
65 |
Correct |
8 ms |
632 KB |
Output is correct |
66 |
Correct |
8 ms |
632 KB |
Output is correct |
67 |
Correct |
8 ms |
632 KB |
Output is correct |
68 |
Correct |
8 ms |
632 KB |
Output is correct |
69 |
Correct |
8 ms |
632 KB |
Output is correct |
70 |
Correct |
8 ms |
636 KB |
Output is correct |
71 |
Correct |
8 ms |
632 KB |
Output is correct |
72 |
Correct |
8 ms |
672 KB |
Output is correct |
73 |
Correct |
7 ms |
636 KB |
Output is correct |
74 |
Correct |
9 ms |
632 KB |
Output is correct |
75 |
Correct |
3077 ms |
30612 KB |
Output is correct |
76 |
Correct |
2839 ms |
33944 KB |
Output is correct |
77 |
Correct |
3100 ms |
34300 KB |
Output is correct |
78 |
Correct |
2980 ms |
34532 KB |
Output is correct |
79 |
Correct |
3083 ms |
34536 KB |
Output is correct |
80 |
Correct |
2933 ms |
34136 KB |
Output is correct |
81 |
Correct |
3172 ms |
33648 KB |
Output is correct |
82 |
Correct |
3099 ms |
33932 KB |
Output is correct |
83 |
Correct |
3250 ms |
34288 KB |
Output is correct |
84 |
Correct |
3480 ms |
34272 KB |
Output is correct |
85 |
Correct |
3289 ms |
33952 KB |
Output is correct |
86 |
Correct |
3078 ms |
33448 KB |
Output is correct |
87 |
Correct |
2895 ms |
33264 KB |
Output is correct |
88 |
Correct |
2975 ms |
33096 KB |
Output is correct |
89 |
Correct |
3033 ms |
33852 KB |
Output is correct |
90 |
Correct |
3236 ms |
34348 KB |
Output is correct |
91 |
Correct |
2972 ms |
33332 KB |
Output is correct |
92 |
Correct |
2935 ms |
33364 KB |
Output is correct |
93 |
Correct |
3078 ms |
33864 KB |
Output is correct |
94 |
Correct |
3161 ms |
34160 KB |
Output is correct |
95 |
Correct |
3418 ms |
34384 KB |
Output is correct |
96 |
Correct |
1197 ms |
33428 KB |
Output is correct |
97 |
Correct |
1253 ms |
34308 KB |
Output is correct |
98 |
Correct |
1226 ms |
34160 KB |
Output is correct |
99 |
Correct |
1257 ms |
34064 KB |
Output is correct |
100 |
Correct |
1162 ms |
33396 KB |
Output is correct |
101 |
Correct |
1162 ms |
33484 KB |
Output is correct |
102 |
Correct |
1691 ms |
33592 KB |
Output is correct |
103 |
Correct |
1655 ms |
33524 KB |
Output is correct |
104 |
Correct |
1702 ms |
34000 KB |
Output is correct |
105 |
Correct |
1818 ms |
33956 KB |
Output is correct |
106 |
Correct |
1823 ms |
34272 KB |
Output is correct |
107 |
Correct |
1815 ms |
33708 KB |
Output is correct |
108 |
Correct |
3226 ms |
34348 KB |
Output is correct |
109 |
Correct |
3263 ms |
34972 KB |
Output is correct |
110 |
Correct |
1487 ms |
32920 KB |
Output is correct |
111 |
Correct |
1505 ms |
33072 KB |
Output is correct |
112 |
Correct |
1180 ms |
32512 KB |
Output is correct |
113 |
Correct |
3210 ms |
35380 KB |
Output is correct |