QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#318563#7782. Ursa MinorNetwork_ErrorWA 71ms249612kbC++205.8kb2024-01-31 14:37:112024-01-31 14:37:12

Judging History

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

  • [2024-01-31 14:37:12]
  • 评测
  • 测评结果:WA
  • 用时:71ms
  • 内存:249612kb
  • [2024-01-31 14:37:11]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define pii pair<int, int>
#define piii tuple<int, int, int>
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define deb(var) cerr << #var << '=' << (var) << "; "
//#define int long long
namespace IO {
	#define BF 65536
	char buf[BF], *p1 = buf, *p2 = buf;
	#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, BF, stdin), p1 == p2) ? EOF : *p1++)
//	template<typename T>
	inline int uread() {
		int x = 0; char c = getchar();
		while (!isdigit(c)) c = getchar();
		while (isdigit(c)) x = x * 10 + (c ^ 48), c = getchar(); return x;
	}
//	template<typename T>
	inline int read() {
		int x = 0, f = 0; char c = getchar();
		while (!isdigit(c)) f |= c == '-', c = getchar();
		while (isdigit(c)) x = x * 10 + (c ^ 48), c = getchar(); return f ? -x : x;
	}
	char obuf[BF + 30]; int o1, o2, num[30];
	#define flush() fwrite(obuf, 1, o1, stdout), o1 = 0
	inline void putchar(const char &c) {
		obuf[o1++] = c; if (o1 >= BF) flush();
	}
//	template<typename T>
	inline void uwrite(int x) {
		do num[++o2] = x % 10; while (x /= 10);
		do obuf[o1++] = num[o2] ^ 48; while (--o2); obuf[o1++] = '\n'; if (o1 >= BF) flush();
	}
//	template<typename T>
	inline void write(const int& x) {
		if (x < 0) obuf[o1++] = '-', uwrite(-x); else uwrite(x);
	}
} using namespace IO;
const long long mod = 10000000000000793ll;
#define ll long long
inline long long mul(long long x, long long y, long long mo) {
    long long t = x * y - (long long)((long double)x / mo * y + 1e-9) * mo; return t < 0 ? t + mo : t;
}
struct Type {
	ll x;
	Type() { x = 0; }
	Type(int y) { x = y == mod ? 0 : y; }
	Type(ll y) { x = y == mod ? 0 : y; }
	friend Type operator + (Type a, Type b) {
		return Type(a.x + b.x >= mod ? a.x + b.x - mod : a.x + b.x);
	}
	friend Type operator * (Type a, Type b) {
		return Type(mul(a.x, b.x, mod));
	}
	friend Type operator - (Type a, Type b) {
		return a + Type(mod - b.x);
	}
	friend void operator += (Type& a, Type b) {
		a = a + b;
	}
	friend bool operator == (Type a, Type b) {
		return a.x == b.x;
	}
	friend bool operator != (Type a, Type b) {
		return a.x != b.x; 
	}
};
namespace Maths {
	Type power(Type x, int y) {
		Type ans = Type(1); while (y) {
			if (y & 1) ans = ans * x; y >>= 1; x = x * x;
		} return ans;
	}
	Type inv(Type x) {
		return Type(power(x.x, mod - 2)); 
	}
} using namespace Maths;
namespace Loser {
	int n, m, q, a[200010], b[200010];
	struct stable {
		int w[200010][19];
		void init() {
			for (int i = 1; i <= m; i++) w[i][0] = b[i];
			for (int k = 1; k <= 18; k++)
				for (int i = 1; i + (1 << k) - 1 <= m; i++) w[i][k] = __gcd(w[i][k - 1], w[i + (1 << (k - 1))][k - 1]);
		}
		int query(int l, int r) {
			int lg = log2(r - l + 1);
			return __gcd(w[l][lg], w[r - (1 << lg) + 1][lg]);
		}
	} st;
	const int mxk = 150;
	const int siz = 1; const Type x[siz] = {Type(1000000513)}; 
	Type powx[siz][200010], invx[siz][200010], sumx[siz][200010];
	const int blk = 500; int tot, bel[200010], L[200010 / blk + 5], R[200010 / blk + 5];
	struct block1 {   // O(1)? O(sqrt)? 
		Type w[200010], sum[200010 / blk + 5];
		void upd(int p, Type x) {
			sum[bel[p]] += x - w[p]; w[p] = x;
		}
		Type query(int l, int r) {
			Type ans = 0;
			if (bel[l] == bel[r]) {
				for (int i = l; i <= r; i++) ans += w[i]; return ans;
			}
			for (int i = bel[l] + 1; i < bel[r]; i++) ans += sum[i];
			for (int i = l; i <= R[bel[l]]; i++) ans += w[i];
			for (int i = L[bel[r]]; i <= r; i++) ans += w[i]; return ans;
		}
	} b1[mxk + 2][siz];
	struct block2 {   // O(sqrt)? O(1)? 
		Type w[200010], b[200010 / blk + 5], pre[200010]; 
		void upd(int p, Type x) {
			for (int i = p; i <= R[bel[p]]; i++) pre[i] += x - w[p]; 
			for (int i = bel[p]; i <= tot; i++) b[i] += x - w[p]; w[p] = x;
		}
		Type query(int r) {
			return b[bel[r] - 1] + pre[r];
		}
		Type query(int l, int r) {
			if (l == 1) return query(r);
			return query(r) - query(l - 1);
		}
	} b2[siz];
	void upd(int p, Type v) {
		for (int k = 1; k <= mxk; k++) {
			for (int i = 0; i < siz; i++) {
				b1[k][i].upd(p, v * powx[i][p % k]);
			}
		}
		for (int i = 0; i < siz; i++) b2[i].upd(p, v * powx[i][p]);
	}
	bool query(int l, int r, int k) {
		Type sum = b1[1][0].query(l, r);
		sum = sum * inv(Type(k));
//		if (sum.x % k) return 0; sum.x /= k;
		if (k <= mxk) {
			for (int i = 0; i < siz; i++) {
				if (b1[k][i].query(l, r) != sumx[i][k - 1] * sum) return 0;
			} return 1;
		} else { 
			for (int i = 0; i < siz; i++) {
				Type ans = 0; 
				for (int b = l / k; b <= r / k; b++) {
					int L = b * k, R = b * k + k - 1;
					L = max(L, l); R = min(R, r);
					if (L <= R) ans += b2[i].query(L, R) * invx[i][b * k];
				}
				if (ans != sumx[i][k - 1] * sum) return 0;
			} return 1;
		}
	}
	void main() {
		n = uread(), m = uread(), q = uread();
		for (int i = 1; i <= n; i++) a[i] =	 uread();
		for (int i = 1; i <= m; i++) b[i] = uread();
		for (int i = 0; i < siz; i++) {
			powx[i][0] = sumx[i][0] = invx[i][0] = 1; 
			for (int k = 1; k <= 2e5; k++) 
				powx[i][k] = powx[i][k - 1] * x[i], sumx[i][k] = sumx[i][k - 1] + powx[i][k], invx[i][k] = inv(powx[i][k]);
		}
		st.init();
		for (int i = 1; i <= n; i++) bel[i] = (i - 1) / blk + 1;
		tot = bel[n]; for (int i = 1; i <= tot; i++) L[i] = (i - 1) * blk + 1, R[i] = i * blk; R[tot] = n;
		for (int i = 1; i <= n; i++) upd(i, a[i]);
		while (q--) {
			char c = getchar();
			while (c != 'U' && c != 'Q') c = getchar();
			if (c == 'U') {
				int p = uread(), v = uread(); upd(p, v);
			} else {
				int l = uread(), r = uread(), s = uread(), t = uread(), len = __gcd(st.query(s, t), r - l + 1);
				puts(query(l, r, len) ? "Yes" : "No");
			}
		}
	}
}
signed main() { return Loser::main(), 0; }

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 71ms
memory: 249612kb

input:

6 4 5
1 1 4 5 1 4
3 3 2 4
Q 1 5 1 2
Q 2 5 3 4
U 5 2
Q 1 6 1 2
Q 2 5 3 4

output:

Yes
No
No
No

result:

wrong answer 4th words differ - expected: 'Yes', found: 'No'