Submission #964328

#	Time	Username	Problem	Language	Result	Execution time	Memory
964328		vjudge1	Fibonacci representations (CEOI18_fib)	C++14	100 / 100	646 ms	32444 KiB

fib

#include<bits/stdc++.h>

using namespace std;

#define int long long

const int mod=1e9+7;

struct Matrix{
   int data[2][2];
   Matrix (int x=0){
      for (int i=0; i<2; ++i) for (int j=0; j<2; ++j) data[i][j]=(i==j)&x;
   }
   auto & operator[](int x){ return data[x]; }
   const auto & operator[](int x) const { return data[x]; }
   Matrix operator*(const Matrix &b){
      Matrix c;
      for (int i=0; i<2; ++i) for (int k=0; k<2; ++k) for (int j=0; j<2; ++j){
         c[i][j]=(c[i][j]+data[i][k]*b[k][j])%mod;
      }
      return c;
   }
   Matrix pow(int y){
      Matrix x=*this, t(1);
      while (y){
         if (y&1) t=t*x;
         x=x*x;
         y>>=1;
      }
      return t;
   }
};

struct SegmentTree{
   int n;
   vector<Matrix> t;
   void init(int _n){
      n=_n;
      t.assign(4*n+1, Matrix(1));
   }
   void update(int k, int l, int r, int pos, const Matrix &val){
      if (l==r){
         t[k]=val;
         return;
      }
      int mid=(l+r)>>1;
      if (pos<=mid) update(k<<1, l, mid, pos, val);
      else update(k<<1|1, mid+1, r, pos, val);
      t[k]=t[k<<1]*t[k<<1|1];
   }
   int get(){
      return t[1][0][0];
   }
} seg;

const int N=1e5+10;
int n, a[N], f[N][2];
vector<pair<int, int>> v[N];

int32_t main(){
   // freopen("fib.inp", "r", stdin);
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   cin >> n;
   for (int i=1; i<=n; ++i) cin >> a[i];
   map<int, int> mp;
   set<pair<int, int>> st;
   for (int i=1; i<=n; ++i){
      auto it=st.lower_bound(make_pair(a[i], 2e9));
      if (it!=st.begin()){
         --it;
         int l=it->first, r=it->second;
         if (l<=a[i] && a[i]<=r){
            if ((l&1)==(a[i]&1)){
               st.erase(it), v[i].emplace_back(l, -1);
               if (a[i]!=r) st.emplace(a[i]+2, r), v[i].emplace_back(a[i]+2, r);
               if (l==1){
                  st.emplace(2, a[i]+1), v[i].emplace_back(2, a[i]+1);
               }else if (l==2){
                  st.emplace(1, a[i]+1), v[i].emplace_back(1, a[i]+1);
               }else{
                  st.emplace(l+1, a[i]+1), v[i].emplace_back(l+1, a[i]+1);
                  st.emplace(l-2, l-2), v[i].emplace_back(l-2, l-2);
               }
            }else{
               st.erase(it), v[i].emplace_back(l, -1);
               if (l<=a[i]-1) st.emplace(l, a[i]-1), v[i].emplace_back(l, a[i]-1);
               if (a[i]+1<=r) st.emplace(a[i]+1, r), v[i].emplace_back(a[i]+1, r);
               st.emplace(a[i], a[i]), v[i].emplace_back(a[i], a[i]);
            }
         }else st.emplace(a[i], a[i]), v[i].emplace_back(a[i], a[i]);
      }else st.emplace(a[i], a[i]), v[i].emplace_back(a[i], a[i]);
      it=st.lower_bound(make_pair(a[i], 2e9));
      if (it!=st.begin()) --it;
      if (it!=st.begin()) --it;
      if (it!=st.begin()) --it;
      for (int _=0; _<5; ++_){
         if (it==st.end() || next(it)==st.end()) break;
         int l1=it->first, r1=it->second, l2=next(it)->first, r2=next(it)->second;
         if (r1+1==l2){
            if (l2==r2){
               if (next(next(it))!=st.end() && next(next(it))->first==r2+1){
                  ++it;
                  continue;
               }
            }
            v[i].emplace_back(l2, -1);
            st.erase(next(it));
            v[i].emplace_back(l1, -1);
            st.erase(it);
            if (l1!=r1) st.emplace(l1, r1-2), v[i].emplace_back(l1, r1-2);
            it=st.emplace(r2+1, r2+1).first, v[i].emplace_back(r2+1, r2+1);
         }else ++it;
      }
      it=st.lower_bound(make_pair(a[i], 2e9));
      if (it!=st.begin()) --it;
      if (it!=st.begin()) --it;
      if (it!=st.begin()) --it;
      for (int _=0; _<5; ++_){
         if (it==st.end() || next(it)==st.end()) break;
         int l1=it->first, r1=it->second, l2=next(it)->first, r2=next(it)->second;
         if (r1+2==l2){
            v[i].emplace_back(l2, -1);
            st.erase(next(it));
            v[i].emplace_back(l1, -1);
            st.erase(it);
            it=st.emplace(l1, r2).first, v[i].emplace_back(l1, r2);
         }else ++it;
      }
   }
   // for (int i=1; i<=n; ++i){
   //    for (int j=0; j<(int)v[i].size(); ++j){
   //       if (v[i][j].second==-1){
   //          for (int k=0; k<j; ++k) if (v[i][k].first==v[i][j].first){
   //             v[i].erase(v[i].begin()+k);
   //             --j;
   //             break;
   //          }
   //       }
   //    }
   // }
   vector<int> vals{-1};
   for (int i=1; i<=n; ++i) for (auto &j:v[i]) vals.push_back(j.first);
   sort(vals.begin(), vals.end());
   vals.resize(unique(vals.begin(), vals.end())-vals.begin());
   seg.init((int)vals.size()-1);
   auto get_pos=[&](int x) -> int {
      return lower_bound(vals.begin(), vals.end(), x)-vals.begin();
   };
   st.clear();
   for (int i=1; i<=n; ++i){
      for (auto &j:v[i]){
         if (j.second==-1){
            auto it=st.lower_bound({j.first, 0});
            {
               int pos=get_pos(j.first);
               seg.update(1, 1, seg.n, pos, Matrix(1));
            }
            it=st.erase(it);
            if (it!=st.end()){
               int pos=get_pos(it->first);
               Matrix d;
               int l=it==st.begin()?0:prev(it)->second;
               int r=it->first;
               d[0][0]=(r-l+1)/2; d[0][1]=d[0][0]-1; d[1][0]=d[1][1]=(l&1)==(r&1);
               Matrix d2(1);
               d2[1][0]=(it->second-it->first)/2;
               seg.update(1, 1, seg.n, pos, d*d2);
            }
         }else{
            auto it=st.insert(j).first;
            {
               int pos=get_pos(j.first);
               Matrix d;
               int l=it==st.begin()?0:prev(it)->second;
               int r=it->first;
               d[0][0]=(r-l+1)/2; d[0][1]=d[0][0]-1; d[1][0]=d[1][1]=(l&1)==(r&1);
               Matrix d2(1);
               d2[1][0]=(it->second-it->first)/2;
               seg.update(1, 1, seg.n, pos, d*d2);
            }
            ++it;
            if (it!=st.end()){
               int pos=get_pos(it->first);
               Matrix d;
               int l=it==st.begin()?0:prev(it)->second;
               int r=it->first;
               d[0][0]=(r-l+1)/2; d[0][1]=d[0][0]-1; d[1][0]=d[1][1]=(l&1)==(r&1);
               Matrix d2(1);
               d2[1][0]=(it->second-it->first)/2;
               seg.update(1, 1, seg.n, pos, d*d2);
            }
         }
      }
      cout << seg.get() << '\n';
   }
   return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 20 / 20
• Subtask 3: 15 / 15
• Subtask 4: 10 / 10
• Subtask 5: 15 / 15
• Subtask 6: 35 / 35