QOJ.ac

QOJ

IDSubmission IDProblemHackerOwnerResultSubmit timeJudge time
#911#591780#9302. Caesar Ciphership2077lonelywolfSuccess!2024-09-26 18:55:562024-09-26 18:55:56

Details

Extra Test:

Wrong Answer
time: 7ms
memory: 11400kb

input:

100 1
17 0 0 0 3 1 3 18 11 4 5 3 6 4 0 0 5 0 0 7 0 0 0 0 0 0 0 0 0 0 0 0 10 0 1 17 0 0 0 0 0 0 0 0 0 0 7 6 13 0 0 13 6 7 0 0 0 0 0 0 0 0 0 0 17 1 0 10 0 0 0 0 0 0 0 0 0 0 0 0 7 0 0 5 0 0 4 6 3 5 4 11 18 3 1 3 0 0 0 17
2 1 51 50

output:

yes

result:

wrong answer expected NO, found YES [1st token]

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#591780#9302. Caesar CipherlonelywolfWA 1362ms59924kbC++205.7kb2024-09-26 17:46:292024-09-26 18:56:22

answer

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

constexpr int N = 500000;
constexpr int B = 516;
constexpr array<int, 2> mod = {998244353, 1000000007};

using ll = long long;

int p[N + 10][2];
int s[N + 10][2];
void init() {
	p[0][0] = p[0][1] = 1;
	s[1][0] = s[1][1] = 1;
	for (int t = 0; t < 2; t++) {
		for (int i = 1; i <= N; i++) {
			p[i][t] = 1LL * p[i - 1][t] * B % mod[t];
			s[i + 1][t] = (p[i][t] + s[i][t]) % mod[t];
		}
	}
}

template<class Info, class Tag>
struct LazySegmentTree {
    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_ + 1, v_));
    }
    template<class T>
    void init(vector<T> init_) {
        n = init_.size() - 1;
        info.assign(4 << __lg(n) + 1, Info());
        tag.assign(4 << __lg(n) + 1, Tag());
        function<void(int, int, int)> build = [&](int p, int l, int r) {
            if (l == r) {
                info[p] = init_[l];
                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) {
        info[p].apply(v);
        tag[p].apply(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 rangeQuery(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 rangeQuery(2 * p, l, m, x, y) + rangeQuery(2 * p + 1, m + 1, r, x, y);
    }
    Info rangeQuery(int l, int r) {
        return rangeQuery(1, 1, n, l, r);
    }
    void rangeApply(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);
        rangeApply(2 * p, l, m, x, y, v);
        rangeApply(2 * p + 1, m + 1, r, x, y, v);
        pull(p);
    }
    void rangeApply(int l, int r, const Tag &v) {
        return rangeApply(1, 1, n, l, r, v);
    }
    void work(int p, int l, int r) {
    	if (info[p].mx != 65536) {
    		return;
    	}
    	if (l == r) {
    		info[p].work();
    		return;
    	}
    	int m = (l + r) / 2;
    	push(p);
    	work(2 * p, l, m);
    	work(2 * p + 1, m + 1, r);
    	pull(p);
    }
	template<class F>
    int findFirst(int p, int l, int r, int x, int y, F pred) {
        if (l > y || r < x || !pred(info[p])) {
            return -1;
        }
        if (l == r) {
            return l;
        }
        int m = (l + r) / 2;
        push(p);
        int res = findFirst(2 * p, l, m, x, y, pred);
        if (res == -1) {
            res = findFirst(2 * p + 1, m + 1, r, x, y, pred);
        }
        return res;
    }
    template<class F>
    int findFirst(int l, int r, F pred) {
        return findFirst(1, 1, n, l, r, pred);
    }
    template<class F>
    int findLast(int p, int l, int r, int x, int y, F pred) {
        if (l > y || r < x || !pred(info[p])) {
            return -1;
        }
        if (l == r) {
            return l;
        }
        int m = (l + r) / 2;
        push(p);
        int res = findLast(2 * p + 1, m + 1, r, x, y, pred);
        if (res == -1) {
            res = findLast(2 * p, l, m, x, y, pred);
        }
        return res;
    }
    template<class F>
    int findLast(int l, int r, F pred) {
        return findLast(1, 1, n, l, r, pred);
    }
};
struct Tag {
    int d = 0;
    void apply(Tag t) {
    	d += t.d;
	}
};
struct Info {
	array<int, 2> val {0, 0};
    int len = 0;
    int mx = 0;
    void apply(Tag t) {
    	mx += t.d;
    	for (int i = 0; i < 2; i++) {
    		val[i] = (1LL * t.d * s[len][i] % mod[i] + val[i]) % mod[i];
    	}
	}
	void work() {
		mx = 0;
		val = {0, 0};
	}
};
Info operator+(Info a, Info b) {
    Info ret;
    ret.len = a.len + b.len;
    ret.mx = max(a.mx, b.mx);
    for (int t = 0; t < 2; t++) {
    	ret.val[t] = (1LL * a.val[t] * p[b.len][t] % mod[t] + b.val[t]) % mod[t];
    }
    return ret;
}

signed main() {  
    ios::sync_with_stdio(false);
    cin.tie(nullptr);  

    init();

    int n, q;
	cin >> n >> q;

	LazySegmentTree<Info, Tag> tr(n);
	for (int i = 1; i <= n; i++) {
		int x;
		cin >> x;
		tr.modify(i, {{x % mod[0], x % mod[1]}, 1, x});
	}

	while (q--) {
		int o;
		cin >> o;

		if (o == 1) {
			int l, r;
			cin >> l >> r;
			tr.rangeApply(l, r, {1});
			tr.work(1, 1, n);
		} else {
			int x, y, L;
			cin >> x >> y >> L;

			auto v1 = tr.rangeQuery(x, min(n, x + L - 1));
			auto v2 = tr.rangeQuery(y, min(n, y + L - 1));
			
			if (v1.val == v2.val && v1.len == v2.len) {
				cout << "yes\n";
			} else {
				cout << "no\n";
			}
		}
	}

    return 0;
}