QOJ.ac
QOJ
ID | 提交记录ID | 题目 | Hacker | Owner | 结果 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|
#1306 | #827169 | #9774. Same Sum | ship2077 | propane | Success! | 2024-12-23 16:12:50 | 2024-12-23 16:12:50 |
詳細信息
Extra Test:
Wrong Answer
time: 89ms
memory: 11396kb
input:
32 1 2483 4385 5260 5900 5921 7135 7167 8210 8340 9172 9453 11679 12533 14210 14276 14514 15829 15910 16487 19174 20201 20921 22042 22682 148078 158693 162220 164358 165810 167129 168745 171083 2 1 32
output:
YES
result:
wrong answer expected NO, found YES [1st token]
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#827169 | #9774. Same Sum | propane | WA | 467ms | 47120kb | C++20 | 6.4kb | 2024-12-22 20:05:35 | 2024-12-23 16:19:35 |
answer
#include<iostream>
#include<cstring>
#include<vector>
#include<array>
#include<stdint.h>
using namespace std;
using LL = long long;
template<const int T>
struct ModInt {
const static int mod = T;
int x;
ModInt(int x = 0) : x(x % mod) {}
ModInt(long long x) : x(int(x % mod)) {}
int val() { return x; }
ModInt operator + (const ModInt &a) const { int x0 = x + a.x; return ModInt(x0 < mod ? x0 : x0 - mod); }
ModInt operator - (const ModInt &a) const { int x0 = x - a.x; return ModInt(x0 < 0 ? x0 + mod : x0); }
ModInt operator * (const ModInt &a) const { return ModInt(1LL * x * a.x % mod); }
ModInt operator / (const ModInt &a) const { return *this * a.inv(); }
bool operator == (const ModInt &a) const { return x == a.x; };
bool operator != (const ModInt &a) const { return x != a.x; };
void operator += (const ModInt &a) { x += a.x; if (x >= mod) x -= mod; }
void operator -= (const ModInt &a) { x -= a.x; if (x < 0) x += mod; }
void operator *= (const ModInt &a) { x = 1LL * x * a.x % mod; }
void operator /= (const ModInt &a) { *this = *this / a; }
friend ModInt operator + (int y, const ModInt &a){ int x0 = y + a.x; return ModInt(x0 < mod ? x0 : x0 - mod); }
friend ModInt operator - (int y, const ModInt &a){ int x0 = y - a.x; return ModInt(x0 < 0 ? x0 + mod : x0); }
friend ModInt operator * (int y, const ModInt &a){ return ModInt(1LL * y * a.x % mod);}
friend ModInt operator / (int y, const ModInt &a){ return ModInt(y) / a;}
friend ostream &operator<<(ostream &os, const ModInt &a) { return os << a.x;}
friend istream &operator>>(istream &is, ModInt &t){return is >> t.x;}
ModInt pow(int64_t n) const {
ModInt res(1), mul(x);
while(n){
if (n & 1) res *= mul;
mul *= mul;
n >>= 1;
}
return res;
}
ModInt inv() const {
int a = x, b = mod, u = 1, v = 0;
while (b) {
int t = a / b;
a -= t * b; swap(a, b);
u -= t * v; swap(u, v);
}
if (u < 0) u += mod;
return u;
}
};
using mint = ModInt<1000000009>;
const int maxn = 1e6 + 5;
const mint base = 12314121;
mint pows[maxn], inv[maxn];
#include<iostream>
#include<cstring>
#include<vector>
#include<numeric>
#include<functional>
using namespace std;
struct Info{
LL sum = 0; int len = 0;
mint hsh1 = 0, hsh2 = 0;
};
struct Tag{
LL add = 0;
mint hsh1 = 1, hsh2 = 1;
};
Info operator+(const Info &a, const Info &b){
return {a.sum + b.sum, a.len + b.len, a.hsh1 + b.hsh1, a.hsh2 + b.hsh2};
}
void apply(Info &x, Tag &a, Tag f){
x.sum += f.add * x.len;
a.add += f.add;
x.hsh1 *= f.hsh1;
x.hsh2 *= f.hsh2;
a.hsh1 *= f.hsh1;
a.hsh2 *= f.hsh2;
}
template<class Info, class Tag>
struct LazySegmentTree{
int n;
vector<Info> info;
vector<Tag> tag;
LazySegmentTree() {}
LazySegmentTree(int n, Info _init = Info()){
init(vector<Info>(n, _init));
}
LazySegmentTree(const vector<Info> &_init){
init(_init);
}
void init(const vector<Info> &_init){
n = (int)_init.size();
info.assign((n << 2) + 1, Info());
tag.assign((n << 2) + 1, Tag());
function<void(int, int, int)> build = [&](int p, int l, int r){
if (l == r){
info[p] = _init[l - 1];
return;
}
int m = (l + r) / 2;
build(2 * p, l, m);
build(2 * p + 1, m + 1, r);
pull(p);
};
build(1, 1, n);
}
void pull(int p){
info[p] = info[2 * p] + info[2 * p + 1];
}
void apply(int p, const Tag &v){
::apply(info[p], tag[p], v);
}
void push(int p){
apply(2 * p, tag[p]);
apply(2 * p + 1, tag[p]);
tag[p] = Tag();
}
void modify(int p, int l, int r, int x, const Info &v){
if (l == r){
info[p] = v;
return;
}
int m = (l + r) / 2;
push(p);
if (x <= m){
modify(2 * p, l, m, x, v);
}
else{
modify(2 * p + 1, m + 1, r, x, v);
}
pull(p);
}
void modify(int p, const Info &v){
modify(1, 1, n, p, v);
}
Info query(int p, int l, int r, int x, int y){
if (l > y || r < x){
return Info();
}
if (l >= x && r <= y){
return info[p];
}
int m = (l + r) / 2;
push(p);
return query(2 * p, l, m, x, y) + query(2 * p + 1, m + 1, r, x, y);
}
Info query(int l, int r){
return query(1, 1, n, l, r);
}
void modify(int p, int l, int r, int x, int y, const Tag &v){
if (l > y || r < x){
return;
}
if (l >= x && r <= y){
apply(p, v);
return;
}
int m = (l + r) / 2;
push(p);
modify(2 * p, l, m, x, y, v);
modify(2 * p + 1, m + 1, r, x, y, v);
pull(p);
}
void modify(int l, int r, const Tag &v){
return modify(1, 1, n, l, r, v);
}
};
int main(){
#ifdef LOCAL
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
pows[0] = 1;
for(int i = 1; i < maxn; i++){
pows[i] = pows[i - 1] * base;
}
for(int i = 0; i < maxn; i++){
inv[i] = pows[i].inv();
}
int n, q;
cin >> n >> q;
vector<Info> init(n);
for(int i = 0; i < n; i++){
int x;
cin >> x;
init[i] = {x, 1, pows[x], inv[x]};
}
LazySegmentTree<Info, Tag> seg(init);
while(q--){
int op;
cin >> op;
if (op == 1){
int l, r, v;
cin >> l >> r >> v;
seg.modify(l, r, {v, pows[v], inv[v]});
}
else{
int l, r;
cin >> l >> r;
auto [sum, len, a, b] = seg.query(l, r);
if (sum % (len / 2)){
cout << "NO" << '\n';
continue;
}
LL ave = sum / (len / 2);
b *= mint(base).pow(ave);
cout << (a == b ? "YES" : "NO") << '\n';
}
}
}