#include <bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
#define FOR(i, l, r, d) for(int i=(l); i<=(r); i+=(d))
#define szof(x) ((int)(x).size())
#define vi vector<int>
#define pii pair<int, int>
#define F first
#define S second
#define pb push_back
#define eb emplace_back
#define mkp make_pair
const int INF = 2147483647;
const int LNF = INF*INF;
const int MOD = 1000000007;
const int mod = 998244353;
const int MAX = 110;
int n;
int id[MAX];
set<int> ids;
struct Treap{
Treap *l, *r;
int key, pri;
pair<pii, pii> mat;
pair<pii, pii> prod;
Treap(int _k, pair<pii, pii> _mat): l(nullptr), r(nullptr), key(_k), pri(rand()), mat(_mat), prod(_mat) {}
};
pair<pii, pii> mult(pair<pii, pii> A, pair<pii, pii> B){
pair<pii, pii> ret;
ret.F.F = (A.F.F * B.F.F + A.F.S * B.S.F) % MOD;
ret.F.S = (A.F.F * B.F.S + A.F.S * B.S.S) % MOD;
ret.S.F = (A.S.F * B.F.F + A.S.S * B.S.F) % MOD;
ret.S.S = (A.S.F * B.F.S + A.S.S * B.S.S) % MOD;
return ret;
}
inline pair<pii, pii> get_mat(Treap *T){
return (T != nullptr) ? T->mat : mkp(mkp((int)1, (int)0), mkp((int)0, (int)1));
}
inline pair<pii, pii> get_prod(Treap *T){
return (T != nullptr) ? T->prod : mkp(mkp((int)1, (int)0), mkp((int)0, (int)1));
}
void pull(Treap *&T){
if(T==nullptr) return;
T->prod = mult(mult(get_prod(T->l), T->mat), get_prod(T->r));
}
Treap* Merge(Treap *a, Treap *b){
if(a == nullptr) return b;
if(b == nullptr) return a;
if(a->pri < b->pri){
a->r = Merge(a->r, b);
pull(a);
return a;
}
else{
b->l = Merge(a, b->l);
pull(b);
return b;
}
}
void Split(Treap *T, Treap *&a, Treap *&b, int k){
if(T == nullptr){
a = b = nullptr;
return;
}
if(T->key < k){
a = T;
Split(T->r, a->r, b, k);
pull(a);
}
else{
b = T;
Split(T->l, a, b->l, k);
pull(b);
}
}
void Insert(Treap *&T, int k, pair<pii, pii> mat){
/*
cerr<<"insert : "<<endl;
cerr<<mat.F.F<<" "<<mat.F.S<<endl<<mat.S.F<<" "<<mat.S.S<<endl;
cerr<<endl;
*/
Treap *a, *b;
Split(T, a, b, k);
T = Merge( Merge(a, new Treap(k, mat)), b );
}
void Erase(Treap *&T, int k){
Treap *a, *b, *c;
Split(T, a, b, k);
Split(b, b, c, k+1);
T = Merge(a, c);
}
Treap *treap;
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n;
FOR(i, 0, n-1, 1){
cin>>id[i];
id[i] *= -1;
}
ids.insert(0);
Insert(treap, 0, mkp(mkp(1, 0), mkp(0, 1)));
FOR(i, 0, n-1, 1){
ids.insert(id[i]);
auto it = ids.find(id[i]);
auto nx = next(it);
int dn = *nx - id[i];
pair<pii, pii> mat_n = mkp(mkp(1, 1), mkp(dn/2 - 1, dn/2));
if(it != ids.begin()){
auto pv = prev(it);
int dp = id[i] - *pv;
pair<pii, pii> mat_p = mkp(mkp(1, 1), mkp(dp/2 - 1, dp/2));
Erase(treap, *pv);
Insert(treap, *pv, mat_p);
Insert(treap, id[i], mat_n);
}
else{
Insert(treap, id[i], mat_n);
}
/*
cerr<<"dp : "<<endl;
cerr<<treap->prod.F.F<<" "<<treap->prod.F.S<<endl<<treap->prod.S.F<<" "<<treap->prod.S.S<<endl;
cerr<<endl;
*/
int res = (treap->prod.F.F + treap->prod.S.F) % MOD;
cout<<res<<" ";
}
cout<<'\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
