QOJ.ac

QOJ

ID提交记录ID题目HackerOwner结果提交时间测评时间
#884#583720#9302. Caesar Ciphership2077retired_midlightsFailed.2024-09-23 07:19:092024-09-23 07:19:11

詳細信息

Extra Test:

Invalid Input

input:

400 4
1 15 21 1 2 9 12 9 23 15 21 1 21 18 1 1 10 1 1 1 1 1 19 14 22 1 1 1 6 20 1 5 21 1 8 17 1 1 8 1 1 1 1 1 1 1 21 1 1 18 18 1 1 21 1 1 1 1 1 1 1 8 1 1 17 8 1 21 5 1 20 6 1 1 1 22 14 19 1 1 1 1 1 10 1 1 18 21 1 21 15 23 9 12 9 2 1 21 15 1 1 1 16 1 1 1 23 7 1 1 6 17 19 1 7 1 1 1 1 15 1 23 15 15 1 1 ...

output:


result:

FAIL Unexpected character #10, but ' ' expected (stdin, line 2)

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#583720#9302. Caesar Cipherretired_midlightsWA 596ms23300kbC++143.7kb2024-09-22 21:33:112024-09-23 07:21:42

answer

#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (int)a; i <= (int)b; i ++)
#define ll long long
#define ls p << 1
#define rs p << 1 | 1
using namespace std;

const int maxn = 500010;
int base = 19260817, mod = 1e9 + 7;

struct Info {
    int tag, mx, hsh;
} t[maxn << 2];

int n, q, a[maxn], power[maxn], sum[maxn];

void push_up(int p, int l, int r) {
    t[p].mx = max(t[ls].mx, t[rs].mx);
    int mid = (l + r) >> 1;
    t[p].hsh = (1ll * t[ls].hsh * power[r - mid] % mod + t[rs].hsh) % mod;
}

void build(int p, int l, int r) {
    t[p].tag = 0;
    if(l == r) {
        t[p].mx = t[p].hsh = a[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(ls, l, mid), build(rs, mid + 1, r);
    push_up(p, l, r);
}

void push_down(int p, int l, int r) {
    t[ls].tag += t[p].tag, t[rs].tag += t[p].tag;
    t[ls].mx += t[p].tag, t[rs].mx += t[p].tag;
    int mid = (l + r) >> 1;
    t[ls].hsh = (t[ls].hsh + 1ll * sum[mid - l] * t[p].tag % mod) % mod;
    t[rs].hsh = (t[rs].hsh + 1ll * sum[r - (mid + 1)] * t[p].tag % mod) % mod;
    t[p].tag = 0;
}

void modify_force(int p, int l, int r) {
    // cout << p << " " << l << " " << r << endl;
    if(l == r) {
        t[p].mx %= 65536;
        t[p].hsh = t[p].mx;
        return;
    }
    if(t[p].tag) push_down(p, l, r);
    int mid = (l + r) >> 1;
    if(t[ls].mx >= 65536) modify_force(ls, l, mid);
    if(t[rs].mx >= 65536) modify_force(rs, mid + 1, r);
    push_up(p, l, r);
}

void modify(int p, int l, int r, int ql, int qr) {
    if(ql <= l && r <= qr) {
        t[p].tag ++;
        t[p].mx ++;
        t[p].hsh = (t[p].hsh + sum[r - l]) % mod;
        if(t[p].mx >= 65536) {
            modify_force(p, l, r);
        }
        return;
    }
    if(t[p].tag) push_down(p, l, r);
    int mid = (l + r) >> 1;
    if(ql <= mid) modify(ls, l, mid, ql, qr);
    if(qr > mid) modify(rs, mid + 1, r, ql, qr);
    push_up(p, l, r);
}

int query(int p, int l, int r, int ql, int qr) {
    if(ql <= l && r <= qr) return t[p].hsh;
    int mid = (l + r) >> 1;
    if(t[p].tag) push_down(p, l, r);
    int res1 = 0, res2 = 0;
    if(ql <= mid) res1 = query(ls, l, mid, ql, qr);
    if(qr > mid) res2 = query(rs, mid + 1, r, ql, qr);
    // cout << p << " " << l << " " << r << " " << res1 << " " << res2 << endl;
    if(qr > mid) return (1ll * res1 * power[min(r, qr) - mid] % mod + res2) % mod;
    else return res1;
}

void solve() {
    int primes[] = { 100511, 100517, 100591, 100523 };
    srand((unsigned int) time(NULL));
    base = primes[rand() % 4];
    int mods[] = { 1000000007, 1000000009, 1000000033, 1000000123 };
    mod = mods[rand() % 4];
    cin >> n >> q;
    rep(i, 1, n) {
        cin >> a[i];
        assert(a[i] >= 0 && a[i] <= 65535);
    }
    power[0] = 1;
    rep(i, 1, n) power[i] = 1ll * power[i - 1] * base % mod;
    sum[0] = 1;
    rep(i, 1, n) sum[i] = (sum[i - 1] + power[i]) % mod;
    build(1, 1, n);
    while(q --) {
        int op, x, y, k;
        cin >> op >> x >> y;
        assert(op == 1 || op == 2);
        assert(x <= y && x >= 1 && y <= n);
        if(op == 1) modify(1, 1, n, x, y);
        else {
            cin >> k;
            assert(max(x, y) + k - 1 <= n);
            // cout << query(1, 1, n, x, x + k - 1) << endl;
            // cout << query(1, 1, n, y, y + k - 1) << "!" << endl;
            cout << (query(1, 1, n, x, x + k - 1) == query(1, 1, n, y, y + k - 1) ? "yes\n" : "no\n");
        }
    }
}

int main() {
    // freopen("G.in", "r", stdin);
    // freopen("G.out", "w", stdout);
    ios :: sync_with_stdio(false);
    cin.tie(0);
    int T = 1;
    // cin >> T;
    while(T --) solve();
    return 0;
}