Submission #3429075
Source Code Expand
/*
#include <boost/functional/hash.hpp>
#include <boost/multiprecision/cpp_int.hpp>
typedef boost::multiprecision::cpp_int mlint;
*/
#include <bits/stdc++.h>
using namespace std;
#define debug 0
#define print(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
#define fcout(d) cout << fixed << setprecision(d)
#define each(i,v) for(auto i = begin(v); i != end(v); ++i)
#define reach(i,v) for(auto i = rbegin(v); i != rend(v); ++i)
#define urep(i,s,t) for(int i = (int)(s); i <= (int)(t); ++i)
#define drep(i,s,t) for(int i = (int)(s); i >= (int)(t); --i)
#define rep(i,n) urep(i,0,(n) - 1)
#define rep1(i,n) urep(i,1,(n))
#define rrep(i,n) drep(i,(n) - 1,0)
#define all(v) begin(v),end(v)
#define rall(v) rbegin(v),rend(v)
#define vct vector
#define prique priority_queue
#define l_bnd lower_bound
#define u_bnd upper_bound
#define rsz resize
#define ers erase
#define emp emplace
#define emf emplace_front
#define emb emplace_back
#define pof pop_front
#define pob pop_back
#define mkp make_pair
#define mkt make_tuple
#define fir first
#define sec second
typedef long long ll;
typedef double db;
typedef vct<vct<ll>> mat;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tiii;
typedef map<int,int> mpii;
typedef unordered_map<int,int> umpii;
template <class T, class U> ostream& operator << (ostream& s, pair<T,U> p) { return s << p.fir << " " << p.sec; }
template <class T> ostream& operator << (ostream& s, vct<T> v) { each(i,v) { if(i != begin(v)) s << " "; s << *i; } return s; }
auto esc = [](auto ret) { cout << ret << endl; exit(0); };
auto odd = [](auto x) { return x & 1; };
auto even = [](auto x) { return !odd(x); };
auto qceil = [](auto x, auto y) { return x > 0 ? (x - 1) / y + 1 : x / y; };
auto parity = [](auto x, auto y) { return odd(x) ^ even(y); };
auto chmax = [](auto& m, auto x) { if(m < x) { m = x; return 1; } return 0; };
auto chmin = [](auto& m, auto x) { if(m > x) { m = x; return 1; } return 0; };
auto cmprs = [](auto v) {
auto tmp = v;
sort(all(tmp));
tmp.erase(unique(all(tmp)),end(tmp));
each(i,v) *i = l_bnd(all(tmp),*i) - begin(tmp) + 1;
return v;
};
const int dir[8][2] = { {1,0},{0,1},{-1,0},{0,-1},{1,1},{-1,1},{-1,-1},{1,-1} };
const ll inf32 = (1 << 30) - 1;
const ll inf64 = (1LL << 62) - 1;
const ll mod = 1e9 + 7;
const db eps = 1e-15;
template <class Abel = int> struct Segtree {
typedef function<Abel(const Abel&, const Abel&)> func_type;
const func_type opr;
const Abel idel;
int range = 1;
vector<Abel> data;
Segtree(int sz, Abel init_val, const func_type& f = plus<Abel>(), Abel id = 0) : opr(f),idel(id)
{
while(sz >= range) range <<= 1;
init(init_val);
}
Segtree(int sz, vector<Abel> init_arr, const func_type& f = plus<Abel>()) : opr(f)
{
while(sz >= range) range <<= 1;
init(init_arr);
}
void init(Abel val) {
data.resize(range << 1);
fill(begin(data) + range,end(data),val);
for(int idx = range - 1; idx; idx--) data[idx] = opr(data[idx * 2],data[idx * 2 + 1]);
}
void init(vector<Abel> arr) {
data.resize(range << 1);
for(int i = 0; i < range; i++) data[i + range] = arr[i];
for(int idx = range - 1; idx; idx--) data[idx] = opr(data[idx * 2],data[idx * 2 + 1]);
}
void update(int idx, Abel val) {
data[idx += range] = val;
while(idx >>= 1) data[idx] = opr(data[idx * 2],data[idx * 2 + 1]);
}
void add(int idx, Abel diff = 1) { update(idx,data[idx + range] + diff); }
// for the interval [l,r)
Abel query(int l, int r) {
l += range;
r += range;
Abel ret = idel;
while(l < r) {
if(l & 1) ret = opr(ret,data[l++]);
if(r & 1) ret = opr(ret,data[--r]);
l >>= 1, r >>= 1;
}
return ret;
}
};
auto modplus = [](ll a,ll b){
return ((a % mod) + (b % mod)) % mod;
};
ll N,A,B;
ll S[100001];
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
cin >> N >> A >> B;
if(A > B) swap(A,B);
rep(i,N) cin >> S[i + 1];
S[0] = -inf32;
Segtree<ll> sgt(N,0,modplus,0);
sgt.add(0);
int bnd = 0;
urep(i,1,N){
int u = u_bnd(S,S + N,S[i] - B) - S;
if(u > bnd) sgt.add(i,sgt.query(bnd,u));
if(S[i] - S[i - 1] < A){
if(i > 1 && S[i] - S[i - 2] < A){
bnd = i;
}else{
bnd = i - 1;
}
}
}
esc(sgt.query(bnd,N + 1));
}
Submission Info
Submission Time |
|
Task |
C - Division into Two |
User |
jell |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
4668 Byte |
Status |
WA |
Exec Time |
46 ms |
Memory |
3072 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 |
AC |
39 ms |
3072 KB |
02.txt |
WA |
40 ms |
3072 KB |
03.txt |
WA |
38 ms |
3072 KB |
04.txt |
WA |
38 ms |
3072 KB |
05.txt |
AC |
45 ms |
3072 KB |
06.txt |
WA |
38 ms |
3072 KB |
07.txt |
AC |
39 ms |
3072 KB |
08.txt |
AC |
40 ms |
3072 KB |
09.txt |
WA |
39 ms |
3072 KB |
10.txt |
WA |
39 ms |
3072 KB |
11.txt |
WA |
38 ms |
3072 KB |
12.txt |
AC |
46 ms |
3072 KB |
13.txt |
AC |
42 ms |
3072 KB |
14.txt |
WA |
38 ms |
3072 KB |
15.txt |
WA |
38 ms |
3072 KB |
16.txt |
AC |
28 ms |
3072 KB |
17.txt |
WA |
14 ms |
3072 KB |
18.txt |
WA |
16 ms |
3072 KB |
19.txt |
AC |
25 ms |
3072 KB |
20.txt |
AC |
30 ms |
3072 KB |
21.txt |
AC |
34 ms |
3072 KB |
22.txt |
WA |
26 ms |
3072 KB |
23.txt |
AC |
28 ms |
3072 KB |
24.txt |
AC |
28 ms |
3072 KB |
25.txt |
AC |
37 ms |
3072 KB |
26.txt |
AC |
37 ms |
3072 KB |
27.txt |
AC |
35 ms |
3072 KB |
28.txt |
AC |
32 ms |
3072 KB |
29.txt |
AC |
30 ms |
3072 KB |
30.txt |
AC |
30 ms |
3072 KB |
31.txt |
AC |
27 ms |
3072 KB |
32.txt |
AC |
27 ms |
3072 KB |
33.txt |
WA |
27 ms |
3072 KB |
34.txt |
AC |
25 ms |
3072 KB |
35.txt |
WA |
27 ms |
3072 KB |
36.txt |
AC |
39 ms |
3072 KB |
37.txt |
AC |
39 ms |
3072 KB |
38.txt |
AC |
38 ms |
3072 KB |
39.txt |
WA |
45 ms |
3072 KB |
40.txt |
AC |
32 ms |
3072 KB |
41.txt |
AC |
22 ms |
3072 KB |
42.txt |
AC |
12 ms |
3072 KB |
43.txt |
AC |
45 ms |
3072 KB |
44.txt |
AC |
45 ms |
3072 KB |
45.txt |
AC |
46 ms |
3072 KB |
46.txt |
AC |
45 ms |
3072 KB |
47.txt |
AC |
45 ms |
3072 KB |
48.txt |
AC |
41 ms |
3072 KB |
49.txt |
WA |
1 ms |
256 KB |
50.txt |
WA |
1 ms |
256 KB |
51.txt |
WA |
1 ms |
256 KB |
52.txt |
AC |
1 ms |
256 KB |
53.txt |
WA |
1 ms |
256 KB |
54.txt |
AC |
1 ms |
256 KB |
55.txt |
AC |
1 ms |
256 KB |
56.txt |
AC |
1 ms |
256 KB |
57.txt |
AC |
1 ms |
256 KB |
58.txt |
AC |
1 ms |
256 KB |
59.txt |
AC |
1 ms |
256 KB |
60.txt |
AC |
1 ms |
256 KB |
61.txt |
AC |
1 ms |
256 KB |
62.txt |
AC |
1 ms |
256 KB |
63.txt |
AC |
1 ms |
256 KB |
64.txt |
AC |
1 ms |
256 KB |
s1.txt |
AC |
1 ms |
256 KB |
s2.txt |
AC |
1 ms |
256 KB |
s3.txt |
AC |
1 ms |
256 KB |
s4.txt |
AC |
1 ms |
256 KB |