QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#185717#5075. Fenwick Treelinzi#WA 51ms7980kbC++17732b2023-09-22 15:43:162023-09-22 15:43:16

Judging History

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

  • [2023-09-22 15:43:16]
  • 评测
  • 测评结果：WA
  • 用时：51ms
  • 内存：7980kb
查看
  • [2023-09-22 15:43:16]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
#define inf 1e18
#define mn 1000005
using namespace std;
ll a[mn],c[mn],bj[mn],ans,n,m;
string s;
inline ll low(ll x)
{
	return (x & (-x));
}
void add(ll pos,ll val,ll bjj)
{
	while (pos <= n)
	{
		c[pos]+=val;
		bj[pos]+=bjj;
		pos += pos & (-pos);
	}
}
int main()
{
	ll t,x,y,z,i,j,k;
	cin>>t;
	while(t--)
	{
		scanf("%lld",&n);
		cin>>s;
		for(i=1;i<=n;i++)
		{	
			a[i]=s[i-1]-'0';
			c[i]=bj[i]=0;
		}
		ans=0;
		for(i=1;i<=n;i++)
		if((c[i]&&a[i])||(c[i]==0&&a[i]==0))continue;
		else if(a[i]&&c[i]==0)
		{
			add(i,1,1);
			ans++;
		}
		else {
			if(bj[i]<2)ans++;
			add(i,-c[i],-bj[i]);
		}
		printf("%lld\n",ans);
	}
	return 0;
}
源文件, 语言: C++17

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 7848kb

input:

3
5
10110
5
00000
5
11111

output:

3
0
3

result:

ok 3 number(s): "3 0 3"

Test #2:

score: 0
Accepted
time: 40ms
memory: 7980kb

input:

100000
10
0000000000
10
0000000100
10
0000000000
10
1000000000
10
0000010000
10
0000000000
10
0000000000
10
0000000000
10
0100000000
10
0000000000
10
0000000001
10
0000001000
10
0000000000
10
0000000000
10
0000000001
10
0000100000
10
0010000000
10
0000000000
10
0010000000
10
0000000001
10
0000000000...

output:

0
1
0
2
2
0
0
0
2
0
1
2
0
0
1
2
2
0
2
1
0
0
2
2
2
0
2
2
2
0
2
2
0
0
2
2
0
0
2
0
2
2
0
0
0
0
0
0
0
2
2
2
2
0
1
0
2
2
0
2
2
0
2
2
0
1
0
2
0
0
2
2
0
0
0
1
2
0
2
0
0
0
0
2
2
0
0
0
0
0
0
2
0
2
2
0
2
2
2
0
0
0
0
0
0
0
1
0
0
0
2
0
2
0
0
0
2
0
2
0
0
2
0
0
0
1
0
0
1
2
0
0
2
0
2
0
0
2
0
2
0
0
0
2
0
0
2
2
1
0
...

result:

ok 100000 numbers

Test #3:

score: -100
Wrong Answer
time: 51ms
memory: 7964kb

input:

100000
10
0000001010
10
1110010000
10
0100010000
10
0001010011
10
0100001001
10
0010100000
10
0101000000
10
0100110100
10
1000001010
10
1000101001
10
1000000011
10
0000000000
10
0100011001
10
1000100101
10
0110101000
10
1000110100
10
0011100000
10
1001000000
10
0111001100
10
1100000100
10
1100110000...

output:

4
4
4
3
5
4
2
3
6
7
3
0
5
6
6
3
4
4
3
3
4
2
4
0
3
3
2
2
0
4
2
2
2
2
4
4
2
2
5
5
2
3
0
4
2
6
6
3
3
0
4
5
4
2
0
6
4
7
3
0
2
2
2
1
4
2
2
5
3
0
4
0
0
4
5
0
0
2
5
3
2
4
1
0
2
4
3
2
1
2
2
2
4
2
5
3
3
1
2
4
0
0
2
5
4
2
4
0
5
7
5
2
7
3
2
4
4
5
0
3
4
4
2
2
0
4
2
0
4
4
9
2
2
5
6
2
6
4
2
0
5
2
1
2
4
6
6
0
2
1
...

result:

wrong answer 1075th numbers differ - expected: '5', found: '4'
English 繁體中文 简体中文

服务器时间: 2024-12-05 06:41:53 | 开源项目