提出 #72694021

ソースコード 拡げる

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

#define int long long

const int N = 2e5 + 1;
const int M = 998244353;
template <class Info, class Tag>
class LazySegmentTree
{
public:
    int n;
    vector<Info> info;
    vector<Tag> tag;
    LazySegmentTree() : n(0) {};
    LazySegmentTree(int _n, Info _v = Info()) { init(_n, _v); }
    template <class T>
    LazySegmentTree(vector<T> _init)
    {
        init(_init);
    }
    void init(int _n, Info _v = Info()) { init(vector(_n, _v)); }
    template <class T>
    void init(vector<T> _init)
    {
        n = _init.size() - 1;
        info.assign(n << 2 + 1, Info());
        tag.assign(n << 2 + 1, Tag());
        auto build = [&](auto build, int p, int l, int r)
        {
            if (r == l)
            {
                info[p] = _init[l];
                return;
            }
            int mid = l + r >> 1;
            build(build, p << 1, l, mid);
            build(build, p << 1 | 1, mid + 1, r);
            pushup(p);
        };
        build(build, 1, 1, n);
    }
    void pushup(int p) { info[p] = info[p << 1] + info[p << 1 | 1]; }
    void apply(int p, const Tag &v, int len)
    {
        info[p].apply(v, len);
        tag[p].apply(v);
    }
    void pushdown(int p, int pl, int pr)
    {
        int mid = pl + pr >> 1;
        apply(p << 1, tag[p], mid - pl + 1);
        apply(p << 1 | 1, tag[p], pr - mid);
        tag[p] = Tag();
    }
    void modify(int p, int pl, int pr, int x, const Info &v)
    {
        if (pl == pr)
        {
            info[p].apply(v);
            return;
        }
        int mid = pl + pr >> 1;
        pushdown(p, pl, pr);
        if (x <= mid)
            modify(p << 1, pl, mid, x, v);
        else
            modify(p << 1 | 1, mid + 1, pr, x, v);
        pushup(p);
    }
    void modify(int p, const Info &v) { modify(1, 1, n, p, v); }
    Info query(int l, int r, int p, int pl, int pr)
    {
        if (pl > r || pr < l)
        {
            return Info();
        }
        if (l <= pl && pr <= r)
        {
            return info[p];
        }
        int mid = pl + pr >> 1;
        pushdown(p, pl, pr);
        return query(l, r, p << 1, pl, mid) + query(l, r, p << 1 | 1, mid + 1, pr);
    }
    Info query(int l, int r) { return query(l, r, 1, 1, n); }
    void modifyRange(int l, int r, int p, int pl, int pr, const Tag &v)
    {
        if (pl > r || pr < l)
        {
            return;
        }
        if (l <= pl && r >= pr)
        {
            apply(p, v, pr - pl + 1);
            return;
        }
        int mid = pl + pr >> 1;
        pushdown(p, pl, pr);
        modifyRange(l, r, p << 1, pl, mid, v);
        modifyRange(l, r, p << 1 | 1, mid + 1, pr, v);
        pushup(p);
    }
    void modifyRange(int l, int r, const Tag &v)
    {
        modifyRange(l, r, 1, 1, n, v);
    }
};
struct Tag
{
    int add;
    Tag(int _add = 0) : add(_add) {}
    void apply(Tag t) { add += t.add; }
};
struct Info
{
    int k;
    void apply(Info v) { k = v.k; }
    void apply(Tag t, int len) { k = k + len * t.add; }
};
Info operator+(Info a, Info b)
{
    Info c;
    c.k = a.k + b.k;
    return c;
}
void solve()
{
    int n, q;
    cin >> n >> q;
    vector<Info> b(n + 1);
    for (int i = 1; i <= n; i++)
    {
        int x;
        cin >> x;
        b[i].k = x;
    }
    LazySegmentTree<Info, Tag> tr(b);
    while (q--)
    {
        int op;
        cin >> op;
        if (op == 1)
        {
            int x;
            cin >> x;

            int temp = tr.query(x + 1, x + 1).k;
            int temp2 = tr.query(x, x).k;
            tr.modify(x, Info{temp});
            tr.modify(x + 1, Info{temp2});
        }
        else if (op == 2)
        {
            int l, r;
            cin >> l >> r;
            cout << tr.query(l, r).k << "\n";
        }
    }
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1;
    //   cin >> T;

    while (T--)
        solve();

    return 0;
}

提出情報

提出日時
問題 D - Swap and Range Sum
ユーザ Hirasawaa
言語 C++23 (GCC 15.2.0)
得点 400
コード長 4174 Byte
結果 AC
実行時間 366 ms
メモリ 33040 KiB

コンパイルエラー

./Main.cpp: In instantiation of 'void LazySegmentTree<Info, Tag>::init(std::vector<T>) [with T = Info; Info = Info; Tag = Tag]':
./Main.cpp:24:13:   required from 'LazySegmentTree<Info, Tag>::LazySegmentTree(std::vector<T>) [with T = Info; Info = Info; Tag = Tag]'
   24 |         init(_init);
      |         ~~~~^~~~~~~
./Main.cpp:142:36:   required from here
  142 |     LazySegmentTree<Info, Tag> tr(b);
      |                                    ^
./Main.cpp:31:28: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   31 |         info.assign(n << 2 + 1, Info());
      |                          ~~^~~
./Main.cpp:32:27: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   32 |         tag.assign(n << 2 + 1, Tag());
      |                         ~~^~~
./Main.cpp: In instantiation of 'LazySegmentTree<Info, Tag>::init<Info>(std::vector<Info>)::<lambda(auto:64, long long int, long long int, long long int)> [with auto:64 = LazySegmentTree<Info, Tag>::init<Info>(std::vector<Info>)::<lambda(auto:64, long long int, long long int, long long int)>]':
./Main.cpp:45:14:   required from 'void LazySegmentTree<Info, Tag>::init(std::vector<T>) [with T = Info; Info = Info; Tag = Tag]'
   45 |         build(build, 1, 1, n);
      |         ~~~~~^~~~~~~~~~~~~~~~
./Main.cpp:24:13:   required from 'LazySegmentTree<Info, Tag>::LazySegmentTree(std::vector<T>) [with T = Info; Info = Info; Tag = Tag]'
   24 |         init(_init);
      |         ~~~~^~~~~~~
./Main.cpp:142:36:   required from here
  142 |     LazySegmentTree<Info, Tag> tr(b);
      |                                    ^
./Main.cpp:40:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   40 |             int mid = l + r >> 1;
      |                       ~~^~~
./Main.cpp: In instantiation of 'Info LazySegmentTree<Info, Tag>::query(long long int, long long int, long long int, long long int, long long int) [with Info = Info; Tag = Tag]':
./Main.cpp:90:44:   required from 'Info LazySegmentTree<Info, Tag>::query(long long int, long long int) [with Info = Info; Tag = Tag]'
   90 |     Info query(int l, int r) { return query(l, r, 1, 1, n); }
      |                                       ~~~~~^~~~~~~~~~~~~~~
./Main.cpp:152:32:   required from here
  152 |             int temp = tr.query(x + 1, x + 1).k;
      |                        ~~~~~~~~^~~~~~~~~~~~~~
./Main.cpp:86:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   86 |         int mid = pl + pr >> 1;
      |                   ~~~^~~~
./Main.cpp: In instantiation of 'void LazySegmentTree<Info, Tag>::modify(long long int, long long int, long long int, long long int, const Info&) [with Info = Info; Tag = Tag]':
./Main.cpp:75:47:   required from 'void LazySegmentTree<Info, Tag>::modify(long long int, const Info&) [with Info = Info; Tag = Tag]'
   75 |     void modify(int p, const Info &v) { modify(1, 1, n, p, v); }
      |                                         ~~~~~~^~~~~~~~~~~~~~~
./Main.cpp:154:22:   required from here
  154 |             tr.modify(x, Info{temp});
      |             ~~~~~~~~~^~~~~~~~~~~~~~~
./Main.cpp:67:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   67 |         int mid = pl + pr >> 1;
      |                   ~~~^~~~
./Main.cpp: In instantiation of 'void LazySegmentTree<Info, Tag>::pushdown(long long int, long long int, long long int) [with Info = Info; Tag = Tag]':
./Main.cpp:87:9:   required from 'Info LazySegmentTree<Info, Tag>::query(long long int, long long int, long long int, long long int, long long int) [with Info = Info; Tag = Tag]'
   87 |         pushdown(p, pl, pr);
      |         ^~~~~~~~
./Main.cpp:90:44:   required from 'Info LazySegmentTree<Info, Tag>::query(long long int, long long int) [with Info = Info; Tag = Tag]'
   90 |     Info query(int l, int r) { return query(l, r, 1, 1, n); }
      |                                       ~~~~~^~~~~~~~~~~~~~~
./Main.cpp:152:32:   required from here
  152 |             int temp = tr.query(x + 1, x + 1).k;
      |                        ~~~~~~~~^~~~~~~~~~~~~~
./Main.cpp:55:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   55 |         int mid = pl + pr >> 1;
      |                   ~~~^~~~

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 400 / 400
結果
AC × 2
AC × 29
セット名 テストケース
Sample 00_sample_00.txt, 00_sample_01.txt
All 00_sample_00.txt, 00_sample_01.txt, 01_random_00.txt, 01_random_01.txt, 01_random_02.txt, 01_random_03.txt, 01_random_04.txt, 01_random_05.txt, 01_random_06.txt, 01_random_07.txt, 01_random_08.txt, 01_random_09.txt, 01_random_10.txt, 01_random_11.txt, 01_random_12.txt, 01_random_13.txt, 01_random_14.txt, 01_random_15.txt, 01_random_16.txt, 01_random_17.txt, 01_random_18.txt, 01_random_19.txt, 01_random_20.txt, 01_random_21.txt, 01_random_22.txt, 01_random_23.txt, 02_handmade_00.txt, 02_handmade_01.txt, 02_handmade_02.txt
ケース名 結果 実行時間 メモリ
00_sample_00.txt AC 2 ms 3552 KiB
00_sample_01.txt AC 1 ms 3512 KiB
01_random_00.txt AC 275 ms 31448 KiB
01_random_01.txt AC 307 ms 32980 KiB
01_random_02.txt AC 305 ms 31368 KiB
01_random_03.txt AC 308 ms 31864 KiB
01_random_04.txt AC 322 ms 32316 KiB
01_random_05.txt AC 331 ms 31772 KiB
01_random_06.txt AC 343 ms 32376 KiB
01_random_07.txt AC 366 ms 31188 KiB
01_random_08.txt AC 347 ms 30992 KiB
01_random_09.txt AC 357 ms 32164 KiB
01_random_10.txt AC 346 ms 31188 KiB
01_random_11.txt AC 189 ms 32964 KiB
01_random_12.txt AC 212 ms 32852 KiB
01_random_13.txt AC 236 ms 32980 KiB
01_random_14.txt AC 249 ms 33040 KiB
01_random_15.txt AC 276 ms 32976 KiB
01_random_16.txt AC 289 ms 33040 KiB
01_random_17.txt AC 308 ms 32900 KiB
01_random_18.txt AC 325 ms 32976 KiB
01_random_19.txt AC 334 ms 32860 KiB
01_random_20.txt AC 355 ms 32980 KiB
01_random_21.txt AC 365 ms 32960 KiB
01_random_22.txt AC 285 ms 32932 KiB
01_random_23.txt AC 287 ms 32976 KiB
02_handmade_00.txt AC 2 ms 3608 KiB
02_handmade_01.txt AC 1 ms 3488 KiB
02_handmade_02.txt AC 83 ms 32960 KiB