QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#269043#1780. Intact Intervalslsj2009WA 1ms3688kbC++141.3kb2023-11-29 11:12:352023-11-29 11:12:35

Judging History

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

  • [2023-11-29 11:12:35]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3688kb
  • [2023-11-29 11:12:35]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
#define ll long long
#define ull unsigned long long
#define ld long double
#define PII pair<int,int>
#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3f
#define chkmax(a,b) a=max(a,b)
#define chkmin(a,b) a=min(a,b)
#define rep(k,l,r) for(int k=l;k<=r;++k)
#define per(k,r,l) for(int k=r;k>=l;--k)
#define cl(f,x) memset(f,x,sizeof(f))
using namespace std;
void file_IO() {
	freopen(".in","r",stdin);
	freopen(".out","w",stdout);
}
const int N=1e6+5,MOD=998244353;
void add(int &a,int b) {
	a+=b;
	if(a>=MOD)
		a-=MOD;
}
int qpow(int a,int b) {
	int res=1,base=a;
	while(b) {
		if(b&1)
			res=res*base%MOD;
		base=base*base%MOD; b>>=1;
	}
	return res;
}
int pre[N],a[N],n;
mt19937 rd(time(0));
map<int,int> cnt,val;
int calc(int x) {
	if(!val.count(x))
		val[x]=rd();
	return val[x];
}
void solve() {
	scanf("%lld",&n);
	rep(i,1,n) {
		int x;
		scanf("%lld",&x);
		a[i]+=calc(x);
	}
	rep(i,1,n) {
		int x;
		scanf("%lld",&x);
		a[i]-=calc(x);
	}
	rep(i,1,n) {
		pre[i]=pre[i-1]+a[i];
		++cnt[pre[i]];
	}
	if(pre[n]!=0) {
		puts("0");
		return;
	}
	int res=0;
	for(auto x:cnt)
		add(res,qpow(2,x.second-1)-1);
	printf("%lld\n",res);
}
signed main() {
//	file_IO();
	int testcase=1;
	//scanf("%d",&testcase);
	while(testcase--)
		solve();
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

2
10 9
9 10

output:

0

result:

ok single line: '0'

Test #2:

score: -100
Wrong Answer
time: 0ms
memory: 3640kb

input:

5
3 6 9 10 6
3 10 6 9 6

output:

3

result:

wrong answer 1st lines differ - expected: '4', found: '3'