Submission #72694021 - JPRS Programming Contest 2026#1 (AtCoder Beginner Contest 442)

Contest Duration: 2026-01-24 21:00:00+0900 - 2026-01-24 22:40:00+0900 (local time) (100 minutes) Back to Home

Submission #72694021

Source Code Expand

#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;
}

Submission Info

Submission Time	2026-01-24 21:14:41+0900
Task	D - Swap and Range Sum
User	Hirasawaa
Language	C++23 (GCC 15.2.0)
Score	400
Code Size	4174 Byte
Status	AC
Exec Time	366 ms
Memory	33040 KiB

Compile Error

./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;
      |                   ~~~^~~~

Judge Result

Set Name

Sample

All

Score / Max Score

0 / 0

400 / 400

Status

× 2

× 29

Set Name	Test Cases
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

Case Name	Status	Exec Time	Memory
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