QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#876792#9986. ShiorizhangmingzuWA 3873ms96580kbC++143.4kb2025-01-31 13:09:272025-01-31 13:09:27

Judging History

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

  • [2025-01-31 13:09:27]
  • 评测
  • 测评结果：WA
  • 用时：3873ms
  • 内存：96580kb
查看
  • [2025-01-31 13:09:27]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e5 + 5, blk = 400;
int n, m, a[maxn], add[maxn], lt[maxn], rt[maxn], bel[maxn], cov[maxn];
long long sum[maxn];
bitset<maxn> bt[2005];
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 (bt[i][x]) return 1;
	return 0;
}
signed main()
{
    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];
				for (int i = l; i <= r; i++) a[i] = v;
				re(il);
				continue;
			}
			continue;
			for (int i = il + 1; i < ir; i++)
			{
				cov[i] = v, add[i] = 0, bt[i].reset();
				if (v < n) bt[i].set(v);
				sum[i] = 1ll * v * (rt[i] - lt[i] + 1);
			}
			for (int i = lt[il]; i <= rt[il]; i++) a[i] = cov[il];
			for (int i = lt[il]; i <= rt[il]; i++) a[i] += add[il];
			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)
		{
//			if (n >= 100) continue;
			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
		{
//			if (n >= 100) continue;
			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: 15980kb

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

input:

1 1
0
1 1 1 0

output:

result:

ok 0 number(s): ""

Test #3:

score: 0
Accepted
time: 385ms
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: 384ms
memory: 18020kb

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: 3873ms
memory: 96580kb

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:

14762902296
79816190583
18785433087
43424977220
44669356924
33274690696
55469791697
45803807118
46503571817
3102718791
27394792696
7876922664
11588516248
34683855798
98060959017
19915531330
6317092334
107906025298
78072767414
44358947965
34054380791
13431268326
48812539738
79483417799
18209836043
57...

result:

wrong answer 1st numbers differ - expected: '71434', found: '14762902296'
English 繁體中文 简体中文

伺服器時間: 2025-02-02 05:49:43 | 開源專案