QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#769756 | #9774. Same Sum | PlentyOfPenalty# | RE | 0ms | 3604kb | C++20 | 4.3kb | 2024-11-21 19:17:16 | 2024-11-21 19:17:20 |
Judging History
你现在查看的是最新测评结果
- [2025-01-11 11:59:18]
- hack成功,自动添加数据
- (/hack/1443)
- [2024-12-23 17:02:06]
- hack成功,自动添加数据
- (/hack/1310)
- [2024-12-23 16:48:26]
- hack成功,自动添加数据
- (/hack/1309)
- [2024-12-23 16:33:45]
- hack成功,自动添加数据
- (/hack/1308)
- [2024-12-23 16:23:53]
- hack成功,自动添加数据
- (/hack/1307)
- [2024-12-23 16:13:08]
- hack成功,自动添加数据
- (/hack/1306)
- [2024-12-23 15:54:42]
- hack成功,自动添加数据
- (/hack/1305)
- [2024-12-23 14:58:39]
- hack成功,自动添加数据
- (/hack/1304)
- [2024-12-23 09:58:11]
- hack成功,自动添加数据
- (/hack/1302)
- [2024-12-23 09:47:22]
- hack成功,自动添加数据
- (/hack/1301)
- [2024-12-23 09:41:23]
- hack成功,自动添加数据
- (/hack/1300)
- [2024-12-23 09:26:32]
- hack成功,自动添加数据
- (/hack/1299)
- [2024-12-23 09:19:58]
- hack成功,自动添加数据
- (/hack/1298)
- [2024-12-23 09:13:29]
- hack成功,自动添加数据
- (/hack/1297)
- [2024-12-22 18:52:18]
- hack成功,自动添加数据
- (/hack/1296)
- [2024-12-22 18:13:14]
- hack成功,自动添加数据
- (/hack/1294)
- [2024-11-21 19:17:16]
- 提交
answer
#include <bits/stdc++.h>
#define sz(x) ((int)(x).size())
#define all(x) begin(x), end(x)
#ifdef memset0
#define log(...) fprintf(stderr, __VA_ARGS__)
#else
#define endl '\n'
#define log(...) (void(0))
#endif
using namespace std;
using ll = long long;
using lf = long double;
using ull = unsigned long long;
using lll = __int128;
const int N = 2e5 + 9;
const int b1 = 131, b2 = 131131;
const int p1 = 998244353, p2 = 1e9 + 7;
int n, m, a[N];
template <const int mod> int power(int a, int b) {
int s = 1;
for (; b; b >>= 1, a = (ll)a * a % mod)
if (b & 1) s = (ll)s * a % mod;
return s;
}
struct atom {
int x, y;
static atom get_base(int k) {
int k1 = k % (p1 - 1);
if (k1 < 0) k1 += p1 - 1;
int k2 = k % (p2 - 1);
if (k2 < 0) k2 += p2 - 1;
return {power<p1>(b1, k1), power<p2>(b2, k2)};
}
atom operator+(atom rhs) const {
rhs.x += x;
if (rhs.x >= p1) rhs.x -= p1;
rhs.y += y;
if (rhs.y >= p2) rhs.y -= p2;
return rhs;
}
atom operator*(const atom &rhs) const {
return {
(int)((ll)x * rhs.x % p1), //
(int)((ll)y * rhs.y % p2),
};
}
bool operator==(const atom &rhs) const { return x == rhs.x && y == rhs.y; }
};
const atom one = {1, 1};
struct segment {
int l, r, mid;
int tag;
int min, max;
atom pos, neg, pos_tag, neg_tag;
} p[N];
void pushup(int u, int tag, const atom &pos_tag, const atom &neg_tag) {
p[u].tag += tag;
p[u].pos_tag = p[u].pos_tag * pos_tag;
p[u].neg_tag = p[u].neg_tag * neg_tag;
}
void pushdown(int u) {
if (p[u].tag) {
pushup(u << 1, p[u].tag, p[u].pos_tag, p[u].neg_tag);
pushup(u << 1 | 1, p[u].tag, p[u].pos_tag, p[u].neg_tag);
p[u].tag = 0;
p[u].pos_tag = one;
p[u].neg_tag = one;
}
}
void maintain(int u) {
p[u].min = min(p[u << 1].min, p[u << 1 | 1].min);
p[u].max = max(p[u << 1].max, p[u << 1 | 1].max);
p[u].pos = p[u << 1].pos + p[u << 1 | 1].pos;
p[u].neg = p[u << 1].neg + p[u << 1 | 1].neg;
}
void build(int u, int l, int r) {
p[u].l = l, p[u].r = r, p[u].mid = (l + r) >> 1;
if (l == r) {
p[u].min = p[u].max = a[l];
p[u].pos = atom::get_base(a[l]);
p[u].neg = atom::get_base(-a[l]);
return;
}
build(u << 1, l, p[u].mid);
build(u << 1 | 1, p[u].mid + 1, r);
maintain(u);
log("u=%d >> min=%d max=%d pos=%d,%d neg=%d,%d\n", u, p[u].min, p[u].max, p[u].pos.x, p[u].pos.y, p[u].neg.x, p[u].neg.y);
}
void modify(int u, int l, int r, int tag, const atom &pos_tag, const atom &neg_tag) {
if (p[u].l == l && p[u].r == r) {
pushup(u, tag, pos_tag, neg_tag);
return;
}
pushdown(u);
if (r <= p[u].mid) {
modify(u << 1, l, r, tag, pos_tag, neg_tag);
} else if (l > p[u].mid) {
modify(u << 1 | 1, l, r, tag, pos_tag, neg_tag);
} else {
modify(u << 1, l, p[u].mid, tag, pos_tag, neg_tag);
modify(u << 1 | 1, p[u].mid + 1, r, tag, pos_tag, neg_tag);
}
maintain(u);
}
tuple<int, int, atom, atom> query(int u, int l, int r) {
if (p[u].l == l && p[u].r == r) {
return make_tuple(p[u].min, p[u].max, p[u].pos, p[u].neg);
}
pushdown(u);
if (r <= p[u].mid) {
return query(u << 1, l, r);
} else if (l > p[u].mid) {
return query(u << 1 | 1, l, r);
} else {
auto s1 = query(u << 1, l, p[u].mid);
auto s2 = query(u << 1 | 1, p[u].mid + 1, r);
return make_tuple( //
min(get<0>(s1), get<0>(s2)), //
max(get<1>(s1), get<1>(s2)), //
get<2>(s1) * get<2>(s2), //
get<3>(s1) * get<3>(s2) //
);
}
}
int main() {
#ifdef memset0
freopen("G.in", "r", stdin);
#endif
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
build(1, 1, n);
for (int o, l, r, v, i = 1; i <= m; i++) {
cin >> o >> l >> r;
log("> o=%d l=%d r=%d\n", o, l, r);
if (o == 1) {
cin >> v;
modify(1, l, r, v, atom::get_base(v), atom::get_base(-v));
} else {
auto [min, max, pos, neg] = query(1, l, r);
// log("! min=%d max=%d pos=%d,%d neg=%d,%d\n", min, max, pos.x, pos.y, neg.x, neg.y);
int s = min + max;
if (pos == neg * atom::get_base(s)) {
cout << "YES" << endl;
} else {
cout << "NO" << endl;
}
}
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3604kb
input:
8 4 1 2 3 4 5 6 7 8 2 1 8 1 1 4 4 2 1 6 2 1 8
output:
YES NO YES
result:
ok 3 token(s): yes count is 2, no count is 1
Test #2:
score: -100
Runtime Error
input:
200000 200000 0 0 0 1 1 0 2 1 1 2 0 1 0 0 0 2 1 0 1 2 2 1 2 1 2 0 0 2 1 2 1 0 0 2 0 2 1 1 1 2 0 0 0 0 2 0 1 0 0 2 2 1 1 0 0 2 1 0 2 0 2 1 2 1 0 1 2 1 0 1 2 1 2 1 0 1 2 0 1 0 1 1 0 2 1 2 0 2 2 1 1 2 1 2 2 0 0 1 2 0 0 2 2 0 1 2 2 0 0 1 2 1 2 0 2 0 0 2 0 2 1 0 1 1 1 1 2 1 2 0 1 2 1 0 2 1 0 1 1 2 2 0 1 ...