QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#865238 | #9774. Same Sum | xieliren | WA | 1821ms | 47504kb | C++14 | 2.9kb | 2025-01-21 16:14:39 | 2025-01-21 16:14:43 |
Judging History
answer
#include<bits/stdc++.h>
#define left rt * 2
#define right rt * 2 + 1
#define int long long
using namespace std;
int read(){
int s = 0, f = 1;char ch = getchar();
while(!isdigit(ch)){if(ch == '-')f = -1;ch = getchar();}
while(isdigit(ch)){s = s * 10 + ch - '0';ch = getchar();}
return s * f;
}
void write(int x){
if(x < 0){putchar('-'); x = -x;}
if(x > 9) write(x / 10);
putchar(x % 10 + '0');
}
const int MAXN = 2e5 + 5, MR = 8e5 + 5, MOD = 911451407, E = 1907, INF = 1e18;
int n, q, a[MAXN];
int fpow(int a, int b){
int res = 1;
while(b){if(b & 1ll)res = res * a % MOD;a = a * a % MOD;b >>= 1ll;}
return res;
}
struct node{
int a, b, c, d;
};
struct Segment_tree{
int lf[MR], rf[MR], num[MR], num2[MR], lazy[MR], maxx[MR], minn[MR];
void push_up(int rt){
num[rt] = (num[left] + num[right]) % MOD;
num2[rt] = (num2[left] + num2[right]) % MOD;
minn[rt] = min(minn[left], minn[right]);
maxx[rt] = max(maxx[left], maxx[right]);
}
void build(int rt, int l, int r){
lf[rt] = l, rf[rt] = r;
if(l == r){
minn[rt] = maxx[rt] = a[l];
num[rt] = fpow(E, a[l]);
num2[rt] = fpow(fpow(E, a[l]), MOD - 2);
return ;
}
int mid = l + r >> 1ll;
build(left, l, mid);
build(right, mid + 1, r);
push_up(rt);
}
void push_down(int rt){
if(!lazy[rt])return ;
int k = lazy[rt];lazy[rt] = 0;
minn[left] += k, minn[right] += k;
maxx[left] += k, maxx[right] += k;
num[left] = num[left] * fpow(E, k) % MOD;
num[right] = num[right] * fpow(E, k) % MOD;
num2[left] = num2[left] * fpow(fpow(E, k), MOD - 2) % MOD;
num2[right] = num2[right] * fpow(fpow(E, k), MOD - 2) % MOD;
lazy[left] += k, lazy[right] += k;
}
void add_list(int rt, int l, int r, int x){
if(lf[rt] > r || rf[rt] < l)return ;
if(l <= lf[rt] && rf[rt] <= r){
num[rt] = num[rt] * fpow(E, x) % MOD;
num2[rt] = num2[rt] * fpow(fpow(E, x), MOD - 2);
minn[rt] += x, maxx[rt] += x;
lazy[rt] += x;
return ;
}
push_down(rt);
add_list(left, l, r, x);
add_list(right, l, r, x);
push_up(rt);
}
node query(int rt, int l, int r){
if(lf[rt] > r || rf[rt] < l)return {0, 0, INF, -INF};
if(l <= lf[rt] && rf[rt] <= r)
return {num[rt], num2[rt], minn[rt], maxx[rt]};
push_down(rt);
node lp = query(left, l, r), rp = query(right, l, r);
node res = {0, 0, INF, -INF};
res.a = (lp.a + rp.a) % MOD, res.b = (lp.b + rp.b) % MOD;
res.c = min(lp.c, rp.c), res.d = max(lp.d, rp.d);
return res;
}
}tr;
signed main(){
n = read(), q = read();
for(int i = 1;i <= n;i ++)a[i] = read();
tr.build(1, 1, n);
while(q --){
int opt = read(), l = read(), r = read();
if(opt == 1){
int x = read();
tr.add_list(1, l, r, x);
}
else{
node tmp = tr.query(1, l, r);
int h = fpow(E, tmp.c + tmp.d) * tmp.b % MOD;
if(h == tmp.a)puts("YES");
else puts("NO");
}
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 15944kb
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: 1821ms
memory: 47504kb
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:
NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO ...
result:
wrong answer expected YES, found NO [9382nd token]