Submission #4075380
Source Code Expand
#include<stdio.h> #include<iostream> #include<vector> #include<algorithm> #include<string> #include<string.h> using namespace std; typedef long long LL; typedef vector<int> VI; #define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i) #define EACH(i,c) for(__typeof((c).begin()) i=(c).begin(),i##_end=(c).end();i!=i##_end;++i) #define eprintf(...) fprintf(stderr, __VA_ARGS__) template<class T> inline void amin(T &x, const T &y) { if (y<x) x=y; } template<class T> inline void amax(T &x, const T &y) { if (x<y) x=y; } template<class Iter> void rprintf(const char *fmt, Iter begin, Iter end) { for (bool sp=0; begin!=end; ++begin) { if (sp) putchar(' '); else sp = true; printf(fmt, *begin); } putchar('\n'); } template<unsigned MOD> struct ModInt { static const unsigned static_MOD = MOD; unsigned x; void undef() { x = (unsigned)-1; } bool isnan() const { return x == (unsigned)-1; } inline int geti() const { return (int)x; } ModInt() { x = 0; } ModInt(const ModInt &y) { x = y.x; } ModInt(int y) { if (y<0 || (int)MOD<=y) y %= (int)MOD; if (y<0) y += MOD; x=y; } ModInt(unsigned y) { if (MOD<=y) x = y % MOD; else x = y; } ModInt(long long y) { if (y<0 || MOD<=y) y %= MOD; if (y<0) y += MOD; x=y; } ModInt(unsigned long long y) { if (MOD<=y) x = y % MOD; else x = y; } ModInt &operator+=(const ModInt y) { if ((x += y.x) >= MOD) x -= MOD; return *this; } ModInt &operator-=(const ModInt y) { if ((x -= y.x) & (1u<<31)) x += MOD; return *this; } ModInt &operator*=(const ModInt y) { x = (unsigned long long)x * y.x % MOD; return *this; } ModInt &operator/=(const ModInt y) { x = (unsigned long long)x * y.inv().x % MOD; return *this; } ModInt operator-() const { return (x ? MOD-x: 0); } ModInt inv() const { unsigned a = MOD, b = x; int u = 0, v = 1; while (b) { int t = a / b; a -= t * b; swap(a, b); u -= t * v; swap(u, v); } if (u < 0) u += MOD; return ModInt(u); } ModInt pow(long long y) const { ModInt b = *this, r = 1; if (y < 0) { b = b.inv(); y = -y; } for (; y; y>>=1) { if (y&1) r *= b; b *= b; } return r; } friend ModInt operator+(ModInt x, const ModInt y) { return x += y; } friend ModInt operator-(ModInt x, const ModInt y) { return x -= y; } friend ModInt operator*(ModInt x, const ModInt y) { return x *= y; } friend ModInt operator/(ModInt x, const ModInt y) { return x *= y.inv(); } friend bool operator<(const ModInt x, const ModInt y) { return x.x < y.x; } friend bool operator==(const ModInt x, const ModInt y) { return x.x == y.x; } friend bool operator!=(const ModInt x, const ModInt y) { return x.x != y.x; } }; const LL MOD = 1000000007; typedef ModInt<MOD> Mint; template<class T> struct Fenwick { int n; T* d; Fenwick() : n(0), d(NULL) {} Fenwick(int n_) : n(n_) { d = new T[n_](); } Fenwick(const Fenwick &y) : n(y.n) { d = new T[n]; memcpy(d, y.d, sizeof (T) * n); } ~Fenwick() { delete[] d; d = NULL; n = 0; } friend void swap(Fenwick &x, Fenwick &y) { swap(x.n, y.n); swap(x.d, y.d); } Fenwick& operator=(Fenwick y) { swap(*this, y); return *this; } inline void add(int i, const T &x) { for (; i<n; i|=i+1) d[i] += x; } inline T sum(int r) { T s = T(); for (; r; r&=r-1) s += d[r-1]; return s; } T sum(int l, int r) { return sum(r) - sum(l); } }; int N; LL A, B; LL S[100011]; int sums[100011]; void MAIN() { scanf("%d%lld%lld", &N, &A, &B); if (A > B) swap(A, B); REP (i, N) scanf("%lld", S+i); REP (i, N-2) if (S[i+2] - S[i] < A) { puts("0"); return; } REP (i, N-1) sums[i+1] = sums[i] + (S[i+1] - S[i] < A? 1: 0); Mint ans = 0; int left = 0; int p = 0; Fenwick<Mint> X(N+2); REP (i, N) { while (S[i] - S[left] >= B) left++; if (i>=2 && S[i-1] - S[i-2] < A) p = i-1; int L = max(0, p-1); int R = min(i+1, left); Mint tmp = 0; if (L < R) { tmp = X.sum(L, R); } if (p == 0) tmp += 1; X.add(i, tmp); if (N-2 <= i || sums[N-1] == sums[i+1]) { ans += tmp; } } if (sums[N-1] == 0) ans += 1; printf("%d\n", ans.geti()); } int main() { int TC = 1; // scanf("%d", &TC); REP (tc, TC) MAIN(); return 0; }
Submission Info
Submission Time | |
---|---|
Task | C - Division into Two |
User | natsugiri |
Language | C++14 (GCC 5.4.1) |
Score | 1100 |
Code Size | 4435 Byte |
Status | AC |
Exec Time | 25 ms |
Memory | 1792 KB |
Compile Error
./Main.cpp: In function ‘void MAIN()’: ./Main.cpp:112:36: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d%lld%lld", &N, &A, &B); ^ ./Main.cpp:114:34: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] REP (i, N) scanf("%lld", S+i); ^
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 | 25 ms | 1792 KB |
02.txt | AC | 24 ms | 1792 KB |
03.txt | AC | 24 ms | 1792 KB |
04.txt | AC | 23 ms | 1792 KB |
05.txt | AC | 22 ms | 1792 KB |
06.txt | AC | 22 ms | 1792 KB |
07.txt | AC | 24 ms | 1792 KB |
08.txt | AC | 24 ms | 1792 KB |
09.txt | AC | 25 ms | 1792 KB |
10.txt | AC | 24 ms | 1792 KB |
11.txt | AC | 22 ms | 1792 KB |
12.txt | AC | 23 ms | 1792 KB |
13.txt | AC | 24 ms | 1792 KB |
14.txt | AC | 24 ms | 1792 KB |
15.txt | AC | 23 ms | 1792 KB |
16.txt | AC | 13 ms | 1792 KB |
17.txt | AC | 15 ms | 1792 KB |
18.txt | AC | 17 ms | 1792 KB |
19.txt | AC | 17 ms | 1792 KB |
20.txt | AC | 19 ms | 1792 KB |
21.txt | AC | 20 ms | 1792 KB |
22.txt | AC | 17 ms | 1792 KB |
23.txt | AC | 16 ms | 1792 KB |
24.txt | AC | 18 ms | 1792 KB |
25.txt | AC | 23 ms | 1792 KB |
26.txt | AC | 22 ms | 1792 KB |
27.txt | AC | 22 ms | 1792 KB |
28.txt | AC | 21 ms | 1792 KB |
29.txt | AC | 20 ms | 1792 KB |
30.txt | AC | 20 ms | 1792 KB |
31.txt | AC | 19 ms | 1792 KB |
32.txt | AC | 19 ms | 1792 KB |
33.txt | AC | 20 ms | 1792 KB |
34.txt | AC | 16 ms | 1792 KB |
35.txt | AC | 19 ms | 1792 KB |
36.txt | AC | 16 ms | 1792 KB |
37.txt | AC | 17 ms | 1792 KB |
38.txt | AC | 16 ms | 1792 KB |
39.txt | AC | 24 ms | 1792 KB |
40.txt | AC | 15 ms | 1792 KB |
41.txt | AC | 15 ms | 1792 KB |
42.txt | AC | 11 ms | 1024 KB |
43.txt | AC | 23 ms | 1792 KB |
44.txt | AC | 23 ms | 1792 KB |
45.txt | AC | 23 ms | 1792 KB |
46.txt | AC | 23 ms | 1792 KB |
47.txt | AC | 18 ms | 1024 KB |
48.txt | AC | 18 ms | 1024 KB |
49.txt | AC | 1 ms | 256 KB |
50.txt | AC | 1 ms | 256 KB |
51.txt | AC | 1 ms | 256 KB |
52.txt | AC | 1 ms | 256 KB |
53.txt | AC | 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 |