QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #602971 | #9242. An Easy Geometry Problem | xi_xi | WA | 11ms | 12444kb | C++14 | 4.2kb | 2024-10-01 13:51:13 | 2024-10-01 13:51:14 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define int long long
using namespace std;
const int maxn = 2e5 + 5;
const int base = 131313131;
const int mod = 998244353;
int n, q, k, b, a[maxn];
int pw[maxn], sum[maxn], ans[maxn];
struct node{
struct nd{
int l, r, laz;
int sum;
}tree[maxn << 2];
void pushup(int p){
tree[p].sum = (tree[p << 1].sum + tree[p << 1 | 1].sum) % mod;
}
void build(int p, int l, int r){
tree[p].l = l;tree[p].r = r;
if(l == r){
tree[p].sum = (a[l] * pw[l - 1]) % mod;
return;
}
int mid = l + r >> 1;
build(p << 1, l, mid);
build(p << 1 | 1, mid + 1, r);
pushup(p);
}
int len(int p){return tree[p].r - tree[p].l + 1;}
void add(int p, int x){
tree[p].laz += x;
tree[p].sum += sum[len(p)] * pw[tree[p].l - 1] % mod * x % mod;
}
void pushdown(int p){
int laz = tree[p].laz;
if(laz){
add(p << 1, laz);
add(p << 1 | 1, laz);
tree[p].laz = 0;
}
}
void update(int p, int l, int r, int x){
if(l <= tree[p].l && tree[p].r <= r){
add(p, x);
return;
}
pushdown(p);
int mid = tree[p].l + tree[p].r >> 1;
if(l <= mid) update(p << 1, l, r, x);
if(mid < r) update(p << 1 | 1, l, r, x);
pushup(p);
}
int query(int p, int l, int r){
if(l <= tree[p].l && tree[p].r <= r) return tree[p].sum;
int mid = tree[p].l + tree[p].r >> 1;
int sum = 0;
if(l <= mid) (sum += query(p << 1, l, r)) %= mod;
if(mid < r) (sum += query(p << 1 | 1, l, r)) %= mod;
return sum;
}
}T1;
struct node1{
struct nd{
int l, r, laz;
int sum;
}tree[maxn << 2];
void pushup(int p){
tree[p].sum = (tree[p << 1].sum + tree[p << 1 | 1].sum) % mod;
}
void build(int p, int l, int r){
tree[p].l = l;tree[p].r = r;
if(l == r){
tree[p].sum = a[l] * pw[n - l] % mod;
return;
}
int mid = l + r >> 1;
build(p << 1, l, mid);
build(p << 1 | 1, mid + 1, r);
pushup(p);
}
int len(int p){return tree[p].r - tree[p].l + 1;}
void add(int p, int x){
tree[p].laz += x;
tree[p].sum += sum[len(p)] * pw[n - tree[p].r] % mod * x % mod;
}
void pushdown(int p){
int laz = tree[p].laz;
if(laz){
add(p << 1, laz);
add(p << 1 | 1, laz);
tree[p].laz = 0;
}
}
void update(int p, int l, int r, int x){
if(l <= tree[p].l && tree[p].r <= r){
add(p, x);
return;
}
pushdown(p);
int mid = tree[p].l + tree[p].r >> 1;
if(l <= mid) update(p << 1, l, r, x);
if(mid < r) update(p << 1 | 1, l, r, x);
pushup(p);
}
int query(int p, int l, int r){
if(l <= tree[p].l && tree[p].r <= r) return tree[p].sum;
int mid = tree[p].l + tree[p].r >> 1;
int sum = 0;
if(l <= mid) (sum += query(p << 1, l, r)) %= mod;
if(mid < r) (sum += query(p << 1 | 1, l, r)) %= mod;
return sum;
}
}T2;
bool check(int i, int mid){
int l = i - mid, r = i + mid;
int x = T1.query(1, i + 1, r) * pw[n - i + 1] % mod;
int y = T2.query(1, l, i - 1) * pw[i] % mod;
// cout << T1.query(1, i + 1, r) << " " << T2.query(1, l, i - 1) << " ";
// cout << x - y << '\n';
// cout << ans[mid] * pw[i] * pw[n - i + 1] << " ";
return (x - y + mod) % mod == (ans[mid] % mod + mod) % mod * pw[i] % mod * pw[n - i + 1] % mod;
}
signed main(){
ios::sync_with_stdio(false);
cout.tie(0);
cin.tie(0);
cin >> n >> q >> k >> b;
for(int i = 1; i <= n; i++) cin >> a[i], a[i] = (a[i] % mod + mod) % mod;
pw[0] = 1;for(int i = 1; i <= n; i++) pw[i] = pw[i - 1] * base % mod;
for(int i = 1; i <= n; i++) sum[i] = (sum[i - 1] + pw[i - 1]) % mod;
T1.build(1, 1, n);T2.build(1, 1, n);
for(int i = 1; i <= n; i++) ans[i] = (ans[i - 1] + pw[i - 1] * ((k * i + b) % mod + mod) % mod) % mod;
while(q--){
int op;cin >> op;
if(op == 1){
int l, r, v;cin >> l >> r >> v;
T1.update(1, l, r, v);
T2.update(1, l, r, v);
}else{
int i;cin >> i;
int l = 1, r = min(n - i + 1, i), ans = 0;
while(l <= r){
int mid = l + r >> 1;
if(check(i, mid)) ans = mid, l = mid + 1;
else r = mid - 1;
}
cout << ans << '\n';
}
}
// for(int i = 1; i <= n; i++) cout << T1.query(1, i, i) << " ";cout << '\n';
return 0;
}
/*
6 2 6 2
1 5 9 13 15 18
2 3
6 6 6 2
1 5 9 10 15 18
2 2
1 3 3 -3
2 2
1 3 4 3
2 3
2 4
*/
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 9732kb
input:
6 6 6 2 1 5 9 10 15 18 2 2 1 3 3 -3 2 2 1 3 4 3 2 3 2 4
output:
1 0 2 0
result:
ok 4 number(s): "1 0 2 0"
Test #2:
score: -100
Wrong Answer
time: 11ms
memory: 12444kb
input:
5000 5000 2 0 -329 -328 -327 -326 -325 -324 -323 -322 -321 -320 -319 -318 -317 -316 -315 -314 -313 -312 -311 -310 -309 -308 -307 -306 -305 -304 -303 -302 -301 -300 -299 -298 -297 -296 -295 -294 -293 -292 -291 -290 -289 -288 -287 -286 -285 -284 -283 -282 -281 -280 -279 -278 -277 -276 -275 -274 -273 -...
output:
2 304 73 29 61 292 139 48 17 99 6 5 53 93 3 91 65 29 33 306 21 24 17 21 281 12 16 1 33 7 18 96 7 40 39 13 7 46 43 16 1 72 33 16 22 5 6 189 27 1 35 107 43 34 3 27 20 21 44 56 96 36 2 27 22 30 32 6 5 105 27 37 12 58 2 21 154 17 110 57 3 7 33 15 24 94 68 25 1 14 10 4 10 2 25 39 36 33 164 11 19 181 11 3...
result:
wrong answer 668th numbers differ - expected: '6', found: '4'