QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#385698 | #5415. Ropeway | shepherd | WA | 3ms | 3868kb | C++20 | 7.3kb | 2024-04-10 23:32:30 | 2024-04-10 23:32:31 |
Judging History
answer
#include <bits/stdc++.h>
#include <climits>
#include <cstdint>
using namespace std;
#pragma GCC optimize("Ofast,unroll-loops")
using ui = unsigned int;
using ll = long long;
using ull = uint64_t;
using ld = long double;
template <typename K, typename V>
using umap = unordered_map<K, V>;
#define null NULL
#define len(a) static_cast<int>((a).size())
#define present(c, x) (c.find(x) != c.end())
#define inrange(val, start, end) (val >= start && val <= end)
const double PI = 2 * acos(0.0);
constexpr int iinf = 0x3f3f3f3f;
constexpr ll inf = 1'000'000'000'000'000;
constexpr ll mod = 1e9 + 7;
#define var(args...) \
{ \
string _s = #args; \
stringstream _ss; \
string ccurr = ""; \
for (int zz = 0; zz < len(_s); zz++) { \
if (_s[zz] == ' ') continue; \
if (_s[zz] == ',') { \
_ss << ' ' + ccurr; \
ccurr = ""; \
} else { \
ccurr += _s[zz]; \
} \
} \
_ss << ' ' + ccurr; \
istream_iterator<string> _it(_ss); \
vars(_it, args); \
}
#define debugDecimal(d) cerr << setprecision(d) << fixed
void vars(istream_iterator<string> it) { cerr << '\n'; }
template <typename T, typename... Args>
void vars(istream_iterator<string> it, T a, Args... args) {
cerr << " [" << *it << ": " << a << "] ";
vars(++it, args...);
}
#define printVerdict(verdict) cout << (verdict ? "YES" : "NO") << '\n'
#define printDecimal(d) cout << setprecision(d) << fixed
#define printCase(_) cout << "Case #" << (_) << ": "
template <int I, typename TupleT>
ostream& printTupleImpl(ostream& out, const TupleT& t) {
if constexpr (I < tuple_size_v<TupleT>) {
out << get<I>(t) << " ";
printTupleImpl<I + 1, TupleT>(out, t);
}
return out;
}
template <typename... Ts>
ostream& operator<<(ostream& out, const tuple<Ts...>& t) {
return printTupleImpl<0>(out, t);
}
template <int I, typename TupleT>
istream& readTupleImpl(istream& in, TupleT* t) {
if constexpr (I < tuple_size_v<TupleT>) {
in >> get<I>(*t);
readTupleImpl<I + 1, TupleT>(in, t);
}
return in;
}
template <typename... Ts>
istream& operator>>(istream& in, tuple<Ts...>& t) {
return readTupleImpl<0>(in, &t);
}
template <typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& p) {
return out << p.first << " " << p.second;
}
template <typename T>
ostream& operator<<(ostream& out, const vector<T>& arr) {
for (const T& a : arr) out << a << " ";
return out;
}
template <typename T>
ostream& operator<<(ostream& out, const vector<vector<T>>& grid) {
for (const vector<T>& row : grid) out << row << '\n';
return out;
}
template <typename T>
istream& operator>>(istream& in, vector<T>& arr) {
for (T& a : arr) in >> a;
return in;
}
template <typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& a) {
in >> a.first >> a.second;
return in;
}
template <typename Fun>
class y_combinator_result {
Fun fun_;
public:
template <typename T>
explicit y_combinator_result(T&& fun) : fun_{std::forward<T>(fun)} {}
template <typename... ArgTs>
decltype(auto) operator()(ArgTs&&... args) {
return fun_(std::ref(*this), std::forward<ArgTs>(args)...);
}
};
template <typename Fun>
decltype(auto) y_combinator(Fun&& fun) {
return y_combinator_result<decay_t<Fun>>(std::forward<Fun>(fun));
}
template <typename T>
struct Tree {
// static constexpr T unit = make_pair(1e16, -1);
T f(T a, T b) { return min(a, b); }
T unit;
vector<T> s;
int n;
explicit Tree(int n_ = 0, T def = T{}) : unit(def), s(2 * n_, def), n(n_) {}
void update(int pos, T val) {
for (s[pos += n] = val; pos /= 2;) {
s[pos] = f(s[pos * 2], s[pos * 2 + 1]);
}
}
T query(int b, int e) {
T ra = unit, rb = unit;
for (b += n, e += n; b < e; b /= 2, e /= 2) {
if (b % 2) ra = f(ra, s[b++]);
if (e % 2) rb = f(s[--e], rb);
}
return f(ra, rb);
}
};
inline void prayGod() {
int t;
cin >> t;
while (t--) {
int n, k;
cin >> n >> k;
vector<ll> a(n);
cin >> a;
a.insert(a.begin(), 0);
a.push_back(0);
string s;
cin >> s;
s = "1" + s + "1";
n = len(s);
vector<int> lb(n, 0), rb(n, n - 1);
vector<ll> left(n), right(n);
Tree<pair<ll, int>> rtree(n, make_pair(LLONG_MAX, -1)),
ltree(n, make_pair(LLONG_MAX, -1));
int boundary = 0;
ltree.update(0, make_pair(0, 0));
rtree.update(n - 1, make_pair(0, n - 1));
vector<int> parent(n, -1);
for (int i = 1; i < n; i++) {
lb[i] = max({0, i - k, boundary});
if (s[i] == '1') boundary = i;
int par;
tie(left[i], par) = ltree.query(lb[i], i);
left[i] += a[i];
parent[i] = par;
ltree.update(i, make_pair(left[i], i));
}
boundary = n - 1;
for (int i = n - 2; i >= 0; i--) {
rb[i] = min({n - 1, i + k, boundary});
if (s[i] == '1') boundary = i;
right[i] = rtree.query(i + 1, rb[i] + 1).first + a[i];
rtree.update(i, make_pair(right[i], i));
}
set<int> path;
ll best_path = 0;
{
int curr = n - 1;
while (curr != -1) {
path.insert(curr);
best_path += a[curr];
curr = parent[curr];
}
}
int q;
cin >> q;
Tree<ll> temp_tree(n, 1e16);
while (q--) {
int p, v;
cin >> p >> v;
if (present(path, p)) {
// p is on optimal path
ll ret = best_path - a[p] + v;
for (int i = p + 1; i <= rb[p]; i++) {
temp_tree.update(i, right[i]);
}
for (int i = p - 1; i >= lb[p]; i--) {
// do stuff
ll curr = temp_tree.query(i + 1, rb[i] + 1);
if (curr != 1e16) curr += left[i];
ret = min(ret, curr);
temp_tree.update(i, curr);
}
for (int i = p - 1; i >= lb[p]; i--) {
temp_tree.update(i, left[i]);
}
for (int i = p + 1; i <= rb[p]; i++) {
// do stuff
auto curr = temp_tree.query(lb[i], i);
if (curr != 1e16) curr += right[i];
ret = min(ret, curr);
temp_tree.update(i, curr);
}
for (int i = lb[p]; i <= rb[p]; i++) {
temp_tree.update(i, 1e16);
}
cout << ret << '\n';
} else {
ll ret = best_path;
ll left_side = ltree.query(lb[p], p).first;
ll right_side = rtree.query(p + 1, rb[p]).first;
for (int i = lb[p]; i < p; i++) {
ret = min(ret, left[i] + v + right_side);
}
for (int i = p + 1; i <= rb[p]; i++) {
ret = min(ret, right[i] + v + left_side);
}
cout << ret << '\n';
}
}
}
}
int main() {
#ifdef LLOCAL
clock_t start = clock();
#endif
std::ios_base::sync_with_stdio(false);
cin.tie(0);
prayGod();
#ifdef LLOCAL
clock_t end = clock();
double time_taken = double(end - start) / CLOCKS_PER_SEC;
debugDecimal(5) << time_taken << " s" << '\n';
#endif
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3868kb
input:
3 10 3 5 10 7 100 4 3 12 5 100 1 0001000010 2 2 3 6 15 5 6 1 1 1 1 1 00000 1 3 100 5 6 1 1 1 1 1 00100 1 3 100
output:
206 214 0 100
result:
ok 4 number(s): "206 214 0 100"
Test #2:
score: -100
Wrong Answer
time: 3ms
memory: 3856kb
input:
500 19 6 285203460 203149294 175739375 211384407 323087820 336418462 114884618 61054702 243946442 19599175 51974474 285317523 222489944 26675167 300331960 1412281 324105264 33722550 169011266 1111111110110100011 18 3 127056246 5 100630226 14 301161052 2 331781882 5 218792226 2 190274295 12 49227476 ...
output:
2472886431 2299111966 2796055445 2650202148 2417273966 2508694561 2285479513 -9223372034836775776 2521569560 2240907690 2577284958 -9223372034230974169 2766700195 2511807344 2521569560 2438434986 2669077215 2682112324 470735446 470735446 211705888 564509290 715543137 470735446 -9223372036540251038 1...
result:
wrong answer 8th numbers differ - expected: '2521569560', found: '-9223372034836775776'