QOJ.ac
QOJ
ID | Submission ID | Problem | Hacker | Owner | Result | Submit time | Judge time |
---|---|---|---|---|---|---|---|
#1296 | #824535 | #9774. Same Sum | ship2077 | ucup-team4474 | Success! | 2024-12-22 18:51:58 | 2024-12-22 18:51:59 |
Details
Extra Test:
Wrong Answer
time: 42ms
memory: 22688kb
input:
200000 1 1989 4673 5022 68316 9289 5943 5568 59200 9038 4151 6342 60469 6573 8957 5225 59245 3468 5640 3177 67715 155 35 2418 77392 1419 5988 7830 64763 7888 5652 5497 60963 3737 3996 2460 69807 4814 9670 7016 58500 1523 4091 6597 67789 5239 8965 3674 62122 7283 5884 9109 57724 6178 3743 1650 68429 ...
output:
YES
result:
wrong answer expected NO, found YES [1st token]
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#824535 | #9774. Same Sum | ucup-team4474# | WA | 1383ms | 23536kb | C++20 | 5.7kb | 2024-12-21 14:34:39 | 2024-12-22 18:57:25 |
answer
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
using i128 = __int128_t;
bool Memory_begin;
template <int mod>
unsigned int down(unsigned int x)
{
return x >= mod ? x - mod : x;
}
template <int mod>
struct Modint
{
unsigned int x;
Modint() = default;
Modint(unsigned int x) : x(x) {}
friend istream &operator>>(istream &in, Modint &a) { return in >> a.x; }
friend ostream &operator<<(ostream &out, Modint a) { return out << a.x; }
friend Modint operator+(Modint a, Modint b) { return down<mod>(a.x + b.x); }
friend Modint operator-(Modint a, Modint b) { return down<mod>(a.x - b.x + mod); }
friend Modint operator*(Modint a, Modint b) { return 1ULL * a.x * b.x % mod; }
friend Modint operator/(Modint a, Modint b) { return a * ~b; }
friend Modint operator^(Modint a, i64 b)
{
Modint ans = 1;
for (; b; b >>= 1, a *= a)
if (b & 1)
ans *= a;
return ans;
}
friend Modint operator~(Modint a) { return a ^ (mod - 2); }
friend Modint operator-(Modint a) { return down<mod>(mod - a.x); }
friend Modint &operator+=(Modint &a, Modint b) { return a = a + b; }
friend Modint &operator-=(Modint &a, Modint b) { return a = a - b; }
friend Modint &operator*=(Modint &a, Modint b) { return a = a * b; }
friend Modint &operator/=(Modint &a, Modint b) { return a = a / b; }
friend Modint &operator^=(Modint &a, i64 b) { return a = a ^ b; }
friend Modint &operator++(Modint &a) { return a += 1; }
friend Modint operator++(Modint &a, int)
{
Modint x = a;
a += 1;
return x;
}
friend Modint &operator--(Modint &a) { return a -= 1; }
friend Modint operator--(Modint &a, int)
{
Modint x = a;
a -= 1;
return x;
}
friend bool operator==(Modint a, Modint b) { return a.x == b.x; }
friend bool operator!=(Modint a, Modint b) { return !(a == b); }
};
const int mod = 998244353;
typedef Modint<mod> mint;
const mint base = 91, e = 1;
const int N = 2e5 + 5;
int n, q, a[N];
struct node
{
mint tag;
mint sum1, sum2;
i64 tag0, sum0;
} st[N << 2];
void build(int cur, int l, int r)
{
st[cur].tag = e;
if (l == r)
{
st[cur].sum0 = a[l];
st[cur].sum1 = base ^ a[l];
st[cur].sum2 = e / st[cur].sum1;
return;
}
int mid = l + r >> 1;
build(cur << 1, l, mid);
build(cur << 1 | 1, mid + 1, r);
st[cur].sum1 = st[cur << 1].sum1 + st[cur << 1 | 1].sum1;
st[cur].sum2 = st[cur << 1].sum2 + st[cur << 1 | 1].sum2;
st[cur].sum0 = st[cur << 1].sum0 + st[cur << 1 | 1].sum0;
}
void pushdown(int cur, int l, int mid, int r)
{
if (st[cur].tag == e)
return;
st[cur << 1].tag *= st[cur].tag;
st[cur << 1].sum1 *= st[cur].tag;
st[cur << 1].sum2 /= st[cur].tag;
st[cur << 1].tag0 += st[cur].tag0;
st[cur << 1].sum0 += 1ll * (mid - l + 1) * st[cur].tag0;
st[cur << 1 | 1].tag *= st[cur].tag;
st[cur << 1 | 1].sum1 *= st[cur].tag;
st[cur << 1 | 1].sum2 /= st[cur].tag;
st[cur << 1 | 1].tag0 += st[cur].tag0;
st[cur << 1 | 1].sum0 += 1ll * (r - mid) * st[cur].tag0;
st[cur].tag = e, st[cur].tag0 = 0;
}
void update(int cur, int l, int r, int a, int b, int x)
{
if (a <= l and r <= b)
{
st[cur].tag0 += x;
st[cur].sum0 += 1ll * x * (r - l + 1);
mint tmp = base ^ x;
st[cur].tag *= tmp;
st[cur].sum1 *= tmp;
st[cur].sum2 /= tmp;
return;
}
int mid = l + r >> 1;
pushdown(cur, l, mid, r);
if (a <= mid)
update(cur << 1, l, mid, a, b, x);
if (b > mid)
update(cur << 1 | 1, mid + 1, r, a, b, x);
st[cur].sum1 = st[cur << 1].sum1 + st[cur << 1 | 1].sum1;
st[cur].sum2 = st[cur << 1].sum2 + st[cur << 1 | 1].sum2;
st[cur].sum0 = st[cur << 1].sum0 + st[cur << 1 | 1].sum0;
}
pair<mint, mint> query(int cur, int l, int r, int a, int b)
{
if (a <= l and r <= b)
return {st[cur].sum1, st[cur].sum2};
if (a > r or b < l)
return {mint(0), mint(0)};
int mid = l + r >> 1;
pushdown(cur, l, mid, r);
auto lft = query(cur << 1, l, mid, a, b);
auto rht = query(cur << 1 | 1, mid + 1, r, a, b);
return {lft.first + rht.first, lft.second + rht.second};
}
i64 query1(int cur, int l, int r, int a, int b)
{
if (a <= l and r <= b)
return st[cur].sum0;
if (a > r or b < l)
return 0;
int mid = l + r >> 1;
pushdown(cur, l, mid, r);
return query1(cur << 1, l, mid, a, b) + query1(cur << 1 | 1, mid + 1, r, a, b);
}
bool Memory_end;
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cerr << (&Memory_end - &Memory_begin) / 1048576.0 << "MB" << '\n';
cin >> n >> q;
for (int i = 1; i <= n; i++)
cin >> a[i];
build(1, 1, n);
while (q--)
{
int opt;
cin >> opt;
if (opt == 1)
{
int l, r, x;
cin >> l >> r >> x;
update(1, 1, n, l, r, x);
}
else
{
int l, r;
cin >> l >> r;
i64 s = query1(1, 1, n, l, r) * 2;
bool ans = false;
if (s % (r - l + 1) == 0)
{
s /= r - l + 1;
auto tmp = query(1, 1, n, l, r);
tmp.second *= base ^ s;
if (tmp.first == tmp.second)
ans = true;
}
if (ans)
cout << "YES\n";
else
cout << "NO\n";
}
}
}
/*
*/