QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#798210#5415. RopewayvwxyzAC ✓582ms177476kbC++2313.6kb2024-12-04 09:46:282024-12-04 09:46:29

Judging History

你现在查看的是最新测评结果

  • [2024-12-04 09:46:29]
  • 评测
  • 测评结果:AC
  • 用时:582ms
  • 内存:177476kb
  • [2024-12-04 09:46:28]
  • 提交

answer

// competitive-verifier: PROBLEM
#include <cassert>
#include <vector>
namespace internal {
// @return same with std::bit::bit_ceil
unsigned int bit_ceil(unsigned int n) {
    unsigned int x = 1;
    while (x < (unsigned int)(n)) x *= 2;
    return x;
}
// @param n `1 <= n`
// @return same with std::bit::countl_zero
int countl_zero(unsigned int n) { return __builtin_clz(n); }
// @param n `1 <= n`
// @return same with std::bit::countr_zero
int countr_zero(unsigned int n) { return __builtin_ctz(n); }
// @param n `1 <= n`
// @return same with std::bit::countr_zero
constexpr int countr_zero_constexpr(unsigned int n) {
    int x = 0;
    while (!(n & (1 << x))) x++;
    return x;
}
}  // namespace internal
/**
 * @brief スパーステーブル
 *
 * @tparam M モノイド
 */
template <class M>
struct sparse_table {
  private:
    using T = typename M::value_type;
  public:
    sparse_table() = default;
    sparse_table(const std::vector<T> &v) : _size(v.size()), data() {
        int b = std::max(1, internal::countr_zero(internal::bit_ceil(_size)));
        data.emplace_back(v);
        for (int i = 1; i < b; ++i) data.emplace_back(_size + 1 - (1 << i));
        for (int i = 1; i < b; ++i) {
            for (int j = 0; j + (1 << i) <= _size; ++j) {
                data[i][j] = M::op(data[i - 1][j], data[i - 1][j + (1 << (i - 1))]);
            }
        }
    }
    T prod(int l, int r) const {
        assert(0 <= l && l < r && r <= _size);
        if (l + 1 == r) return data[0][l];
        int b = 31 - internal::countl_zero(r - l - 1);
        return M::op(data[b][l], data[b][r - (1 << b)]);
    }
  private:
    int _size;
    std::vector<std::vector<T>> data;
};
#include <algorithm>
#include <limits>
#include <numeric>
#include <utility>
template <class T>
struct Add {
    using value_type = T;
    static constexpr T id() { return T(); }
    static constexpr T op(const T &lhs, const T &rhs) { return lhs + rhs; }
    template <class U>
    static constexpr U f(T lhs, U rhs) {
        return lhs + rhs;
    }
};
template <class T>
struct Mul {
    using value_type = T;
    static constexpr T id() { return T(1); }
    static constexpr T op(const T &lhs, const T &rhs) { return lhs * rhs; }
    template <class U>
    static constexpr U f(T lhs, U rhs) {
        return lhs * rhs;
    }
};
template <class T>
struct And {
    using value_type = T;
    static constexpr T id() { return std::numeric_limits<T>::max(); }
    static constexpr T op(const T &lhs, const T &rhs) { return lhs & rhs; }
    template <class U>
    static constexpr U f(T lhs, U rhs) {
        return lhs & rhs;
    }
};
template <class T>
struct Or {
    using value_type = T;
    static constexpr T id() { return T(); }
    static constexpr T op(const T &lhs, const T &rhs) { return lhs | rhs; }
    template <class U>
    static constexpr U f(T lhs, U rhs) {
        return lhs | rhs;
    }
};
template <class T>
struct Xor {
    using value_type = T;
    static constexpr T id() { return T(); }
    static constexpr T op(const T &lhs, const T &rhs) { return lhs ^ rhs; }
    template <class U>
    static constexpr U f(T lhs, U rhs) {
        return lhs ^ rhs;
    }
};
template <class T>
struct Min {
    using value_type = T;
    static constexpr T id() { return std::numeric_limits<T>::max(); }
    static constexpr T op(const T &lhs, const T &rhs) { return std::min(lhs, rhs); }
    template <class U>
    static constexpr U f(T lhs, U rhs) {
        return std::min((U)lhs, rhs);
    }
};
template <class T>
struct Max {
    using value_type = T;
    static constexpr T id() { return std::numeric_limits<T>::lowest(); }
    static constexpr T op(const T &lhs, const T &rhs) { return std::max(lhs, rhs); }
    template <class U>
    static constexpr U f(T lhs, U rhs) {
        return std::max((U)lhs, rhs);
    }
};
template <class T>
struct Gcd {
    using value_type = T;
    static constexpr T id() { return std::numeric_limits<T>::max(); }
    static constexpr T op(const T &lhs, const T &rhs) {
        return lhs == Gcd::id() ? rhs : (rhs == Gcd::id() ? lhs : std::gcd(lhs, rhs));
    }
};
template <class T>
struct Lcm {
    using value_type = T;
    static constexpr T id() { return std::numeric_limits<T>::max(); }
    static constexpr T op(const T &lhs, const T &rhs) {
        return lhs == Lcm::id() ? rhs : (rhs == Lcm::id() ? lhs : std::lcm(lhs, rhs));
    }
};
template <class T>
struct Update {
    using value_type = T;
    static constexpr T id() { return std::numeric_limits<T>::max(); }
    static constexpr T op(const T &lhs, const T &rhs) { return lhs == Update::id() ? rhs : lhs; }
    template <class U>
    static constexpr U f(T lhs, U rhs) {
        return lhs == Update::id() ? rhs : lhs;
    }
};
template <class T>
struct Affine {
    using P = std::pair<T, T>;
    using value_type = P;
    static constexpr P id() { return P(1, 0); }
    static constexpr P op(P lhs, P rhs) {
        return {lhs.first * rhs.first, lhs.first * rhs.second + lhs.second};
    }
};
template <class M>
struct Rev {
    using T = typename M::value_type;
    using value_type = T;
    static constexpr T id() { return M::id(); }
    static constexpr T op(T lhs, T rhs) { return M::op(rhs, lhs); }
};
/**
 * @brief セグメント木
 * @see https://noshi91.hatenablog.com/entry/2020/04/22/212649
 *
 * @tparam M モノイド
 */
template <class M>
struct segment_tree {
  private:
    using T = typename M::value_type;
    struct _segment_tree_reference {
      private:
        segment_tree<M> &self;
        int k;
      public:
        _segment_tree_reference(segment_tree<M> &self, int k) : self(self), k(k) {}
        _segment_tree_reference &operator=(const T &x) {
            self.set(k, x);
            return *this;
        }
        _segment_tree_reference &operator=(T &&x) {
            self.set(k, std::move(x));
            return *this;
        }
        operator T() const { return self.get(k); }
    };
  public:
    segment_tree() : segment_tree(0) {}
    explicit segment_tree(int n, T e = M::id()) : segment_tree(std::vector<T>(n, e)) {}
    template <class U>
    explicit segment_tree(const std::vector<U> &v) : _n(v.size()) {
        _size = internal::bit_ceil(_n);
        _log = internal::countr_zero(_size);
        data = std::vector<T>(_size << 1, M::id());
        for (int i = 0; i < _n; ++i) data[_size + i] = T(v[i]);
        for (int i = _size - 1; i >= 1; --i) update(i);
    }
    const T &operator[](int k) const { return data[k + _size]; }
    _segment_tree_reference operator[](int k) { return _segment_tree_reference(*this, k); }
    T at(int k) const { return data[k + _size]; }
    T get(int k) const { return data[k + _size]; }
    void set(int k, T val) {
        assert(0 <= k && k < _n);
        k += _size;
        data[k] = val;
        for (int i = 1; i <= _log; ++i) update(k >> i);
    }
    void reset(int k) { set(k, M::id()); }
    T all_prod() const { return data[1]; }
    T prod(int a, int b) const {
        assert(0 <= a && b <= _n);
        T l = M::id(), r = M::id();
        for (a += _size, b += _size; a < b; a >>= 1, b >>= 1) {
            if (a & 1) l = M::op(l, data[a++]);
            if (b & 1) r = M::op(data[--b], r);
        }
        return M::op(l, r);
    }
    template <class F>
    int max_right(F f) const {
        return max_right(0, f);
    }
    template <class F>
    int max_right(int l, F f) const {
        assert(0 <= l && l <= _n);
        assert(f(M::id()));
        if (l == _n) return _n;
        l += _size;
        T sm = M::id();
        do {
            while (l % 2 == 0) l >>= 1;
            if (!f(M::op(sm, data[l]))) {
                while (l < _size) {
                    l = (2 * l);
                    if (f(M::op(sm, data[l]))) {
                        sm = M::op(sm, data[l]);
                        l++;
                    }
                }
                return l - _size;
            }
            sm = M::op(sm, data[l]);
            l++;
        } while ((l & -l) != l);
        return _n;
    }
    template <class F>
    int min_left(F f) const {
        return min_left(_n, f);
    }
    template <class F>
    int min_left(int r, F f) const {
        assert(0 <= r && r <= _n);
        assert(f(M::id()));
        if (r == 0) return 0;
        r += _size;
        T sm = M::id();
        do {
            r--;
            while (r > 1 && (r % 2)) r >>= 1;
            if (!f(M::op(data[r], sm))) {
                while (r < _size) {
                    r = (2 * r + 1);
                    if (f(M::op(data[r], sm))) {
                        sm = M::op(data[r], sm);
                        r--;
                    }
                }
                return r + 1 - _size;
            }
            sm = M::op(data[r], sm);
        } while ((r & -r) != r);
        return 0;
    }
  private:
    int _n, _size, _log;
    std::vector<T> data;
    void update(int k) { data[k] = M::op(data[2 * k], data[2 * k + 1]); }
};
#ifdef ATCODER
#pragma GCC target("sse4.2,avx512f,avx512dq,avx512ifma,avx512cd,avx512bw,avx512vl,bmi2")
#endif
#pragma GCC optimize("Ofast,fast-math,unroll-all-loops")
#include <bits/stdc++.h>
#ifndef ATCODER
#pragma GCC target("sse4.2,avx2,bmi2")
#endif
template <class T, class U>
constexpr bool chmax(T &a, const U &b) {
    return a < (T)b ? a = (T)b, true : false;
}
template <class T, class U>
constexpr bool chmin(T &a, const U &b) {
    return (T)b < a ? a = (T)b, true : false;
}
constexpr std::int64_t INF = 1000000000000000003;
constexpr int Inf = 1000000003;
constexpr double EPS = 1e-7;
constexpr double PI = 3.14159265358979323846;
#define FOR(i, m, n) for (int i = (m); i < int(n); ++i)
#define FORR(i, m, n) for (int i = (m)-1; i >= int(n); --i)
#define FORL(i, m, n) for (int64_t i = (m); i < int64_t(n); ++i)
#define rep(i, n) FOR (i, 0, n)
#define repn(i, n) FOR (i, 1, n + 1)
#define repr(i, n) FORR (i, n, 0)
#define repnr(i, n) FORR (i, n + 1, 1)
#define all(s) (s).begin(), (s).end()
struct Sonic {
    Sonic() {
        std::ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
        std::cout << std::fixed << std::setprecision(20);
    }
    constexpr void operator()() const {}
} sonic;
using namespace std;
using ll = std::int64_t;
using ld = long double;
template <class T, class U>
std::istream &operator>>(std::istream &is, std::pair<T, U> &p) {
    return is >> p.first >> p.second;
}
template <class T>
std::istream &operator>>(std::istream &is, std::vector<T> &v) {
    for (T &i : v) is >> i;
    return is;
}
template <class T, class U>
std::ostream &operator<<(std::ostream &os, const std::pair<T, U> &p) {
    return os << '(' << p.first << ',' << p.second << ')';
}
template <class T>
std::ostream &operator<<(std::ostream &os, const std::vector<T> &v) {
    for (auto it = v.begin(); it != v.end(); ++it) os << (it == v.begin() ? "" : " ") << *it;
    return os;
}
template <class Head, class... Tail>
void co(Head &&head, Tail &&...tail) {
    if constexpr (sizeof...(tail) == 0) std::cout << head << '\n';
    else std::cout << head << ' ', co(std::forward<Tail>(tail)...);
}
template <class Head, class... Tail>
void ce(Head &&head, Tail &&...tail) {
    if constexpr (sizeof...(tail) == 0) std::cerr << head << '\n';
    else std::cerr << head << ' ', ce(std::forward<Tail>(tail)...);
}
void Yes(bool is_correct = true) { std::cout << (is_correct ? "Yes\n" : "No\n"); }
void No(bool is_not_correct = true) { Yes(!is_not_correct); }
void YES(bool is_correct = true) { std::cout << (is_correct ? "YES\n" : "NO\n"); }
void NO(bool is_not_correct = true) { YES(!is_not_correct); }
void Takahashi(bool is_correct = true) { std::cout << (is_correct ? "Takahashi" : "Aoki") << '\n'; }
void Aoki(bool is_not_correct = true) { Takahashi(!is_not_correct); }
void solve() {
    int n, k;
    cin >> n >> k;
    vector<ll> a(n);
    cin >> a;
    a.emplace(a.begin(), 0);
    a.emplace_back(0);
    string s;
    cin >> s;
    set<ll> st;
    rep (i, n) {
        if (s[i] == '1')
            st.emplace(i + 1);
    }
    segment_tree<Min<ll>> stl(n + 2), str(n + 2);
    stl.set(0, 0);
    repn (i, n + 1) {
        int l = 0;
        auto it = st.lower_bound(i);
        if (it != st.begin()) {
            chmax(l, *prev(it));
        }
        stl.set(i, stl.prod(max(l, i - k), i) + a[i]);
    }
    str.set(n + 1, 0);
    repr (i, n + 1) {
        int r = n + 2;
        auto it = st.upper_bound(i);
        if (it != st.end()) {
            chmin(r, *it + 1);
        }
        str.set(i, str.prod(i + 1, min(r, i + k + 1)) + a[i]);
    }
    vector<ll> vl(n + 2), vr(n + 2);
    rep (i, n + 2) {
        vl[i] = stl.get(i);
        vr[i] = str.get(i);
    }
    sparse_table<Min<ll>> spl(vl), spr(vr);
    int q;
    cin >> q;
    while (q--) {
        int p;
        ll v;
        cin >> p >> v;
        ll ans = INF;
        if (s[p - 1] == '1') {
            co(stl.get(n + 1) - a[p] + v);
        } else {
            chmin(ans, vl[p] + vr[p] - a[p] * 2 + v);
            auto it = st.lower_bound(p);
            int l = max(0, p - k);
            if (it != st.begin())
                chmax(l, *prev(it));
            FOR (i, l, p) {
                int r = min(n + 2, i + k + 1);
                if (it != st.end())
                    chmin(r, *it + 1);
                if (p + 1 < r)
                    chmin(ans, vl[i] + spr.prod(p + 1, r));
            }
            co(ans);
        }
    }
}
int main(void) {
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3592kb

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: 0
Accepted
time: 2ms
memory: 3616kb

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
2521569560
2521569560
2240907690
2577284958
2521569560
2766700195
2511807344
2521569560
2438434986
2669077215
2682112324
470735446
470735446
211705888
564509290
715543137
470735446
470735446
18
19
19
19
20
19
54
849950346
8...

result:

ok 5277 numbers

Test #3:

score: 0
Accepted
time: 4ms
memory: 3964kb

input:

50
183 160
22617237 21369258 39718669 4582413 28629717 25947766 1690897 19844235 35568283 42909820 21829213 70588436 8472484 53107624 21547259 11440081 6630789 5896457 19770793 30204510 29796593 27689811 39350369 21646987 36362667 38164292 13428410 54681069 24526477 58941286 70890011 43730474 388615...

output:

5303746210
5262479222
5346682277
5299354906
5290045662
5350552810
5343191051
5268759163
5299354906
5340227887
5299354906
5253956732
5289945955
5230918240
5287812187
5299354906
5299354906
5273800386
5299354906
5299354906
5353471727
5283662384
5230330060
5319166005
5338060400
5304825609
5268929476
526...

result:

ok 9541 numbers

Test #4:

score: 0
Accepted
time: 425ms
memory: 174696kb

input:

3
500000 891
806445768 895003544 461699845 184479965 853541910 593542573 667984604 465354540 303586741 243665567 285056069 294245042 675066412 456713460 215929340 756894934 773828574 317143965 451366539 891390118 436168373 633752416 78781758 298770626 35280548 226923750 96421159 523108871 265102517 ...

output:

5202946193
5202946193
5202946193
5202946193
5202946193
5202946193
5202946193
5202946193
5202946193
5202946193
5202946193
5202946193
5202946193
5202946193
5202946193
5202946193
5202946193
5202946193
5202946193
5202946193
5202946193
5202946193
5202946193
5202946193
5202946193
5202946193
5202946193
520...

result:

ok 9000 numbers

Test #5:

score: 0
Accepted
time: 559ms
memory: 174984kb

input:

4
500000 3000
303543765 129078653 192039183 226458565 208138322 436645868 210834986 135457074 162914826 137413668 192916902 146302909 434058637 370665799 433071720 460608259 413021067 44008462 416238964 258228162 317315155 28299542 422136622 102236305 489978791 223662501 132197157 47793593 265792210...

output:

50490529
50490529
50490529
50490529
50490529
50490529
50490529
50490529
50490529
50490529
50490529
50490529
50490529
50490529
50490529
50490529
50490529
50490529
50490529
50490529
50490529
50490529
50490529
50490529
50490529
50490529
50490529
50490529
50490529
50490529
50490529
50490529
50490529
504...

result:

ok 10000 numbers

Test #6:

score: 0
Accepted
time: 361ms
memory: 173960kb

input:

3
500000 895
688 1201 2221 3857 4357 4465 8482 8585 9839 11049 11429 11462 11467 12642 13620 14171 14220 14419 15332 17522 18107 18753 18851 18863 18915 20273 20374 20482 22320 22934 24333 25223 25947 26879 27015 27794 27850 29892 31082 31103 35023 35611 36010 36365 36452 36708 36830 37302 39844 427...

output:

102387246746
102601622426
102404770741
102607362161
102607362161
102607362161
102475496180
102558851848
102607403181
102607362161
102427271560
102593532165
102583224195
102607362161
102607362161
102607362161
102605413877
102607362161
102607362161
102607362161
102607362161
102607362161
102607362161
1...

result:

ok 9000 numbers

Test #7:

score: 0
Accepted
time: 582ms
memory: 177476kb

input:

4
500000 3000
807 3313 3431 3532 3653 4229 4574 5708 6325 7571 8354 11026 11363 17596 18919 20930 23420 25860 26462 27514 29428 30001 31416 33806 35417 35902 36640 37602 38082 40496 43170 44783 45474 46146 48538 49134 49711 55502 56776 56805 57172 62132 62994 66887 69086 70397 70840 71041 74735 7581...

output:

53400340472
53262820133
53408913719
53408913719
53139987488
53408913719
53391409768
53408913719
53297244457
53408913719
53408913719
53408913719
53408913719
53408913719
53408913719
53408913719
53370502963
53408913719
53408913719
53408913719
53408913719
53408913719
53183451361
53408913719
53250342681
...

result:

ok 10000 numbers

Test #8:

score: 0
Accepted
time: 416ms
memory: 175320kb

input:

3
500000 898
72235410 72235201 72234995 72234626 72234618 72234521 72234278 72234246 72234049 72233851 72233816 72233538 72233508 72233443 72233401 72233339 72233290 72233253 72233209 72233115 72233082 72233035 72232958 72232727 72232634 72232375 72232328 72232273 72232147 72231963 72231949 72231774...

output:

20193388372
20193082246
20193388372
20193388372
20137454774
20188193632
20193388372
20142612908
20193388372
20193388372
20193388372
20193388372
20193388372
20193388372
20138539830
20187126013
20193388372
20193388372
20193388372
20193388372
20186094266
20193388372
20193388372
20193388372
20193388372
...

result:

ok 9000 numbers

Test #9:

score: 0
Accepted
time: 574ms
memory: 173968kb

input:

4
500000 3000
940751349 940750988 940750901 940750476 940748407 940746205 940745797 940741835 940740148 940736196 940735197 940734866 940730194 940729360 940725799 940725665 940725655 940725053 940723831 940721542 940721363 940717981 940717755 940714833 940712714 940711645 940710684 940709233 940708...

output:

77887099213
77887099213
77887099213
77887099213
77887099213
77887099213
77887099213
77828029837
77887099213
77887099213
77671399735
77743075018
77549812395
77887099213
77887099213
77817237157
77887099213
77887099213
77887099213
77887099213
77887099213
77887099213
77887099213
77887099213
77887099213
...

result:

ok 10000 numbers

Test #10:

score: 0
Accepted
time: 372ms
memory: 173996kb

input:

3
500000 197
249644882 249644882 249644882 210710900 249644882 249644882 249644882 249644882 249644882 249644882 249644882 249644882 249644882 249644882 249644882 245319185 249644882 249644882 249644882 78092123 249644882 249644882 249644882 249644882 249644882 249644882 249644882 249644882 24964488...

output:

131507955421
131507955421
131507955421
131507955421
131507955421
131509822232
131507955421
131507955421
131507955421
131507955421
131507955421
131507955421
131507955421
131507955421
131507955421
131507955421
131507955421
131507955421
131507955421
131507955421
131507955421
131507955421
131507955421
1...

result:

ok 9000 numbers

Test #11:

score: 0
Accepted
time: 568ms
memory: 175116kb

input:

4
500000 3000
831 161289 161289 161289 161289 161289 161289 161289 161289 161289 161289 161289 161289 161289 161289 161289 161289 161289 161289 161289 161289 161289 161289 161289 128794 161289 161289 106109 161289 161289 161289 161289 161289 161289 161289 161289 161289 190991 161289 161289 161289 16...

output:

197826
197826
197826
197826
197826
197826
197826
197826
197826
197826
197826
197826
197826
197826
197826
197826
197826
197826
197826
197826
197826
197826
197826
197826
197826
197826
197826
197826
197826
197826
197826
197826
197826
197826
197826
197826
197826
197826
197826
197826
197826
197826
197826...

result:

ok 10000 numbers

Test #12:

score: 0
Accepted
time: 510ms
memory: 173936kb

input:

4
498000 3000
999999994 999999999 999999994 999999991 999999995 999999996 999999990 999999991 999999998 999999998 999999993 999999999 999999995 999999994 999999990 999999996 999999991 999999999 999999992 999999993 999999991 999999994 999999994 999999995 999999993 999999996 999999999 999999992 999999...

output:

165000000490
165000000794
165000000989
164999999136
165000001051
164999998817
165000001132
164999998874
164999998746
164999999349
165000000359
165000001251
165000000882
164999999400
164999999628
164999998782
165000001164
165000001353
164999998477
164999999056
165000001286
165000000562
164999998745
1...

result:

ok 10000 numbers