QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#603837#9242. An Easy Geometry Problemxi_xiCompile Error//C++148.4kb2024-10-01 20:02:062024-10-01 20:02:07

Judging History

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

  • [2024-10-01 20:02:07]
  • 评测
查看
  • [2024-10-01 20:02:06]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define int long long
using namespace std;

const int maxn = 1e6 + 5;
const int base = 4545454545;
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];
	int len(int p){return tree[p].r - tree[p].l + 1;}
	void pushup(int p){
		tree[p].sum = (tree[p << 1].sum + tree[p << 1 | 1].sum * pw[len(p << 1)]) % 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] * base % mod;
			return;
		}
		int mid = l + r >> 1;
		build(p << 1, l, mid);
		build(p << 1 | 1, mid + 1, r);
		pushup(p);
	}
	void add(int p, int x){
		(tree[p].laz += x) %= mod;
		(tree[p].sum += sum[len(p)] % 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(tree[p].l > r || tree[p].r < l) return 0;
		if(l <= tree[p].l && tree[p].r <= r) return tree[p].sum;
		pushdown(p);
		int mid = tree[p].l + tree[p].r >> 1;
		if(l > mid) return query(p << 1 | 1, l, r);
		if(r <= mid) return query(p << 1, l, r);
		return (query(p << 1, l, r) + query(p << 1 | 1, l, r) * pw[mid - l + 1]) % mod;
	}
}T1;

struct node1{
	struct nd{
		int l, r, laz;
		int sum;
	}tree[maxn << 2];
	int len(int p){return tree[p].r - tree[p].l + 1;}
	void pushup(int p){
		tree[p].sum = (tree[p << 1].sum * pw[len(p << 1 | 1)] + 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] * base % mod;
			return;
		}
		int mid = l + r >> 1;
		build(p << 1, l, mid);
		build(p << 1 | 1, mid + 1, r);
		pushup(p);
	}
	void add(int p, int x){
		(tree[p].laz += x) %= mod;
		(tree[p].sum += sum[len(p)] % 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;
		pushdown(p);
		int mid = tree[p].l + tree[p].r >> 1;
		if(l > mid) return query(p << 1 | 1, l, r);
		if(r <= mid) return query(p << 1, l, r);
		return (query(p << 1, l, r) * pw[r - mid] + query(p << 1 | 1, l, r)) % mod;
	}
}T2;

bool check(int i, int mid){
	int x = T1.query(1, i + 1, i + mid) % mod;
	int y = T2.query(1, i - mid, i - 1) % mod;
	return (x - y + mod) % mod == (ans[mid] % mod + mod) % mod;
}

signed main(){
    ios::sync_with_stdio(false);
    cout.tie(0);
    cin.tie(0);
	
	cin >> n >> q >> k >> b; k = (k + mod) % mod, b = (b + mod) % mod;
	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]) % 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] * ((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, i - 1), 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
*/#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define int long long
using namespace std;

const int maxn = 1e6 + 5;
const int base = 2333;
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];
	int len(int p){return tree[p].r - tree[p].l + 1;}
	void pushup(int p){
		tree[p].sum = (tree[p << 1].sum + tree[p << 1 | 1].sum * pw[len(p << 1)]) % 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] * base % mod;
			return;
		}
		int mid = l + r >> 1;
		build(p << 1, l, mid);
		build(p << 1 | 1, mid + 1, r);
		pushup(p);
	}
	void add(int p, int x){
		tree[p].laz += x;
		tree[p].sum += sum[len(p)] % 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(tree[p].l > r || tree[p].r < l) return 0;
		if(l <= tree[p].l && tree[p].r <= r) return tree[p].sum;
		pushdown(p);
		int mid = tree[p].l + tree[p].r >> 1;
		if(l > mid) return query(p << 1 | 1, l, r);
		if(r <= mid) return query(p << 1, l, r);
		return (query(p << 1, l, r) + query(p << 1 | 1, l, r) * pw[mid - l + 1]) % mod;
	}
}T1;

struct node1{
	struct nd{
		int l, r, laz;
		int sum;
	}tree[maxn << 2];
	int len(int p){return tree[p].r - tree[p].l + 1;}
	void pushup(int p){
		tree[p].sum = (tree[p << 1].sum * pw[len(p << 1 | 1)] + 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] * base % mod;
			return;
		}
		int mid = l + r >> 1;
		build(p << 1, l, mid);
		build(p << 1 | 1, mid + 1, r);
		pushup(p);
	}
	void add(int p, int x){
		tree[p].laz += x;
		tree[p].sum += sum[len(p)] % 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;
		pushdown(p);
		int mid = tree[p].l + tree[p].r >> 1;
		if(l > mid) return query(p << 1 | 1, l, r);
		if(r <= mid) return query(p << 1, l, r);
		return (query(p << 1, l, r) * pw[r - mid] + query(p << 1 | 1, l, r)) % mod;
	}
}T2;

bool check(int i, int mid){
	int x = T1.query(1, i + 1, i + mid) % mod;
	int y = T2.query(1, i - mid, i - 1) % mod;
	return (x - y + mod) % mod == (ans[mid] % mod + mod) % mod;
}

signed main(){
    ios::sync_with_stdio(false);
    cout.tie(0);
    cin.tie(0);
	
	cin >> n >> q >> k >> b; k = (k + mod) % mod, b = (b + mod) % mod;
	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]) % 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] * ((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, i - 1), 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
*/
Source code, Language: C++14

Details 

answer.code:178:11: error: redefinition of ‘const long long int maxn’
  178 | const int maxn = 1e6 + 5;
      |           ^~~~
answer.code:7:11: note: ‘const long long int maxn’ previously defined here
    7 | const int maxn = 1e6 + 5;
      |           ^~~~
answer.code:179:11: error: redefinition of ‘const long long int base’
  179 | const int base = 2333;
      |           ^~~~
answer.code:8:11: note: ‘const long long int base’ previously defined here
    8 | const int base = 4545454545;
      |           ^~~~
answer.code:180:11: error: redefinition of ‘const long long int mod’
  180 | const int mod = 998244353;
      |           ^~~
answer.code:9:11: note: ‘const long long int mod’ previously defined here
    9 | const int mod = 998244353;
      |           ^~~
answer.code:181:5: error: redefinition of ‘long long int n’
  181 | int n, q, k, b, a[maxn];
      |     ^
answer.code:10:5: note: ‘long long int n’ previously declared here
   10 | int n, q, k, b, a[maxn];
      |     ^
answer.code:181:8: error: redefinition of ‘long long int q’
  181 | int n, q, k, b, a[maxn];
      |        ^
answer.code:10:8: note: ‘long long int q’ previously declared here
   10 | int n, q, k, b, a[maxn];
      |        ^
answer.code:181:11: error: redefinition of ‘long long int k’
  181 | int n, q, k, b, a[maxn];
      |           ^
answer.code:10:11: note: ‘long long int k’ previously declared here
   10 | int n, q, k, b, a[maxn];
      |           ^
answer.code:181:14: error: redefinition of ‘long long int b’
  181 | int n, q, k, b, a[maxn];
      |              ^
answer.code:10:14: note: ‘long long int b’ previously declared here
   10 | int n, q, k, b, a[maxn];
      |              ^
answer.code:181:17: error: redefinition of ‘long long int a [1000005]’
  181 | int n, q, k, b, a[maxn];
      |                 ^
answer.code:10:17: note: ‘long long int a [1000005]’ previously declared here
   10 | int n, q, k, b, a[maxn];
      |                 ^
answer.code:182:5: error: redefinition of ‘long long int pw [1000005]’
  182 | int pw[maxn], sum[maxn], ans[maxn];
      |     ^~
answer.code:11:5: note: ‘long long int pw [1000005]’ previously declared here
   11 | int pw[maxn], sum[maxn], ans[maxn];
      |     ^~
answer.code:182:15: error: redefinition of ‘long long int sum [1000005]’
  182 | int pw[maxn], sum[maxn], ans[maxn];
      |               ^~~
answer.code:11:15: note: ‘long long int sum [1000005]’ previously declared here
   11 | int pw[maxn], sum[maxn], ans[maxn];
      |               ^~~
answer.code:182:26: error: redefinition of ‘long long int ans [1000005]’
  182 | int pw[maxn], sum[maxn], ans[maxn];
      |                          ^~~
answer.code:11:26: note: ‘long long int ans [1000005]’ previously declared here
   11 | int pw[maxn], sum[maxn], ans[maxn];
      |                          ^~~
answer.code:183:8: error: redefinition of ‘struct node’
  183 | struct node{
      |        ^~~~
answer.code:12:8: note: previous definition of ‘struct node’
   12 | struct node{
      |        ^~~~
answer.code:235:2: error: conflicting declaration ‘int T1’
  235 | }T1;
      |  ^~
answer.code:64:2: note: previous declaration as ‘node T1’
   64 | }T1;
      |  ^~
answer.code:237:8: error: redefinition of ‘struct node1’
  237 | struct node1{
      |        ^~~~~
answer.code:66:8: note: previous definition of ‘struct node1’
   66 | struct node1{
      |        ^~~~~
answer.code:288:2: error: conflicting declaration ‘int T2’
  288 | }T2;
      |  ^~
answer.code:117:2: note: previous declaration as ‘node1 T2’
  117 | }T2;
      |  ^~
answer.code:290:6: error: redefinition of ‘bool check(long long int, long long int)’
  290 | bool check(int i, int mid){
      |      ^~~~~
answer.code:119:6: note: ‘bool check(long long int, long long int)’ previously defined here
  119 | bool check(int i, int mid){
      |      ^~~~~
answer.code:296:8: error: redefinition of ‘int main()’
  296 | signed main(){
      |        ^~~~
answer.code:125:8: note: ‘int main()’ previously defined here
  125 | signed main(){
      |        ^~~~
English 繁體中文 简体中文

Server Time: 2024-11-30 02:32:03 | OpenSource Project