QOJ.ac
QOJ
ID | 提交记录ID | 题目 | Hacker | Owner | 结果 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|
#1298 | #825726 | #9774. Same Sum | ship2077 | ucup-team191 | Success! | 2024-12-23 09:19:37 | 2024-12-23 09:19:38 |
詳細信息
Extra Test:
Wrong Answer
time: 6ms
memory: 18932kb
input:
560 1 613 7631 7337 184419 24398 12501 22302 140799 7487 4927 17287 170299 24884 17586 9143 148387 9598 15815 13841 160746 1359 4799 7190 186652 22442 15419 12541 149598 7471 4031 1693 186805 15806 504 9541 174149 23279 2726 14421 159574 13316 7716 20610 158358 22675 9840 5055 162430 19618 16760 186...
output:
YES
result:
wrong answer expected NO, found YES [1st token]
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#825726 | #9774. Same Sum | ucup-team191# | WA | 462ms | 22624kb | C++23 | 3.9kb | 2024-12-21 21:56:46 | 2024-12-23 09:24:17 |
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 500;
const int OFF = (1 << 18);
const int MOD = 998244353;
const int MOD2 = 1e9 + 7;
const int BS = 3;
inline int add(int A, int B) {
if(A + B >= MOD) return A + B - MOD;
return A + B;
}
inline int sub(int A, int B) {
if(A - B < 0) return A - B + MOD;
return A - B;
}
inline int mul(int A, int B) {
return A * 1ll * B % MOD;
}
inline int add2(int A, int B) {
if(A + B >= MOD2) return A + B - MOD2;
return A + B;
}
inline int sub2(int A, int B) {
if(A - B < 0) return A - B + MOD2;
return A - B;
}
inline int mul2(int A, int B) {
return A * 1ll * B % MOD2;
}
const int STEP = 50000;
int pott1[N], pott2[N];
int pott12[N], pott22[N];
inline int fast_pot(ll B) {
if(B < 0) B = (B % (MOD - 1)) + (MOD - 1);
B %= (MOD - 1);
return mul(pott1[B % STEP], pott2[B / STEP]);
}
inline int fast_pot2(ll B) {
if(B < 0) B = (B % (MOD2 - 1)) + (MOD2 - 1);
B %= (MOD2 - 1);
return mul2(pott12[B % STEP], pott22[B / STEP]);
}
int T[2 * OFF], rT[2 * OFF];
int T2[2 * OFF], rT2[2 * OFF];
ll Tsum[2 * OFF], prop[2 * OFF];
void refresh(int x, int len) {
if(!prop[x]) return;
Tsum[x] += (ll)prop[x] * len;
T[x] = mul(T[x], fast_pot(prop[x]));
rT[x] = mul(rT[x], fast_pot(-prop[x]));
T2[x] = mul2(T2[x], fast_pot2(prop[x]));
rT2[x] = mul2(rT2[x], fast_pot2(-prop[x]));
if(x < OFF) {
prop[2 * x] += prop[x];
prop[2 * x + 1] += prop[x];
}
prop[x] = 0;
}
void update(int i, int a, int b, int lo, int hi, int kol) {
if(lo <= a && b <= hi) {
prop[i] += kol; refresh(i, b - a + 1);
return;
}
refresh(i, b - a + 1);
if(a > hi || b < lo) return;
update(2 * i, a, (a + b) / 2, lo, hi, kol);
update(2 * i + 1, (a + b) / 2 + 1, b, lo, hi, kol);
T[i] = add(T[2 * i], T[2 * i + 1]);
rT[i] = add(rT[2 * i], rT[2 * i + 1]);
T2[i] = add2(T2[2 * i], T2[2 * i + 1]);
rT2[i] = add2(rT2[2 * i], rT2[2 * i + 1]);
Tsum[i] = Tsum[2 * i] + Tsum[2 * i + 1];
}
int ob_hsh, rev_hsh, ob_hsh2, rev_hsh2;
ll sum_q;
void query(int i, int a, int b, int lo, int hi) {
refresh(i, b - a + 1);
if(lo <= a && b <= hi) {
sum_q += Tsum[i];
ob_hsh = add(ob_hsh, T[i]);
rev_hsh = add(rev_hsh, rT[i]);
ob_hsh2 = add2(ob_hsh2, T2[i]);
rev_hsh2 = add2(rev_hsh2, rT2[i]);
return;
}
if(a > hi || b < lo) return;
query(2 * i, a, (a + b) / 2, lo, hi);
query(2 * i + 1, (a + b) / 2 + 1, b, lo, hi);
}
void precompute() {
pott1[0] = pott2[0] = 1;
for(int i = 1;i < STEP;i++)
pott1[i] = mul(pott1[i - 1], BS);
int korak = mul(pott1[STEP - 1], BS);
for(int i = 1;i < STEP;i++)
pott2[i] = mul(pott2[i - 1], korak);
pott12[0] = pott22[0] = 1;
for(int i = 1;i < STEP;i++)
pott12[i] = mul2(pott12[i - 1], BS);
int korak2 = mul2(pott12[STEP - 1], BS);
for(int i = 1;i < STEP;i++)
pott22[i] = mul2(pott22[i - 1], korak2);
}
int main() {
precompute();
int n, q; scanf("%d%d", &n, &q);
for(int i = 0;i < n;i++) {
int a; scanf("%d", &a);
Tsum[OFF + i] = a;
T[OFF + i] = fast_pot(a);
rT[OFF + i] = fast_pot(-a);
T2[OFF + i] = fast_pot2(a);
rT2[OFF + i] = fast_pot2(-a);
}
for(int i = OFF - 1; i ;i--) {
T[i] = add(T[2 * i], T[2 * i + 1]);
rT[i] = add(rT[2 * i], rT[2 * i + 1]);
Tsum[i] = Tsum[2 * i] + Tsum[2 * i + 1];
T2[i] = add2(T2[2 * i], T2[2 * i + 1]);
rT2[i] = add2(rT2[2 * i], rT2[2 * i + 1]);
}
for(;q--;) {
int ty, l, r, v;
scanf("%d%d%d", &ty, &l, &r);l--, r--;
if(ty == 1) {
scanf("%d", &v);
update(1, 0, OFF - 1, l, r, v);
} else {
sum_q = 0; ob_hsh = rev_hsh = 0;
ob_hsh2 = 0; rev_hsh2 = 0;
query(1, 0, OFF - 1, l, r);
ll val = sum_q / ((r - l + 1) / 2);
printf(((sum_q % ((r - l + 1) / 2) == 0 ) && (ob_hsh == mul(rev_hsh, fast_pot(val))) &&
(ob_hsh2 == mul2(rev_hsh2, fast_pot2(val)))) ? "YES\n" : "NO\n");
}
}
return 0;
}