QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#852964#9727. Barkley IIIucup-team045#WA 0ms3596kbC++206.8kb2025-01-11 15:03:392025-01-11 15:03:40

Judging History

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

  • [2025-01-13 03:55:43]
  • hack成功，自动添加数据
  • (/hack/1447)
  • [2025-01-11 15:03:40]
  • 评测
  • 测评结果：WA
  • 用时：0ms
  • 内存：3596kb
查看
  • [2025-01-11 15:03:39]
  • 提交

answer

#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
using LL = long long;
using ULL = unsigned long long;

#include<iostream>
#include<cstring>
#include<vector>
#include<numeric>
#include<functional>
using namespace std;

const ULL ALL = (1ULL << 63) - 1;

// mask0, 区间全是1的位
// mask1, 区间只含一个0的位
struct Info{
    int len = 0;
    ULL mask0 = ALL, mask1 = 0;
};

struct Tag{
	ULL tag = ALL;
};

Info operator+(const Info &a, const Info &b){
    Info ret;
    ret.len = a.len + b.len;
    ret.mask0 = a.mask0 & b.mask0;
    ret.mask1 = (a.mask0 & b.mask1) | (a.mask1 & b.mask0);
    return ret;
}

void apply(Info &x, Tag &a, Tag f){
    x.mask0 &= f.tag;
    a.tag &= f.tag;
    if (x.len > 1) x.mask1 &= f.tag;
}

template<class Info, class Tag>
struct LazySegmentTree{
    int n;
    vector<Info> info;
    vector<Tag> tag;

    LazySegmentTree() {}

    LazySegmentTree(int n, Info _init = Info()){
        init(vector<Info>(n, _init));
    }

    LazySegmentTree(const vector<Info> &_init){
        init(_init);
    }

    void init(const vector<Info> &_init){
        n = (int)_init.size();
        info.assign((n << 2) + 1, Info());
        tag.assign((n << 2) + 1, Tag());
        function<void(int, int, int)> build = [&](int p, int l, int r){
            if (l == r){
                info[p] = _init[l - 1];
                return;
            }
            int m = (l + r) / 2;
            build(2 * p, l, m);
            build(2 * p + 1, m + 1, r);
            pull(p);
        };
        build(1, 1, n);
    }
    
    void pull(int p){
        info[p] = info[2 * p] + info[2 * p + 1];
    }
    
    void apply(int p, const Tag &v){
        ::apply(info[p], tag[p], v);
    }
    
    void push(int p){
        apply(2 * p, tag[p]);
        apply(2 * p + 1, tag[p]);
        tag[p] = Tag();
    }
    
    void modify(int p, int l, int r, int x, const Info &v){
        if (l == r){
            info[p] = v;
            return;
        }
        int m = (l + r) / 2;
        push(p);
        if (x <= m){
            modify(2 * p, l, m, x, v);
        } 
        else{
            modify(2 * p + 1, m + 1, r, x, v);
        }
        pull(p);
    }
    
    void modify(int p, const Info &v){
        modify(1, 1, n, p, v);
    }
    
    Info query(int p, int l, int r, int x, int y){
        if (l > y || r < x){
            return Info();
        }
        if (l >= x && r <= y){
            return info[p];
        }
        int m = (l + r) / 2;
        push(p);
        return query(2 * p, l, m, x, y) + query(2 * p + 1, m + 1, r, x, y);
    }
    
    Info query(int l, int r){
        return query(1, 1, n, l, r);
    }
    
    void modify(int p, int l, int r, int x, int y, const Tag &v){
        if (l > y || r < x){
            return;
        }
        if (l >= x && r <= y){
            apply(p, v);
            return;
        }
        int m = (l + r) / 2;
        push(p);
        modify(2 * p, l, m, x, y, v);
        modify(2 * p + 1, m + 1, r, x, y, v);
        pull(p);
    }
    
    void modify(int l, int r, const Tag &v){
        return modify(1, 1, n, l, r, v);
    }

    int find_first(int p, int l, int r, int L, int R, const function<bool(const Info&)> &f, Info &pre){
        if (l > R || r < L){
            return r + 1;
        }
        if (l >= L && r <= R){
            if (!f(pre + info[p])){
                pre = pre + info[p];
                return r + 1;
            }
            if (l == r) return r;
            int m = (l + r) / 2;
            push(p);
            int res;
            if (f(pre + info[2 * p])){
                res = find_first(2 * p, l, m, L, R, f, pre);
            }
            else{
                pre = pre + info[2 * p];
                res = find_first(2 * p + 1, m + 1, r, L, R, f, pre);
            }
            return res;
        }
        int m = (l + r) / 2;
        push(p);
        int res = m + 1;
        if (L <= m){
            res = find_first(2 * p, l, m, L, R, f, pre);
        }
        if (R > m && res == m + 1){
            res = find_first(2 * p + 1, m + 1, r, L, R, f, pre);
        }
        return res;
    }

    int find_first(int l, int r, const function<bool(const Info&)> &f){
        Info pre = Info();
        return find_first(1, 1, n, l, r, f, pre);
    }

    int find_last(int p, int l, int r, int L, int R, const function<bool(const Info&)> &f, Info &suf){
        if (l > R || r < L){
            return l - 1;
        }
        if (l >= L && r <= R){
            if (!f(info[p] + suf)){
                suf = info[p] + suf;
                return l - 1;
            }
            if (l == r) return r;
            int m = (l + r) / 2;
            push(p);
            int res;
            if (f(info[2 * p + 1] + suf)){
                res = find_last(2 * p + 1, m + 1, r, L, R, f, suf);
            }
            else{
                suf = info[2 * p + 1] + suf;
                res = find_last(2 * p, l, m, L, R, f, suf);
            }
            return res;
        }
        int m = (l + r) / 2;
        push(p);
        int res = m;
        if (R > m){
            res = find_last(2 * p + 1, m + 1, r, L, R, f, suf);
        }
        if (L <= m && res == m){
            res = find_last(2 * p, l, m, L, R, f, suf);
        }
        return res;        
    }

    int find_last(int l, int r, const function<bool(const Info&)> &f){
        Info suf = Info();
        return find_last(1, 1, n, l, r, f, suf);
    }
};

int main(){

#ifdef LOCAL
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif

    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    int n, q;
    cin >> n >> q;
    vector<Info> init(n);
    for(int i = 0; i < n; i++){
        ULL x;
        cin >> x;
        init[i] = {1, x, x ^ ALL};
    }
    LazySegmentTree<Info, Tag> seg(init);
    while(q--){
        int op;
        cin >> op;
        if (op == 1){
            int l, r; ULL x;
            cin >> l >> r >> x;
            seg.modify(l, r, {x});
        }
        else if (op == 2){
            int x; ULL y;
            cin >> x >> y;
            seg.modify(x, {1, y, y ^ ALL});
        }
        else{
            int l, r;
            cin >> l >> r;
            ULL val = seg.query(l, r).mask1;
            int pos = l;
            if (val != 0){
                int bit = __lg(val);

                auto f = [&](const Info &info){
                    return (info.mask0 >> bit & 1) == 0;
                };

                pos = seg.find_first(l, r, f);
            }
            cout << (seg.query(l, pos - 1).mask0 & seg.query(pos + 1, r).mask0) << '\n';
        }
    }

}
源文件, 语言: C++20

詳細信息

Test #1:

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

input:

5 9
7 7 7 6 7
3 1 5
2 1 3
3 1 5
3 1 3
1 1 2 3
3 1 3
2 2 8
3 1 3
3 1 2

output:

7
6
7
3
3
8

result:

ok 6 lines

Test #2:

score: 0
Accepted
time: 0ms
memory: 3532kb

input:

10 10
6760061359215711796 1568091718842717482 1568091718842717482 1568091718842717482 5232472783634052627 8795942500783873690 1568091718842717482 1568091718842717482 1568091718842717482 1568091718842717482
1 3 5 7587422031989082829
3 6 10
1 7 8 5197616143400216932
2 4 2518604563805514908
2 2 4533959...

output:

1568091718842717482
35184908959744
176025477579040
8795942500783873690

result:

ok 4 lines

Test #3:

score: -100
Wrong Answer
time: 0ms
memory: 3596kb

input:

100 100
4263579105072360993 4263579105072360993 4263579105072360993 4263579105072360993 4263579105072360993 4263579105072360993 4263579105072360993 4263579105072360993 4263579105072360993 625967318191814868 4263579105072360993 4263579105072360993 4263579105072360993 4263579105072360993 4263579105072...

output:

576531121047601152
1
576460752303423488
4263579105072360993
1306043896232411137
4263579105072360993
576531121047601152
633397148123136
0
1153488865559840256
562951027425280
1730020640668059136
3533641810948498945
67108864
1730020640668059136
0
633397148123136
1729382296723653632
0
173002064066805913...

result:

wrong answer 11th lines differ - expected: '1152922054496880128', found: '562951027425280'
English 繁體中文 简体中文

伺服器時間: 2025-02-01 18:02:09 | 開源專案