Submission #1439780
Source Code Expand
#include<ctime>
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<cassert>
#include<string>
#include<sstream>
#include<fstream>
#include<deque>
#include<queue>
#include<vector>
#include<map>
#include<list>
#include<stack>
#include<set>
#include<bitset>
#include<iomanip>
#include<utility>
#include<functional>
#include<cctype>
#include<cerrno>
#include<cfloat>
#include<ciso646>
#include<climits>
#include<clocale>
#include<complex>
#include<csetjmp>
#include<csignal>
#include<cstdarg>
#include<cstddef>
#include<cwchar>
#include<cwctype>
#include<exception>
#include<locale>
#include<numeric>
#include<new>
#include<stdexcept>
#include<limits>
using namespace std;
#define ll long long
#define INF 1e9
#define rep(i,n) for(int (i)=0;(i)<n;i++)
#define REP(i,n) for(int (i)=1;(i)<=n;i++)
#define mk(a,b) make_pair(a,b)
#define fi first
#define se second
#define pii pair<int,int>
#define sz(s) s.size()
#define all(s) (s.begin(),s.end())
const int maxn=100005;
const int mod=1e9+7;
int n,A[2];
int s[maxn];
int tree[maxn*4][2],tag[maxn*4][2];
int ne[maxn][2];
void Push(int node,int set){
if(tag[node][set]){
tree[node][set]=(tree[node][set]+tag[node][set])%mod;
tag[node*2][set]=(tag[node*2][set]+tag[node][set])%mod;
tag[node*2+1][set]=(tag[node*2+1][set]+tag[node][set])%mod;
tag[node][set]=0;
}
}
void Pull(int node,int set){
tree[node][set]=(tree[node][set]+tree[node*2][set])%mod;
tree[node][set]=(tree[node][set]+tree[node*2+1][set])%mod;
}
void update(int l,int r,int vl,int vr,int node,int val,int set){
if(vl>vr)return;
if(l>vr||r<vl)return;
if(l>=vl&&r<=vr){
tag[node][set]=(tag[node][set]+val)%mod;
Push(node,set);
return;
}
Push(node,set);
int mid=(l+r)>>1;
update(l,mid,vl,vr,node*2,val,set);
update(mid+1,r,vl,vr,node*2+1,val,set);
Pull(node,set);
}
int query(int l,int r,int vl,int vr,int node,int set){
if(l>vr||r<vl)return 0;
if(l>=vl&&r<=vr)return (tree[node][set]+tag[node][set])%mod;
Push(node,set);
int mid=(l+r)>>1;
return (query(l,mid,vl,vr,node*2,set)+query(mid+1,r,vl,vr,node*2+1,set))%mod;
}
int main(){
ios::sync_with_stdio(false);
cin>>n>>A[0]>>A[1];
rep(i,n)cin>>s[i];
ne[n-1][0]=ne[n-1][1]=n-1;
for(int i=n-2;i>=0;i--){
rep(j,2){
if(s[i+1]-s[i]>=A[j])ne[i][j]=ne[i+1][j];
else ne[i][j]=i;
}
}
rep(i,2)update(0,n-1,0,0,1,1,i);
rep(i,n){
rep(j,2){
int cur=query(0,n-1,i,i,1,j);
int low=lower_bound(s,s+n,s[i]+A[j])-s;
int high=ne[i+1][j^1];
// cout<<i<<" "<<j<<" "<<cur<<endl;
update(0,n-1,max(low-1,i+1),high,1,cur,j^1);
// cout<<"update:"<<(j^1)<<" "<<max(low-1,i+1)<<" "<<high<<endl;
// update(0,n-1,max(low,i+2),min(high+1,n-1),1,cur,j);
// cout<<"update:"<<j<<" "<<max(low,i+2)<<" "<<min(high+1,n-1)<<endl;
}
}
cout<<(query(0,n-1,n-1,n-1,1,0)+query(0,n-1,n-1,n-1,1,1))%mod;
return 0;
}
Submission Info
Submission Time |
|
Task |
C - Division into Two |
User |
little_waxberry |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
2998 Byte |
Status |
WA |
Exec Time |
123 ms |
Memory |
6784 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 1100 |
Status |
|
|
Set Name |
Test Cases |
Sample |
s1.txt, s2.txt, s3.txt, s4.txt |
All |
01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt, 38.txt, 39.txt, 40.txt, 41.txt, 42.txt, 43.txt, 44.txt, 45.txt, 46.txt, 47.txt, 48.txt, 49.txt, 50.txt, 51.txt, 52.txt, 53.txt, 54.txt, 55.txt, 56.txt, 57.txt, 58.txt, 59.txt, 60.txt, 61.txt, 62.txt, 63.txt, 64.txt, s1.txt, s2.txt, s3.txt, s4.txt |
Case Name |
Status |
Exec Time |
Memory |
01.txt |
WA |
99 ms |
5888 KB |
02.txt |
WA |
100 ms |
5888 KB |
03.txt |
WA |
100 ms |
5888 KB |
04.txt |
WA |
101 ms |
5888 KB |
05.txt |
WA |
100 ms |
5888 KB |
06.txt |
WA |
100 ms |
5888 KB |
07.txt |
WA |
100 ms |
5888 KB |
08.txt |
WA |
100 ms |
5888 KB |
09.txt |
WA |
100 ms |
5888 KB |
10.txt |
WA |
100 ms |
5888 KB |
11.txt |
AC |
100 ms |
5888 KB |
12.txt |
WA |
100 ms |
5888 KB |
13.txt |
WA |
100 ms |
5888 KB |
14.txt |
WA |
100 ms |
5888 KB |
15.txt |
WA |
100 ms |
5888 KB |
16.txt |
WA |
111 ms |
6272 KB |
17.txt |
WA |
50 ms |
5120 KB |
18.txt |
WA |
100 ms |
5888 KB |
19.txt |
WA |
103 ms |
6784 KB |
20.txt |
AC |
109 ms |
6528 KB |
21.txt |
AC |
114 ms |
6528 KB |
22.txt |
WA |
50 ms |
5120 KB |
23.txt |
WA |
111 ms |
6784 KB |
24.txt |
WA |
105 ms |
6528 KB |
25.txt |
WA |
50 ms |
5120 KB |
26.txt |
WA |
50 ms |
5120 KB |
27.txt |
WA |
50 ms |
5120 KB |
28.txt |
WA |
50 ms |
5120 KB |
29.txt |
WA |
50 ms |
5120 KB |
30.txt |
WA |
50 ms |
5120 KB |
31.txt |
WA |
52 ms |
5248 KB |
32.txt |
WA |
50 ms |
5120 KB |
33.txt |
WA |
50 ms |
5120 KB |
34.txt |
WA |
104 ms |
6784 KB |
35.txt |
WA |
100 ms |
5888 KB |
36.txt |
WA |
123 ms |
6784 KB |
37.txt |
WA |
121 ms |
6784 KB |
38.txt |
WA |
121 ms |
6784 KB |
39.txt |
WA |
100 ms |
5888 KB |
40.txt |
AC |
111 ms |
6272 KB |
41.txt |
AC |
96 ms |
6272 KB |
42.txt |
WA |
100 ms |
5888 KB |
43.txt |
WA |
50 ms |
5120 KB |
44.txt |
WA |
50 ms |
5120 KB |
45.txt |
WA |
50 ms |
5120 KB |
46.txt |
WA |
50 ms |
5120 KB |
47.txt |
WA |
100 ms |
5888 KB |
48.txt |
WA |
100 ms |
5888 KB |
49.txt |
WA |
2 ms |
2304 KB |
50.txt |
AC |
2 ms |
2304 KB |
51.txt |
AC |
2 ms |
2304 KB |
52.txt |
WA |
2 ms |
2304 KB |
53.txt |
AC |
2 ms |
2304 KB |
54.txt |
AC |
2 ms |
2304 KB |
55.txt |
AC |
2 ms |
2304 KB |
56.txt |
AC |
2 ms |
2304 KB |
57.txt |
AC |
2 ms |
2304 KB |
58.txt |
AC |
2 ms |
2304 KB |
59.txt |
AC |
2 ms |
2304 KB |
60.txt |
AC |
2 ms |
2304 KB |
61.txt |
AC |
2 ms |
2304 KB |
62.txt |
AC |
2 ms |
2304 KB |
63.txt |
AC |
2 ms |
2304 KB |
64.txt |
AC |
2 ms |
2304 KB |
s1.txt |
AC |
2 ms |
2304 KB |
s2.txt |
AC |
2 ms |
2304 KB |
s3.txt |
AC |
2 ms |
2304 KB |
s4.txt |
AC |
2 ms |
2304 KB |