#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> v;
typedef pair<int,int> P;
set<P> s;
int val[100000];
set<P> del;
vector<long long> vec;
const int mod=1e9+7;
long long dp[105][2];
void insert(P x) {
val[x.second]=x.first;
auto it2=s.lower_bound(x);
auto it1=prev(it2);
long long d=(*it2).first-(*it1).first;
del.erase(P(d,(*it1).second));
d=x.first-(*it1).first;
del.insert(P(d,(*it1).second));
d=(*it2).first-x.first;
del.insert(P(d,x.second));
s.insert(x);
}
void erase(P x) {
auto it=s.lower_bound(x);
P v1=*prev(it);
P v2=*next(it);
long long d=x.first-v1.first;
del.erase(P(d,v1.second));
d=v2.first-x.first;
del.erase(P(d,x.second));
d=v2.first-v1.first;
del.erase(P(d,v1.second));
s.erase(it);
}
long long ans(int ind,int type) {
if (ind==0) {
if (type==0) {
return (vec[0]+1)/2;
}
return (vec[0]-1)/2;
}
if (dp[ind][type]!=-1) {
return dp[ind][type];
}
if (type==1) {
return dp[ind][type]=(ans(ind,0)-ans(ind-1,0)+mod)%mod;
}
long long d=vec[ind]-vec[ind-1];
if (d%2==0) {
return dp[ind][type]=((d/2)*ans(ind-1,0)+ans(ind-1,1))%mod;
}
return dp[ind][type]=((d/2+1)*ans(ind-1,0))%mod;
}
int main(void) {
scanf("%d",&n);
for(int ind=0;ind<n;ind++) {
int x;
scanf("%d",&x);
v.push_back(x);
s.clear();
for(int i=0;i<v.size();i++) {
s.insert(P(v[i],i));
val[i]=v[i];
}
s.insert(P(2e9+7,-1));
s.insert(P(-10,-1));
for(auto iter=s.begin();iter!=s.end();iter++) {
if (iter!=s.begin()) {
P now=(*iter);
P pr=(*prev(iter));
del.insert(P(now.first-pr.first,pr.second));
}
}
while (1) {
P got=(*del.begin());
if (got.first>1) {
break;
}
if (got.first==0) {
auto it=s.lower_bound(P(val[got.second],got.second));
P one=(*it);
it=next(it);
P two=(*it);
erase(one);
erase(two);
if (one.first==1) {
val[one.second]=2;
val[two.second]=0;
insert(P(2,one.second));
}
else if (one.first==2) {
val[one.second]=3;
val[two.second]=1;
insert(P(3,one.second));
insert(P(1,one.second));
}
else {
val[one.second]=one.first+1;
val[two.second]=two.first-2;
insert(P(one.first+1,one.second));
insert(P(two.first-2,two.second));
}
}
else {
auto it=s.lower_bound(P(val[got.second],got.second));
P one=(*it);
it=next(it);
P two=(*it);
erase(one);
erase(two);
val[one.second]=one.first+2;
val[two.second]=0;
insert(P(one.first+2,one.second));
}
}
s.erase(P(2e9+7,-1));
s.erase(P(-10,-1));
vec.clear();
for(auto now:s) {
vec.push_back(now.first);
}
sort(vec.begin(),vec.end());
memset(dp,-1,sizeof(dp));
printf("%lld\n",ans(vec.size()-1,0));
}
}
Compilation message
fib.cpp: In function 'int main()':
fib.cpp:67:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
67 | for(int i=0;i<v.size();i++) {
| ~^~~~~~~~~
fib.cpp:61:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
61 | scanf("%d",&n);
| ~~~~~^~~~~~~~~
fib.cpp:64:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
64 | scanf("%d",&x);
| ~~~~~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
