QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#769843 | #9774. Same Sum | PlentyOfPenalty# | WA | 742ms | 63968kb | C++20 | 4.5kb | 2024-11-21 19:35:05 | 2024-11-21 19:35:06 |
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:35:05]
- 提交
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;
#define int long long
const int N = 2e5 + 9;
const int b1 = 131, b2 = 131131;
// const int p1 = 998244353, p2 = 1e9 + 7;
const ll p1 = 1000000000000000003ll;
const ll p2 = 1000000000000030219ll;
int n, m, a[N];
template <const int mod> int power(int a, int b) {
int s = 1;
for (; b; b >>= 1, a = (lll)a * a % mod)
if (b & 1) s = (lll)s * a % mod;
return s;
}
struct atom {
int x, y;
static atom get_base(ll 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)((lll)x * rhs.x % p1), //
(int)((lll)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;
ll tag;
ll min, max;
atom pos, neg, pos_tag, neg_tag;
} p[N << 2];
void pushup(int u, ll tag, const atom &pos_tag, const atom &neg_tag) {
p[u].min += tag;
p[u].max += tag;
p[u].tag += tag;
p[u].pos = p[u].pos * pos_tag;
p[u].neg = p[u].neg * neg_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=%lld >> min=%lld max=%lld pos=%lld,%lld neg=%lld,%lld\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, ll 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<ll, ll, 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) //
);
}
}
signed 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=%lld l=%lld r=%lld\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=%lld max=%lld pos=%lld,%lld neg=%lld,%lld\n", min, max, pos.x, pos.y, neg.x, neg.y);
ll s = min + max;
if (pos == neg * atom::get_base(s)) {
cout << "YES" << endl;
} else {
cout << "NO" << endl;
}
}
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5512kb
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
Wrong Answer
time: 742ms
memory: 63968kb
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 ...
output:
YES NO YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES NO YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YE...
result:
wrong answer expected NO, found YES [1st token]