QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#74737#5000. Balanced Seesaw ArrayXKError#RE 0ms0kbC++143.1kb2023-02-03 16:36:552023-02-03 16:36:57

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-02-03 16:36:57]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2023-02-03 16:36:55]
  • 提交

answer

#include <bits/stdc++.h>

#define maxn 1000005
//#define ll long long
#define inf 1000000000
#define int long long

using namespace std;

int n, q;
int a[maxn];
int s1[maxn];
int s2[maxn];
int tg1[maxn];
int tg2[maxn];

int bel[maxn];
int bl[maxn];
int br[maxn];

void pushdown(int p) {
	if (tg1[p] != inf) {
		for (int i = bl[p]; i <= br[p]; i++) a[i] = tg1[p];
		tg1[p] = inf;
	}
	if (tg2[p] != inf) {
		for (int i = bl[p]; i <= br[p]; i++) a[i] += tg2[p];
		tg2[p] = inf;
	}
}

void Swork1(int p, int l, int r, int k) {
	pushdown(p);
	for (int i = l; i <= r; i++) a[i] = k;
	s1[p] = s2[p] = 0;
	for (int i = bl[p]; i <= br[p]; i++) s1[i] += a[i];
	for (int i = bl[p]; i <= br[p]; i++) s2[i] += 1ll * a[i] * i;
} 

void Wwork1(int p, int k) {
	tg1[p] = k, tg2[p] = inf;
	s1[p] = 1ll * k * (br[p] - bl[p] + 1);
	s2[p] = 1ll * k * (br[p] + bl[p]) * (br[p] - bl[p] + 1);
}

void Swork2(int p, int l, int r, int k) {
	pushdown(p);
	for (int i = l; i <= r; i++) a[i] += k;
	s1[p] = s2[p] = 0;
	for (int i = bl[p]; i <= br[p]; i++) s1[i] += a[i];
	for (int i = bl[p]; i <= br[p]; i++) s2[i] += 1ll * a[i] * i;
}

void Wwork2(int p, int k) {
	if (tg2[p] == inf) tg2[p] = k;
	else tg2[p] += k;
	s1[p] += 1ll * k * (br[p] - bl[p] + 1);
	s2[p] += 1ll * k * (br[p] + bl[p]) * (br[p] - bl[p] + 1);
} 

pair<int, int> Sqry(int p, int l, int r) {
	pushdown(p);
	pair<int, int> res = {0, 0};
	for (int i = l; i <= r; i++) res.first += a[i], res.second += a[i] * i;
	return res;
}

pair<int, int> Wqry(int p) {
	return {s1[p], s2[p]};
}

pair<int, int> add(pair<int, int> &a, pair<int, int> b) {
	a.first += b.first;
	a.second += b.second;
}

signed main() {
	scanf("%lld%lld", &n, &q);
	for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
	int B = sqrt(n), cnt = 0;
	for (int i = 1; i <= n; i += B) {
		int l = i, r = min(l + B - 1, n);
		bl[++cnt] = l;
		br[cnt] = r;
		tg1[cnt] = tg2[cnt] = inf;
		for (int j = l; j <= r; j++) {
			bel[j] = cnt;
			s1[cnt] += a[j];
			s2[cnt] += 1ll * a[j] * j;
		}
	}
	while (q--) {
		int op, l, r, k;
		scanf("%lld", &op);
		if (op == 1) {
			scanf("%lld%lld%lld", &l, &r, &k);
			if (bel[l] == bel[r]) Swork2(bel[l], l, r, k);
			else {
				Swork2(bel[l], l, br[bel[l]], k);
				Swork2(bel[r], bl[bel[r]], r, k);
				for (int i = bel[l] + 1; i < bel[r]; i++) Wwork2(i, k);
			}
		}
		else if (op == 2) {
			scanf("%lld%lld%lld", &l, &r, &k);
			if (bel[l] == bel[r]) Swork1(bel[l], l, r, k);
			else {
				Swork1(bel[l], l, br[bel[l]], k);
				Swork1(bel[r], bl[bel[r]], r, k);
				for (int i = bel[l] + 1; i < bel[r]; i++) Wwork1(i, k);
			}
		}
		else {
			scanf("%lld%lld", &l, &r);
			pair<int, int> res;
			if (bel[l] == bel[r]) res = Sqry(bel[l], l, r);
			else {
				add(res, Sqry(bel[l], l, br[bel[l]]));
				add(res, Sqry(bel[r], bl[bel[r]], r));
				for (int i = bel[l] + 1; i < bel[r]; i++) add(res, Wqry(i));
			}
			if (res.first == 0) {
				if (res.second == 0) puts("Yes");
				else puts("No");
			}
			else if (res.second % res.first) puts("No");
			else puts("Yes");
		}
	}
	return 0;
}

详细

Test #1:

score: 0
Runtime Error

input:

3 6
1 2 3
3 1 1
3 1 3
1 1 1 2
3 1 3
2 2 2 0
3 2 3

output:


result: