Submission #2147307
Source Code Expand
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; (i) < int(n); ++ (i))
using ll = long long;
using namespace std;
template <class OperatorMonoid>
struct dual_segment_tree {
typedef typename OperatorMonoid::underlying_type operator_type;
typedef typename OperatorMonoid::target_type underlying_type;
int n;
vector<operator_type> f;
vector<underlying_type> a;
const OperatorMonoid op;
dual_segment_tree() = default;
dual_segment_tree(int a_n, underlying_type initial_value, OperatorMonoid const & a_op = OperatorMonoid()) : op(a_op) {
n = 1; while (n < a_n) n *= 2;
a.resize(n, initial_value);
f.resize(n-1, op.unit());
}
underlying_type point_get(int i) { // 0-based
underlying_type acc = a[i];
for (i = (i+n)/2; i > 0; i /= 2) { // 1-based
acc = op.apply(f[i-1], acc);
}
return acc;
}
void range_apply(int l, int r, operator_type z) { // 0-based, [l, r)
assert (0 <= l and l <= r and r <= n);
range_apply(0, 0, n, l, r, z);
}
void range_apply(int i, int il, int ir, int l, int r, operator_type z) {
if (l <= il and ir <= r) { // 0-based
if (i < f.size()) {
f[i] = op.append(z, f[i]);
} else {
a[i-n+1] = op.apply(z, a[i-n+1]);
}
} else if (ir <= l or r <= il) {
// nop
} else {
range_apply(2*i+1, il, (il+ir)/2, 0, n, f[i]);
range_apply(2*i+2, (il+ir)/2, ir, 0, n, f[i]);
f[i] = op.unit();
range_apply(2*i+1, il, (il+ir)/2, l, r, z);
range_apply(2*i+2, (il+ir)/2, ir, l, r, z);
}
}
};
struct grad_init_operator_monoid {
typedef tuple<ll, ll, bool, int> underlying_type; // (a, b, does_erase, set_index), add a * index + b
typedef pair<ll, int> target_type; // (value, index)
underlying_type unit() const {
return make_tuple(0ll, 0ll, false, -1);
}
underlying_type append(underlying_type f, underlying_type g) const {
if (get<2>(f)) return f;
ll a = get<0>(f) + get<0>(g);
ll b = get<1>(f) + get<1>(g);
bool does_erase = get<2>(g);
int set_index = max(get<3>(f), get<3>(g));
return make_tuple(a, b, does_erase, set_index);
}
target_type apply(underlying_type f, target_type x) const {
ll a, b; bool does_erase; int set_index; tie(a, b, does_erase, set_index) = f;
ll value; int index; tie(value, index) = x;
ll next_value = a * index + b + (does_erase ? 0 : value);
int next_index = set_index != -1 ? set_index : index;
return make_pair(next_value, next_index);
}
};
template <typename UnaryPredicate>
int64_t binsearch(int64_t l, int64_t r, UnaryPredicate p) {
assert (l <= r);
-- l;
while (r - l > 1) {
int64_t m = l + (r - l) / 2; // avoid overflow
(p(m) ? r : l) = m;
}
return r;
}
int main() {
// input
int n, l; scanf("%d%d", &n, &l);
vector<int> t(n), p(n);
REP (i, n) scanf("%d%d", &t[i], &p[i]);
// solve
// // reverse poss to ignore times
for (int l = 0; l < n; ) {
int r = l;
while (r < n and t[l] == t[r]) ++ r;
reverse(p.begin() + l, p.begin() + r);
l = r;
}
// // compute dp
dual_segment_tree<grad_init_operator_monoid> dp(l + 1, make_pair(0, -1));
REP (x, l + 1) {
dp.range_apply(x, x + 1, make_tuple(0ll, 0ll, false, x)); // init
}
for (int p_i : p) {
dp.range_apply(0, p_i, make_tuple(-1, p_i, false, -1));
dp.range_apply(p_i, l + 1, make_tuple(1, - p_i, false, -1));
int x = binsearch(0, l, [&](int x) {
return dp.point_get(x + 1).first - dp.point_get(x).first >= 0;
});
ll min_dp = dp.point_get(x).first;
dp.range_apply(x, l + 1, make_tuple(0ll, min_dp, true, -1));
}
// output
ll result = dp.point_get(l).first;
printf("%lld\n", result);
return 0;
}
Submission Info
Submission Time
2018-03-02 17:22:17+0900
Task
E - 花火
User
kimiyuki
Language
C++14 (GCC 5.4.1)
Score
160
Code Size
4040 Byte
Status
AC
Exec Time
441 ms
Memory
6144 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:85:36: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
int n, l; scanf("%d%d", &n, &l);
^
./Main.cpp:87:43: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
REP (i, n) scanf("%d%d", &t[i], &p[i]);
^
Judge Result
Set Name
Sample
Subtask1
Subtask2
Score / Max Score
0 / 0
30 / 30
130 / 130
Status
Set Name
Test Cases
Sample
sample_01.txt, sample_02.txt, sample_03.txt
Subtask1
sample_01.txt, sample_02.txt, sample_03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt, subtask1_23.txt, subtask1_24.txt, subtask1_25.txt, subtask1_26.txt, subtask1_27.txt, subtask1_28.txt, subtask1_29.txt, subtask1_30.txt, subtask1_31.txt, subtask1_32.txt, subtask1_33.txt, subtask1_34.txt, subtask1_35.txt, subtask1_36.txt, subtask1_37.txt, subtask1_38.txt, subtask1_39.txt, subtask1_40.txt, subtask1_41.txt, subtask1_42.txt
Subtask2
sample_01.txt, sample_02.txt, sample_03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt, subtask1_23.txt, subtask1_24.txt, subtask1_25.txt, subtask1_26.txt, subtask1_27.txt, subtask1_28.txt, subtask1_29.txt, subtask1_30.txt, subtask1_31.txt, subtask1_32.txt, subtask1_33.txt, subtask1_34.txt, subtask1_35.txt, subtask1_36.txt, subtask1_37.txt, subtask1_38.txt, subtask1_39.txt, subtask1_40.txt, subtask1_41.txt, subtask1_42.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt, subtask2_13.txt, subtask2_14.txt, subtask2_15.txt, subtask2_16.txt, subtask2_17.txt, subtask2_18.txt, subtask2_19.txt, subtask2_20.txt, subtask2_21.txt, subtask2_22.txt, subtask2_23.txt, subtask2_24.txt, subtask2_25.txt, subtask2_26.txt, subtask2_27.txt, subtask2_28.txt, subtask2_29.txt, subtask2_30.txt, subtask2_31.txt, subtask2_32.txt, subtask2_33.txt, subtask2_34.txt, subtask2_35.txt, subtask2_36.txt, subtask2_37.txt, subtask2_38.txt, subtask2_39.txt, subtask2_40.txt, subtask2_41.txt, subtask2_42.txt, subtask2_43.txt, subtask2_44.txt, subtask2_45.txt, subtask2_46.txt, subtask2_47.txt, subtask2_48.txt, subtask2_49.txt, subtask2_50.txt
Case Name
Status
Exec Time
Memory
sample_01.txt
AC
1 ms
256 KB
sample_02.txt
AC
1 ms
256 KB
sample_03.txt
AC
1 ms
256 KB
subtask1_01.txt
AC
6 ms
384 KB
subtask1_02.txt
AC
6 ms
384 KB
subtask1_03.txt
AC
6 ms
384 KB
subtask1_04.txt
AC
6 ms
384 KB
subtask1_05.txt
AC
2 ms
256 KB
subtask1_06.txt
AC
2 ms
256 KB
subtask1_07.txt
AC
3 ms
256 KB
subtask1_08.txt
AC
3 ms
256 KB
subtask1_09.txt
AC
6 ms
384 KB
subtask1_10.txt
AC
6 ms
384 KB
subtask1_11.txt
AC
6 ms
384 KB
subtask1_12.txt
AC
6 ms
384 KB
subtask1_13.txt
AC
1 ms
256 KB
subtask1_14.txt
AC
2 ms
256 KB
subtask1_15.txt
AC
3 ms
256 KB
subtask1_16.txt
AC
3 ms
256 KB
subtask1_17.txt
AC
6 ms
384 KB
subtask1_18.txt
AC
6 ms
384 KB
subtask1_19.txt
AC
6 ms
384 KB
subtask1_20.txt
AC
6 ms
384 KB
subtask1_21.txt
AC
6 ms
384 KB
subtask1_22.txt
AC
6 ms
384 KB
subtask1_23.txt
AC
6 ms
384 KB
subtask1_24.txt
AC
6 ms
384 KB
subtask1_25.txt
AC
2 ms
256 KB
subtask1_26.txt
AC
3 ms
256 KB
subtask1_27.txt
AC
6 ms
384 KB
subtask1_28.txt
AC
6 ms
384 KB
subtask1_29.txt
AC
1 ms
256 KB
subtask1_30.txt
AC
2 ms
256 KB
subtask1_31.txt
AC
6 ms
384 KB
subtask1_32.txt
AC
6 ms
384 KB
subtask1_33.txt
AC
6 ms
384 KB
subtask1_34.txt
AC
5 ms
384 KB
subtask1_35.txt
AC
5 ms
384 KB
subtask1_36.txt
AC
5 ms
384 KB
subtask1_37.txt
AC
1 ms
256 KB
subtask1_38.txt
AC
2 ms
384 KB
subtask1_39.txt
AC
1 ms
256 KB
subtask1_40.txt
AC
2 ms
384 KB
subtask1_41.txt
AC
1 ms
256 KB
subtask1_42.txt
AC
2 ms
384 KB
subtask2_01.txt
AC
424 ms
6144 KB
subtask2_02.txt
AC
441 ms
6144 KB
subtask2_03.txt
AC
428 ms
6144 KB
subtask2_04.txt
AC
424 ms
6144 KB
subtask2_05.txt
AC
408 ms
6144 KB
subtask2_06.txt
AC
324 ms
6016 KB
subtask2_07.txt
AC
212 ms
3200 KB
subtask2_08.txt
AC
129 ms
3072 KB
subtask2_09.txt
AC
22 ms
1024 KB
subtask2_10.txt
AC
43 ms
1024 KB
subtask2_11.txt
AC
79 ms
1024 KB
subtask2_12.txt
AC
118 ms
1024 KB
subtask2_13.txt
AC
270 ms
1664 KB
subtask2_14.txt
AC
400 ms
6144 KB
subtask2_15.txt
AC
407 ms
6144 KB
subtask2_16.txt
AC
409 ms
6144 KB
subtask2_17.txt
AC
412 ms
6144 KB
subtask2_18.txt
AC
406 ms
6144 KB
subtask2_19.txt
AC
18 ms
1024 KB
subtask2_20.txt
AC
39 ms
1024 KB
subtask2_21.txt
AC
74 ms
1024 KB
subtask2_22.txt
AC
112 ms
1024 KB
subtask2_23.txt
AC
252 ms
1664 KB
subtask2_24.txt
AC
409 ms
6144 KB
subtask2_25.txt
AC
407 ms
6144 KB
subtask2_26.txt
AC
407 ms
6144 KB
subtask2_27.txt
AC
413 ms
6144 KB
subtask2_28.txt
AC
418 ms
6144 KB
subtask2_29.txt
AC
391 ms
6144 KB
subtask2_30.txt
AC
402 ms
6144 KB
subtask2_31.txt
AC
408 ms
6144 KB
subtask2_32.txt
AC
387 ms
6144 KB
subtask2_33.txt
AC
414 ms
6144 KB
subtask2_34.txt
AC
407 ms
6144 KB
subtask2_35.txt
AC
63 ms
1024 KB
subtask2_36.txt
AC
97 ms
1024 KB
subtask2_37.txt
AC
278 ms
1664 KB
subtask2_38.txt
AC
409 ms
6144 KB
subtask2_39.txt
AC
404 ms
6144 KB
subtask2_40.txt
AC
16 ms
1024 KB
subtask2_41.txt
AC
20 ms
1024 KB
subtask2_42.txt
AC
403 ms
6144 KB
subtask2_43.txt
AC
404 ms
6144 KB
subtask2_44.txt
AC
407 ms
6144 KB
subtask2_45.txt
AC
305 ms
6144 KB
subtask2_46.txt
AC
301 ms
6144 KB
subtask2_47.txt
AC
311 ms
6144 KB
subtask2_48.txt
AC
45 ms
5376 KB
subtask2_49.txt
AC
1 ms
256 KB
subtask2_50.txt
AC
45 ms
5376 KB