Submission #71490945 - AtCoder Beginner Contest 435

Contest Duration: 2025-12-06 21:00:00+0900 - 2025-12-06 22:40:00+0900 (local time) (100 minutes) Back to Home

Submission #71490945

Source Code Expand

#include<bits/stdc++.h>
using namespace std;

namespace atcoder {
namespace internal {
long long ceil_pow2(long long n) {
    long long x = 0;
    while ((1U << x) < (unsigned long long)(n)) x++;
    return x;
}
long long bsf(unsigned long long n) {
#ifdef _MSC_VER
    unsigned long index;
    _BitScanForward(&index, n);
    return index;
#else
    return __builtin_ctz(n);
#endif
}
}
}

namespace atcoder {
template <class S,
          S (*op)(S, S),
          S (*e)(),
          class F,
          S (*mapping)(F, S),
          F (*composition)(F, F),
          F (*id)()>
struct lazy_segtree {
  public:
    lazy_segtree() : lazy_segtree(0) {}
    lazy_segtree(long long n) : lazy_segtree(std::vector<S>(n, e())) {}
    lazy_segtree(const std::vector<S>& v) : _n(int(v.size())) {
        log = internal::ceil_pow2(_n);
        size = 1 << log;
        d = std::vector<S>(2 * size, e());
        lz = std::vector<F>(size, id());
        for (long long i = 0; i < _n; i++) d[size + i] = v[i];
        for (long long i = size - 1; i >= 1; i--) {
            update(i);
        }
    }

    void set(long long p, S x) {
        assert(0 <= p && p < _n);
        p += size;
        for (long long i = log; i >= 1; i--) push(p >> i);
        d[p] = x;
        for (long long i = 1; i <= log; i++) update(p >> i);
    }

    S get(long long p) {
        assert(0 <= p && p < _n);
        p += size;
        for (long long i = log; i >= 1; i--) push(p >> i);
        return d[p];
    }

    S prod(long long l, long long r) {
        assert(0 <= l && l <= r && r <= _n);
        if (l == r) return e();

        l += size;
        r += size;

        for (long long i = log; i >= 1; i--) {
            if (((l >> i) << i) != l) push(l >> i);
            if (((r >> i) << i) != r) push(r >> i);
        }

        S sml = e(), smr = e();
        while (l < r) {
            if (l & 1) sml = op(sml, d[l++]);
            if (r & 1) smr = op(d[--r], smr);
            l >>= 1;
            r >>= 1;
        }

        return op(sml, smr);
    }

    S all_prod() { return d[1]; }

    void apply(long long p, F f) {
        assert(0 <= p && p < _n);
        p += size;
        for (long long i = log; i >= 1; i--) push(p >> i);
        d[p] = mapping(f, d[p]);
        for (long long i = 1; i <= log; i++) update(p >> i);
    }
    void apply(long long l, long long r, F f) {
        assert(0 <= l && l <= r && r <= _n);
        if (l == r) return;

        l += size;
        r += size;

        for (long long i = log; i >= 1; i--) {
            if (((l >> i) << i) != l) push(l >> i);
            if (((r >> i) << i) != r) push((r - 1) >> i);
        }

        {
            long long l2 = l, r2 = r;
            while (l < r) {
                if (l & 1) all_apply(l++, f);
                if (r & 1) all_apply(--r, f);
                l >>= 1;
                r >>= 1;
            }
            l = l2;
            r = r2;
        }

        for (long long i = 1; i <= log; i++) {
            if (((l >> i) << i) != l) update(l >> i);
            if (((r >> i) << i) != r) update((r - 1) >> i);
        }
    }

    template <bool (*g)(S)> long long max_right(long long l) {
        return max_right(l, [](S x) { return g(x); });
    }
    template <class G> long long max_right(long long l, G g) {
        assert(0 <= l && l <= _n);
        assert(g(e()));
        if (l == _n) return _n;
        l += size;
        for (long long i = log; i >= 1; i--) push(l >> i);
        S sm = e();
        do {
            while (l % 2 == 0) l >>= 1;
            if (!g(op(sm, d[l]))) {
                while (l < size) {
                    push(l);
                    l = (2 * l);
                    if (g(op(sm, d[l]))) {
                        sm = op(sm, d[l]);
                        l++;
                    }
                }
                return l - size;
            }
            sm = op(sm, d[l]);
            l++;
        } while ((l & -l) != l);
        return _n;
    }
    template <bool (*g)(S)> long long min_left(long long r) {
        return min_left(r, [](S x) { return g(x); });
    }
    template <class G> long long min_left(long long r, G g) {
        assert(0 <= r && r <= _n);
        assert(g(e()));
        if (r == 0) return 0;
        r += size;
        for (long long i = log; i >= 1; i--) push((r - 1) >> i);
        S sm = e();
        do {
            r--;
            while (r > 1 && (r % 2)) r >>= 1;
            if (!g(op(d[r], sm))) {
                while (r < size) {
                    push(r);
                    r = (2 * r + 1);
                    if (g(op(d[r], sm))) {
                        sm = op(d[r], sm);
                        r--;
                    }
                }
                return r + 1 - size;
            }
            sm = op(d[r], sm);
        } while ((r & -r) != r);
        return 0;
    }

  private:
    long long _n, size, log;
    std::vector<S> d;
    std::vector<F> lz;

    void update(long long k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
    void all_apply(long long k, F f) {
        d[k] = mapping(f, d[k]);
        if (k < size) lz[k] = composition(f, lz[k]);
    }
    void push(long long k) {
        all_apply(2 * k, lz[k]);
        all_apply(2 * k + 1, lz[k]);
        lz[k] = id();
    }
};
}

//-----------------------------------区間加算、区間最小値---------------------
/*
using S = long long;
using F = long long;

const S INF = 8e18;

S op(S a, S b){ return std::min(a, b); }
S e(){ return INF; }
S mapping(F f, S x){ return f+x; }
F composition(F f, F g){ return f+g; }
F id(){ return 0; }

signed main(){
    long long n;
    std::vector<S> v(n);
    atcoder::lazy_segtree<S, op, e, F, mapping, composition, id> seg(v);
}
*/

//-----------------------------------区間加算、区間最大値---------------------
/*
using S = long long;
using F = long long;

const S INF = 8e18;

S op(S a, S b){ return std::max(a, b); }
S e(){ return -INF; }
S mapping(F f, S x){ return f+x; }
F composition(F f, F g){ return f+g; }
F id(){ return 0; }

signed main(){
    long long n;
    std::vector<S> v(n);
    atcoder::lazy_segtree<S, op, e, F, mapping, composition, id> seg(v);
}
*/

//-----------------------------------区間加算、区間和--------------------------
/*
struct S{
    long long value;
    long long size;
};
using F = long long;

S op(S a, S b){ return {a.value+b.value, a.size+b.size}; }
S e(){ return {0, 0}; }
S mapping(F f, S x){ return {x.value + f*x.size, x.size}; }
F composition(F f, F g){ return f+g; }
F id(){ return 0; }

signed main(){
    long long n;
    std::vector<S> v(n, {0, 1});
    atcoder::lazy_segtree<S, op, e, F, mapping, composition, id> seg(v);
}
*/

//-----------------------------------区間変更、区間最小値-----------------
/*
using S = long long;
using F = long long;

const S INF = 8e18;
const F ID = 8e18;

S op(S a, S b){ return std::min(a, b); }
S e(){ return INF; }
S mapping(F f, S x){ return (f == ID ? x : f); }
F composition(F f, F g){ return (f == ID ? g : f); }
F id(){ return ID; }

signed main(){
    long long n;
    std::vector<S> v(n);
    atcoder::lazy_segtree<S, op, e, F, mapping, composition, id> seg(v);
}
*/

//-----------------------------------区間変更、区間最大値-----------------
/*
using S = long long;
using F = long long;

const S INF = 8e18;
const F ID = 8e18;

S op(S a, S b){ return std::max(a, b); }
S e(){ return -INF; }
S mapping(F f, S x){ return (f == ID ? x : f); }
F composition(F f, F g){ return (f == ID ? g : f); }
F id(){ return ID; }

signed main(){
    long long n;
    std::vector<S> v(n);
    atcoder::lazy_segtree<S, op, e, F, mapping, composition, id> seg(v);
}
*/

//-----------------------------------区間変更、区間和-----------------

struct S{
    long long value;
    long long size;
};
using F = long long;

const F ID = 8e18;

S op(S a, S b){ return {a.value+b.value, a.size+b.size}; }
S e(){ return {0, 0}; }
S mapping(F f, S x){
    if(f != ID) x.value = f*x.size;
    return x;
}
F composition(F f, F g){ return (f == ID ? g : f); }
F id(){ return ID; }

signed main(){
    long long n,q;cin>>n>>q;
    std::vector<S> v(n, {0, 1});
    atcoder::lazy_segtree<S, op, e, F, mapping, composition, id> seg(v);
    seg.apply(0,n,1);
    for(int i=0;i<q;i++){
        int l,r;cin>>l>>r;l--;r--;
        seg.apply(l,r+1,0);
        cout<<seg.prod(0,n).value<<"\n";
    }
}

//---------------------------------------------------------------------

// 上のコメント化を外して使う

/*

[更新]
sからtまで(s以上t+1未満)に値xで操作する
seg.apply(s, t+1, x);

[クエリ]
sからtまで(s以上t+1未満)にクエリを行い、答えが返り値である

「区間min,maxの場合」
seg.prod(s, t+1)

「区間和の場合」
seg.prod(s, t+1).value

*/

Submission Info

Submission Time	2025-12-06 21:25:35+0900
Task	E - Cover query
User	Sabakanmelm
Language	C++23 (GCC 15.2.0)
Score	0
Code Size	9156 Byte
Status	RE
Exec Time	105 ms
Memory	3756 KiB

Judge Result

Set Name

Sample

All

Score / Max Score

0 / 0

0 / 450

Status

AC	× 1
RE	× 1

AC	× 3
RE	× 39

Set Name	Test Cases
Sample	example_00.txt, example_01.txt
All	example_00.txt, example_01.txt, hand_00.txt, hand_01.txt, hand_02.txt, hand_03.txt, hand_04.txt, hand_05.txt, hand_06.txt, hand_07.txt, hand_08.txt, hand_09.txt, hand_10.txt, hand_11.txt, random_00.txt, random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, random_16.txt, random_17.txt, random_18.txt, random_19.txt, random_20.txt, random_21.txt, random_22.txt, random_23.txt, random_24.txt, random_25.txt, random_26.txt, random_27.txt

Case Name	Status	Exec Time	Memory
example_00.txt	AC	2 ms	3524 KiB
example_01.txt	RE	94 ms	3712 KiB
hand_00.txt	RE	91 ms	3424 KiB
hand_01.txt	RE	92 ms	3536 KiB
hand_02.txt	RE	91 ms	3624 KiB
hand_03.txt	RE	89 ms	3536 KiB
hand_04.txt	RE	89 ms	3632 KiB
hand_05.txt	RE	89 ms	3624 KiB
hand_06.txt	RE	90 ms	3568 KiB
hand_07.txt	RE	91 ms	3712 KiB
hand_08.txt	RE	91 ms	3536 KiB
hand_09.txt	RE	92 ms	3536 KiB
hand_10.txt	AC	105 ms	3496 KiB
hand_11.txt	AC	105 ms	3576 KiB
random_00.txt	RE	90 ms	3720 KiB
random_01.txt	RE	91 ms	3756 KiB
random_02.txt	RE	89 ms	3424 KiB
random_03.txt	RE	88 ms	3636 KiB
random_04.txt	RE	90 ms	3536 KiB
random_05.txt	RE	91 ms	3656 KiB
random_06.txt	RE	91 ms	3632 KiB
random_07.txt	RE	91 ms	3536 KiB
random_08.txt	RE	92 ms	3744 KiB
random_09.txt	RE	92 ms	3484 KiB
random_10.txt	RE	92 ms	3424 KiB
random_11.txt	RE	91 ms	3720 KiB
random_12.txt	RE	91 ms	3712 KiB
random_13.txt	RE	89 ms	3720 KiB
random_14.txt	RE	90 ms	3636 KiB
random_15.txt	RE	90 ms	3720 KiB
random_16.txt	RE	90 ms	3696 KiB
random_17.txt	RE	91 ms	3628 KiB
random_18.txt	RE	91 ms	3756 KiB
random_19.txt	RE	89 ms	3424 KiB
random_20.txt	RE	91 ms	3576 KiB
random_21.txt	RE	91 ms	3720 KiB
random_22.txt	RE	92 ms	3532 KiB
random_23.txt	RE	91 ms	3704 KiB
random_24.txt	RE	91 ms	3704 KiB
random_25.txt	RE	91 ms	3484 KiB
random_26.txt	RE	93 ms	3452 KiB
random_27.txt	RE	92 ms	3484 KiB