Submission #1751649
Source Code Expand
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 100010;
const ll MOD = 1000000007;
int n;
ll s[MAXN], A, B, ans;
template<typename T> inline T read() {
T x(0), f(1);
char ch = getchar();
for(; !isdigit(ch); ch = getchar()) if(ch=='-') f=-1;
for(; isdigit(ch); ch = getchar()) x = (x*10)+(ch^48);
return x * f;
}
inline void Update(ll &cur, ll val) {
cur += val;
if(cur >= MOD) cur -= MOD;
}
struct Seg_T {
#define mid ((l+r)>>1)
#define ls (p<<1)
#define rs (p<<1|1)
ll sum[MAXN*4], tag[MAXN*4];
inline void init() {
memset(tag, -1, sizeof(tag));
}
inline void pushdown(int p, int l, int r) {
if(tag[p] != -1) {
tag[ls] = tag[rs] = tag[p];
sum[ls] = tag[p]*l%MOD;
sum[rs] = tag[p]*r%MOD;
tag[p] = -1;
}
}
inline void modify(int p, int l, int r, int x, int y, ll val) {
if(l == x && r == y) {
tag[p] = val;
sum[p] = val*(y-x+1)%MOD;
return;
}
pushdown(p, mid-l+1, r-mid);
if(y <= mid) modify(ls, l, mid, x, y, val);
else if(x > mid) modify(rs, mid+1, r, x, y, val);
else {
modify(ls, l, mid, x, mid, val);
modify(rs, mid+1, r, mid+1, y, val);
}
sum[p] = (sum[ls]+sum[rs])%MOD;
}
inline ll query(int p, int l, int r, int x, int y) {
if(l == x && r == y) return sum[p];
pushdown(p, mid-l+1, r-mid);
if(y <= mid) return query(ls, l, mid, x, y);
if(x > mid) return query(rs, mid+1, r, x, y);
return (query(ls, l, mid, x, mid)+query(rs, mid+1, r, mid+1, y))%MOD;
}
}f, g;
int main() {
int i, j;
n = read<int>();
A = read<ll>(), B = read<ll>();
if(A > B) swap(A, B);
for(i = 1; i <= n; i++) s[i] = read<ll>();
f.init(), g.init();
f.modify(1, 1, n, 1, 1, 1);
g.modify(1, 1, n, 1, 1, 1);
/*for(i = 1; i <= n; i++) printf("%lld ", f.query(1, 1, n, i, i));
printf("\n");
for(i = 1; i <= n; i++) printf("%lld ", g.query(1, 1, n, i, i));
printf("\n");*/
for(i = 1; i < n; i++) {
int loc = upper_bound(s+1, s+n+1, s[i+1]-B)-s-1;
ll res = f.query(1, 1, n, 1, min(loc+1, i));
//printf("%d:%lld ", loc, res);
g.modify(1, 1, n, i+1, i+1, res);
loc = upper_bound(s+1, s+n+1, s[i+1]-A)-s-1;
res = g.query(1, 1, n, 1, min(loc+1, i));
//printf("%d:%lld\n", loc, res);
f.modify(1, 1, n, i+1, i+1, res);
if(s[i+1]-s[i] < A) {
f.modify(1, 1, n, 1, i, 0);
//printf("fclear(%d, %d)\n", 1, i);
}
if(s[i+1]-s[i] < B) {
g.modify(1, 1, n, 1, i, 0);
//printf("gclear(%d, %d)\n", 1, i);
}
}
Update(ans, f.query(1, 1, n, 1, n));
Update(ans, g.query(1, 1, n, 1, n));
printf("%lld\n", ans);
return 0;
}
Submission Info
Submission Time |
|
Task |
C - Division into Two |
User |
Sunshine_cfbsl |
Language |
C++14 (GCC 5.4.1) |
Score |
1100 |
Code Size |
2645 Byte |
Status |
AC |
Exec Time |
116 ms |
Memory |
13568 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
1100 / 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 |
AC |
98 ms |
13568 KB |
02.txt |
AC |
98 ms |
13568 KB |
03.txt |
AC |
114 ms |
13568 KB |
04.txt |
AC |
115 ms |
13568 KB |
05.txt |
AC |
98 ms |
13568 KB |
06.txt |
AC |
115 ms |
13568 KB |
07.txt |
AC |
114 ms |
13568 KB |
08.txt |
AC |
94 ms |
13568 KB |
09.txt |
AC |
111 ms |
13568 KB |
10.txt |
AC |
111 ms |
13568 KB |
11.txt |
AC |
116 ms |
13568 KB |
12.txt |
AC |
82 ms |
13568 KB |
13.txt |
AC |
100 ms |
13568 KB |
14.txt |
AC |
108 ms |
13568 KB |
15.txt |
AC |
115 ms |
13568 KB |
16.txt |
AC |
79 ms |
13568 KB |
17.txt |
AC |
81 ms |
13568 KB |
18.txt |
AC |
84 ms |
13568 KB |
19.txt |
AC |
93 ms |
13568 KB |
20.txt |
AC |
99 ms |
13568 KB |
21.txt |
AC |
99 ms |
13568 KB |
22.txt |
AC |
93 ms |
13568 KB |
23.txt |
AC |
91 ms |
13568 KB |
24.txt |
AC |
97 ms |
13568 KB |
25.txt |
AC |
102 ms |
13568 KB |
26.txt |
AC |
100 ms |
13568 KB |
27.txt |
AC |
101 ms |
13568 KB |
28.txt |
AC |
102 ms |
13568 KB |
29.txt |
AC |
100 ms |
13568 KB |
30.txt |
AC |
100 ms |
13568 KB |
31.txt |
AC |
97 ms |
13568 KB |
32.txt |
AC |
97 ms |
13568 KB |
33.txt |
AC |
99 ms |
13568 KB |
34.txt |
AC |
94 ms |
13568 KB |
35.txt |
AC |
97 ms |
13568 KB |
36.txt |
AC |
71 ms |
13568 KB |
37.txt |
AC |
96 ms |
13568 KB |
38.txt |
AC |
91 ms |
13568 KB |
39.txt |
AC |
100 ms |
13568 KB |
40.txt |
AC |
106 ms |
13568 KB |
41.txt |
AC |
102 ms |
13568 KB |
42.txt |
AC |
101 ms |
13568 KB |
43.txt |
AC |
81 ms |
13568 KB |
44.txt |
AC |
82 ms |
13568 KB |
45.txt |
AC |
82 ms |
13568 KB |
46.txt |
AC |
81 ms |
13568 KB |
47.txt |
AC |
83 ms |
13568 KB |
48.txt |
AC |
85 ms |
13568 KB |
49.txt |
AC |
4 ms |
10752 KB |
50.txt |
AC |
4 ms |
10752 KB |
51.txt |
AC |
4 ms |
10752 KB |
52.txt |
AC |
4 ms |
10752 KB |
53.txt |
AC |
4 ms |
10752 KB |
54.txt |
AC |
4 ms |
10752 KB |
55.txt |
AC |
4 ms |
10752 KB |
56.txt |
AC |
4 ms |
10752 KB |
57.txt |
AC |
4 ms |
10752 KB |
58.txt |
AC |
4 ms |
10752 KB |
59.txt |
AC |
4 ms |
10752 KB |
60.txt |
AC |
4 ms |
10752 KB |
61.txt |
AC |
4 ms |
10752 KB |
62.txt |
AC |
4 ms |
10752 KB |
63.txt |
AC |
4 ms |
10752 KB |
64.txt |
AC |
4 ms |
10752 KB |
s1.txt |
AC |
4 ms |
10752 KB |
s2.txt |
AC |
4 ms |
10752 KB |
s3.txt |
AC |
4 ms |
10752 KB |
s4.txt |
AC |
4 ms |
10752 KB |