QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#876842#9986. ShiorizhangmingzuWA 618ms18024kbC++143.6kb2025-01-31 13:53:512025-01-31 13:53:52

Judging History

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

  • [2025-01-31 13:53:52]
  • 评测
  • 测评结果：WA
  • 用时：618ms
  • 内存：18024kb
查看
  • [2025-01-31 13:53:51]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e5 + 5, blk = 3;
int n, m, a[maxn], add[maxn], lt[maxn], rt[maxn], bel[maxn], cov[maxn];
long long sum[maxn];
bitset<maxn> bt[405];
void re(int x)
{
	sum[x] = 0;
	if (~cov[x]) for (int j = lt[x]; j <= rt[x]; j++) a[j] = cov[x];
	cov[x] = -1;
	bt[x].reset();
	for (int j = lt[x]; j <= rt[x]; j++)
	{
		a[j] += add[x], sum[x] += a[j];
		if (a[j] < n) bt[x].set(a[j]);
	}
	add[x] = 0;
}
bool check(int x, int l, int r)
{
	int il = bel[l], ir = bel[r];
	for (int i = l; i <= min(r, rt[il]); i++)
	{
		int tmp = a[i];
		if (~cov[il]) tmp = cov[il];
		tmp += add[il];
		if (tmp == x) return 1;
	}
	if (il != ir)
		for (int i = lt[ir]; i <= r; i++)
		{
			int tmp = a[i];
			if (~cov[ir]) tmp = cov[ir];
			tmp += add[ir];
			if (tmp == x) return 1;
		}
	for (int i = il + 1; i < ir; i++)
	{
		if (~cov[i])
		{
			if (x == add[i] + cov[i]) return 1;
		}
		else if (x >= add[i] && bt[i][x - add[i]]) return 1;
	}
	return 0;
}
signed main()
{
//	freopen("1.in", "r", stdin);
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    memset(cov, -1, sizeof(cov));
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i += blk)
    {
    	int l = i, r = min(n, i + blk - 1), id = (i - 1) / blk + 1;
    	lt[id] = l, rt[id] = r;
    	for (int j = l; j <= r; j++)
    	{
    		if (a[j] < n) bt[id].set(a[j]);
			bel[j] = id;
		}
	}
	while (m--)
	{
		int op, l, r, v;
		cin >> op >> l >> r;
		int il = bel[l], ir = bel[r];
		if (op == 1)
		{
			cin >> v;
			if (il == ir)
			{
				sum[il] = 0;
				for (int i = lt[il]; i <= rt[il]; i++)
					a[i] = (cov[il] == -1 ? a[i] : cov[il]) + add[il], sum[il] += a[i];
				cov[il] = -1, add[il] = 0;
				for (int i = l; i <= r; i++) a[i] = v;
				re(il);
				continue;
			}
			for (int i = il + 1; i < ir; i++)
			{
				cov[i] = v, add[i] = 0;
				sum[i] = 1ll * v * (rt[i] - lt[i] + 1);
			}
			for (int i = lt[il]; i <= rt[il]; i++)
				a[i] = (cov[il] == -1 ? a[i] : cov[il]) + add[il];
			for (int i = lt[ir]; i <= rt[ir]; i++)
				a[i] = (cov[ir] == -1 ? a[i] : cov[ir]) + add[ir];
			cov[il] = cov[ir] = -1, add[il] = add[ir] = 0;
			for (int i = l; i <= rt[il]; i++) a[i] = v;
			for (int i = lt[ir]; i <= r; i++) a[i] = v;
			sum[il] = sum[ir] = 0;
			for (int i = lt[il]; i <= rt[il]; i++) sum[il] += a[i];
			for (int i = lt[ir]; i <= rt[ir]; i++) sum[ir] += a[i];
			re(il), re(ir);
		}
		else if (op == 2)
		{
			int i;
			for (i = 0; check(i, l, r); i++);
			if (~cov[il])
			{
				for (int j = lt[il]; j <= rt[il]; j++)
					a[j] = cov[il];
				cov[il] = -1;
			}
			if (~cov[ir])
			{
				for (int j = lt[ir]; j <= rt[ir]; j++)
					a[j] = cov[ir];
				cov[ir] = -1;
			}
			for (int j = l; j <= min(r, rt[il]); j++)
				a[j] += i, sum[j] += i;
			re(il);
			if (il != ir)
			{
				for (int j = lt[ir]; j <= r; j++)
					a[j] += i, sum[j] += i;
				re(ir);
			}
			for (int j = il + 1; j < ir; j++)
				add[j] += i, sum[j] += 1ll * i * (rt[j] - lt[j] + 1);
		}
		else
		{
			long long ans = 0;
			for (int i = il + 1; i < ir; i++)
				ans += sum[i];
			for (int i = l; i <= min(r, rt[il]); i++)
			{
				if (~cov[il]) ans += cov[il] + add[il];
				else ans += a[i] + add[il];
			}
			if (il != ir)
				for (int i = lt[ir]; i <= r; i++)
				{
					if (~cov[ir]) ans += cov[ir] + add[ir];
					else ans += a[i] + add[ir];
				}
			cout << ans << '\n';
		}
	}
    return 0;
}
/*
5 8
0 7 2 1 0
1 2 4 0
2 1 3
2 3 4
3 1 3
1 2 3 4
3 1 4
2 1 5
3 2 5
*/
源文件, 语言: C++14

詳細信息

Test #1:

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

input:

5 8
0 7 2 1 0
1 2 4 0
2 1 3
2 3 4
3 1 3
1 2 3 4
3 1 4
2 1 5
3 2 5

output:

5
11
22

result:

ok 3 number(s): "5 11 22"

Test #2:

score: 0
Accepted
time: 0ms
memory: 15976kb

input:

1 1
0
1 1 1 0

output:

result:

ok 0 number(s): ""

Test #3:

score: -100
Wrong Answer
time: 618ms
memory: 14308kb

input:

10 500000
0 0 0 0 0 0 0 0 0 0
3 2 9
2 4 10
2 2 7
2 7 9
3 1 1
3 5 8
1 5 10 0
3 1 9
3 5 9
2 2 4
1 2 4 0
2 5 6
3 8 8
1 4 6 0
1 6 6 0
2 4 10
3 1 9
3 5 7
1 4 10 0
3 6 9
3 2 6
2 1 8
1 5 9 0
3 7 8
3 4 8
2 4 8
2 5 8
2 1 9
2 3 8
1 5 10 0
2 4 8
3 1 6
2 1 4
2 3 7
3 4 10
1 4 6 0
1 1 6 0
2 3 7
1 1 1 0
2 1 10
1 5...

output:

0
0
10
7
0
0
6
3
0
0
0
1
25
12
10
0
0
0
0
19
24
1
21
2
11
27
26
2
18
2
2
0
0
0
2
4
1
0
0
0
8
2
0
4
32
15
7
11
0
4
5
2
8
5
1
6
0
7
0
7
6
3
2
5
0
0
0
7
14
2
5
0
2
0
0
6
14
6
0
2
3
0
0
1
16
12
1
1
12
0
3
4
4
10
3
16
0
17
2
4
0
0
16
8
2
8
19
23
2
24
4
12
7
4
14
5
0
2
8
4
17
10
6
4
21
15
1
3
3
0
2
6
0
2
...

result:

wrong answer 20th numbers differ - expected: '17', found: '19'
English 繁體中文 简体中文

伺服器時間: 2025-02-02 07:01:12 | 開源專案