QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#42299#1780. Intact IntervalspskkkWA 3ms16060kbC++171.8kb2022-08-01 21:09:442022-08-01 21:09:46

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-08-01 21:09:46]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:16060kb
  • [2022-08-01 21:09:44]
  • 提交

answer

#include <bits/stdc++.h>
#define F(i, l, r) for(int i = (l), _end_ = (int)(r); i <= _end_; ++i)
#define f(i, r, l) for(int i = (r), _end_ = (int)(l); i >= _end_; --i)
#define Set(a, v) memset(a, v, sizeof(a))
#define File(a) freopen("input.txt","r",stdin);freopen("output.txt","w",stdout)
using namespace std;
bool chkmin(int &a, int b) {return b < a ? a = b, 1 : 0;}
bool chkmax(int &a, int b) {return b > a ? a = b, 1 : 0;}

inline int read() {
 int x = 0, fh = 1; char ch = getchar();
    for (; !isdigit(ch); ch = getchar() ) if (ch == '-') fh = -1;
    for (; isdigit(ch); ch = getchar() ) x = (x<<1) + (x<<3) + (ch ^ '0');
    return x * fh;
}
int pw[1000005];
const int mod=1e9+7;
mt19937_64 rng(2333333),rng2(19260817);
vector<int>g;
int n;
int a[1000005], b[1000005];
unsigned long long val[1000005],val2[1000005];
unsigned long long psum[1000005],psum2[1000005];
unsigned long long qpow(unsigned long long x,unsigned long long y){
		unsigned long long res=1;
		while(y){
			if(y&1)res=res*x;
			x=x*x;
			y>>=1;
		}
		return res;
}
void solve(){
	n=read();
	pw[0]=1;
	F(i,1,n)a[i]=read(),g.push_back(a[i]),pw[i]=2ll*pw[i-1]%mod;
	F(i,1,n)b[i]=read();
	sort(g.begin(),g.end());
	g.resize(unique(g.begin(),g.end())-g.begin());
	F(i,1,n)a[i]=lower_bound(g.begin(),g.end(),a[i])-g.begin(),b[i]=lower_bound(g.begin(),g.end(),b[i])-g.begin();
	F(i,0,g.size()-1)val[i]=rng(),val2[i]=rng2();
	map<unsigned long long, int>cnt;
	int res=0;
    F(i,1,2*n){
        psum[i]=psum[i-1]+qpow(998244353,a[i])-qpow(998244353,b[i]);
         if(i>n){
            cnt[psum[i-n]]--;
            res=(res+pw[cnt[psum[i]]]-1+mod)%mod;
        }
        if(i<=n)cnt[psum[i]]++;
    }
    
    printf("%d\n",res);
} 
int main () {
#ifndef ONLINE_JUDGE
	File();
#endif
 	int T=1;
 //	cin>>T;
 	while(T--){
	 	solve();
	 }
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 3ms
memory: 16060kb

input:

2
10 9
9 10

output:

1

result:

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