QOJ.ac

QOJ

ID	提交记录ID	题目	Hacker	Owner	结果	提交时间	测评时间
#1022	#642842	#9302. Caesar Cipher	ship2077	Ashbourne	Success!	2024-10-21 09:47:30	2024-10-21 09:47:30

详细

Extra Test:

Wrong Answer

time: 0ms

memory: 7632kb

input:

101 1
0 0 0 0 0 6 16 32 33 33 51 51 51 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 85 108 108 119 119 119 119 119 139 145 157 165 65371 0 8 20 26 46 46 46 46 46 57 57 80 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 114 114 114 132 132 133 ...

output:

yes

result:

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

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#642842	#9302. Caesar Cipher	Ashbourne	WA	908ms	33676kb	C++20	4.3kb	2024-10-15 16:33:47	2024-10-21 09:48:00

answer

#include<bits/stdc++.h>
#define int long long
#define rep(i, j, k) for(int i = j; i <= k; ++ i)
#define drp(i, j, k) for(int i = j; i >= k; -- i)
#define pii pair<int, int>
using namespace std;
const int N = 5e5 + 10;
const int Mod = 65536, M1 = 998244353, M2 = 1e9 + 7;
// #define ls(x) (x << 1)
// #define rs(x) (x << 1 | 1)
// struct SGT {
    // pii tr[N << 2];
    // void upd (int x) {
        // tr[x] = tr[ls(x)] + tr[rs(x)];
    // }
    // void build(int x, int l, int r, vector<int> &in) {
        // if (l == r) return tr[x] = in[l - 1], void();
        // int mid = (l + r) >> 1;
        // build (ls(x), l, mid, in);
        // build (rs(x), mid + 1, r, in);
        // upd (x);
    // }
    // void modify(int x, int l, int r, int cur, int val){
        // if(l == r){
            // tr[x] = tr[x] + val;
            // return;
        // }
        // int mid = (l + r) >> 1;
        // if(cur <= mid) modify(ls(x), l, mid, cur, val);
        // else modify(rs(x), mid + 1, r, cur, val);
        // upd(x);
    // }
    // int query(int x, int l, int r, int L, int R) {
        // if (L <= l && r <= R) return tr[x];
        // int mid = (l + r) >> 1;
        // if (R <= mid) return query(ls(x), l, mid, L, R);
        // if (L > mid) return query(rs(x), mid + 1, r, L, R);
        // return query(ls(x), l, mid, L, R) + query(rs(x), mid + 1, r, L, R);
    // }
// } Tr;
int fpow(int a, int b, int M){
	int x = 1;
	while(b){
		if(b & 1)x = x * a % M;
		a = a * a % M;
		b >>= 1;
	}
	return x;
}
struct BST{
	int tot, Mod;
	void resize(int n, int m){
		tot = n;
		Mod = m;
	}
        int tr[N << 1];
        void init(){
            memset(tr, 0, sizeof tr);
        }
        void add(int x, int num){
        	if(x == 0) return;
                while(x <= tot){
                    tr[x] += num;
                    tr[x] %= Mod;
                    x += x & (-x);
                }
        }
        int query(int x){
                int ans = 0;
                while(x){
                    ans += tr[x];
                    ans %= Mod;
                    x -= x & (-x);
                }
                return ans;
        }
}bst, tr1, tr2;
void solve(){
	int n, q;
	cin >> n >> q;
	// cout << n << q << endl;
	bst.resize(n, Mod);
	vector<int> a(n + 1), b(n + 1), w1(n + 1), w2(n + 1);
	for(int i = 1; i <= n; ++ i){
		cin >> a[i];
	}
	bst.add(1, a[1]);
	rep(i, 1, n - 1) b[i] = (a[i + 1] - a[i] + Mod) % Mod, bst.add(i + 1, b[i]);
	int p1 = 70067, p2 = 70379;
	tr1.resize(n - 1, M1);
	tr2.resize(n - 1, M2);
	w1[1] = w2[1] = 1;
	for(int i = 1; i <= n - 1; ++ i){
		w1[i + 1] = w1[i] * p1 % M1;
		w2[i + 1] = w2[i] * p2 % M2;
		tr1.add(i, w1[i] * b[i] % M1);
		tr2.add(i, w2[i] * b[i] % M2);
	}
	while(q--){
		int cc; cin >> cc;
		if(cc == 2){
			int x, y, len;
			cin >> x >> y >> len;
			int a1 = bst.query(x), a2 = bst.query(y);
			if(a1 != a2){
				cout << "no" << endl;
				continue;
			} 
			int hs1 = tr1.query(x + len - 2) + M1 - tr1.query(x - 1);
			hs1 %= M1; hs1 = hs1 * fpow(w1[x], M1 - 2, M1) % M1;
			int hs2 = tr2.query(x + len - 2) + M2 - tr2.query(x - 1);
			hs2 %= M2; hs2 = hs2 * fpow(w2[x], M2 - 2, M2) % M2;
			int hs3 = tr1.query(y + len - 2) + M1 - tr1.query(y - 1);
			hs3 %= M1; hs3 = hs3 * fpow(w1[y], M1 - 2, M1) % M1;
			int hs4 = tr2.query(y + len - 2) + M2 - tr2.query(y - 1);
			hs4 %= M2; hs4 = hs4 * fpow(w2[y], M2 - 2, M2) % M2;
			// cout << hs1 << " " << hs3 << endl;
			// cout << fpow(w1[y], M1 - 2, M1) * w1[y] % M1 << endl;
			if(hs1 == hs3 && hs2 == hs4){
				cout << "yes" << endl;
			}else cout << "no" << endl;
		}else{
			int l, r;
			cin >> l >> r;
			bst.add(l, 1);  bst.add(r + 1, Mod - 1);
			if(l != 1){
				b[l - 1] ++;
				tr1.add(l - 1, w1[l - 1] % M1);
				tr2.add(l - 1, w2[l - 1] % M2);
				if(b[l - 1] >= Mod){
					b[l - 1] -= Mod;
					tr1.add(l - 1, (M1 - Mod) * w1[l - 1] % M1);
					tr2.add(l - 1, (M2 - Mod) * w2[l - 1] % M2);
				}
			}
			if(r != n){
				b[r] --;
				tr2.add(r, w2[r] * (M2 - 1) % M2);
				tr1.add(r, w1[r] * (M1 - 1) % M1);
				if(b[r] < 0){
					b[r] += Mod;
					tr2.add(r, w2[r] * (Mod) % M2);
					tr1.add(r, w1[r] * (Mod) % M1);
				}
			}
		}
	}
}
signed main(){
	ios::sync_with_stdio(0);
	int T = 1;
	// cin >> T;
	while(T--){
		solve();
	}
}

源文件, 语言: C++20