QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#876826#9986. ShiorizhangmingzuWA 5460ms44100kbC++143.6kb2025-01-31 13:37:432025-01-31 13:38:11

Judging History

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

  • [2025-01-31 13:38:11]
  • 评测
  • 测评结果：WA
  • 用时：5460ms
  • 内存：44100kb
查看
  • [2025-01-31 13:37:43]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e5 + 5, blk = 1250;
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)
			{
				for (int i = lt[il]; i <= rt[il]; i++)
					a[i] = (cov[il] == -1 ? a[i] : cov[il]) + add[il];
				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];
			sum[il] = sum[ir] = 0;
			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: 16108kb

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

input:

1 1
0
1 1 1 0

output:

result:

ok 0 number(s): ""

Test #3:

score: 0
Accepted
time: 386ms
memory: 15980kb

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
17
23
1
20
2
11
27
26
2
18
2
2
0
0
0
2
4
1
0
0
0
7
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
12
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
18
23
2
24
4
12
7
4
14
5
0
2
8
4
16
10
6
4
21
15
1
3
3
0
2
5
0
2
...

result:

ok 166844 numbers

Test #4:

score: 0
Accepted
time: 389ms
memory: 13936kb

input:

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

output:

0
9
0
0
0
0
0
0
2
5
2
3
1
0
5
7
1
0
1
3
20
1
23
13
7
14
6
19
0
2
1
2
1
1
0
1
2
2
3
1
0
0
12
28
20
0
0
0
0
0
1
0
1
1
0
2
21
6
9
2
5
10
0
0
0
1
2
1
0
0
0
1
1
0
3
0
2
0
2
0
2
2
2
0
8
3
2
1
0
2
12
4
2
0
0
6
0
9
3
15
0
0
6
0
14
11
6
0
5
4
4
26
11
8
7
7
10
0
4
6
2
4
4
6
4
7
0
3
6
4
20
3
17
14
18
14
9
13
8...

result:

ok 166636 numbers

Test #5:

score: -100
Wrong Answer
time: 5460ms
memory: 44100kb

input:

500000 500000
472024 143520 268267 155743 162119 212911 326774 283734 445407 353394 432929 138490 36366 247037 157063 203731 162782 54322 321700 39379 6459 358816 32001 245189 167252 460348 113630 85323 283872 285182 191285 487821 395892 328168 467455 469639 234067 325083 145477 450046 16029 142429 ...

output:

71434
2040073
0
5432967
4856153
2204
1000102
27244642
6476935
2817769
6321297
0
1187529
2134
9498260
2084
2681823
21686068
2490676
0
2661807
0
690198
18540166
0
9360769
6235737
313778
0
9648705
0
0
8514204
8822805
3211337
10302067
7544370
2240353
483384
0
55154
33327240
18370380

result:

wrong answer 6th numbers differ - expected: '0', found: '2204'
English 繁體中文 简体中文

服务器时间: 2025-02-02 07:03:37 | 开源项目