QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#602617#9242. An Easy Geometry Problemxi_xiWA 11ms10360kbC++144.2kb2024-10-01 11:15:072024-10-01 11:15:09

Judging History

你现在查看的是最新测评结果

  • [2024-10-01 11:15:09]
  • 评测
  • 测评结果：WA
  • 用时：11ms
  • 内存：10360kb
查看
  • [2024-10-01 11:15:07]
  • 提交

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 = 1313131;
const int mod = 1e9 + 7;
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];
	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;
			v = v % mod + mod;
			v %= mod;
			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 10 15 18
1 4 4 3
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
*/
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 7736kb

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: 10360kb

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 903rd numbers differ - expected: '24', found: '16'
English 繁體中文 简体中文

Server Time: 2024-11-30 01:26:59 | OpenSource Project