oj.uz

Submission #963162

# Submission time Handle Problem Language Result Execution time Memory
963162 2024-04-14T15:57:33 Z vjudge1 Fibonacci representations (CEOI18_fib) C++14
50 / 100
 4000 ms 7292 KB 
#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];
   }
} st;

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

int32_t main(){
   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;
   for (int i=1; i<=n; ++i){
      auto get=[&](int x) -> pair<int, int> {
         auto it=mp.lower_bound(x);
         return {it==mp.begin()?0:prev(it)->first, it==mp.end()?0:it->first};
      };
      if (!mp.count(a[i])) v[i].push_back({{a[i], 0}, get(a[i])});
      ++mp[a[i]];
      for (auto it=mp.begin(); it!=mp.end();){
         if (it!=mp.begin() && prev(it)->first+1==it->first){
            int x=it->first;
            int d=min(prev(it)->second, it->second);
            if (!mp.count(x+1)) v[i].push_back({{x+1, 0}, get(x+1)});
            mp[x+1]+=d;
            prev(it)->second-=d;
            if (prev(it)->second==0) mp.erase(prev(it)), v[i].push_back({{x-1, 1}, get(x-1)});
            it->second-=d;
            if (it->second==0) it=mp.erase(it), v[i].push_back({{x, 1}, get(x)});
            while (it!=mp.begin() && prev(it)->first>=x-1) --it;
         }else if (it->second>=2){
            int x=it->first;
            int d=it->second/2;
            if (x==1){
               if (it->second==2){
                  if (!mp.count(2)) v[i].push_back({{2, 0}, get(2)});
                  ++mp[2];
                  it=mp.erase(it);
                  v[i].push_back({{1, 1}, get(1)});
               }else{
                  if (!mp.count(3)) v[i].push_back({{3, 0}, get(3)});
                  mp[3]+=it->second/3;
                  it->second%=3;
                  if (it->second==0) it=mp.erase(it), v[i].push_back({{1, 1}, get(1)});
                  else ++it;
               }
            }else if (x==2){
               int sum=it->second*2;
               if (!mp.count(3)) v[i].push_back({{3, 0}, get(3)});
               mp[3]+=sum/3;
               if (sum%3){
                  if (!mp.count(1)) v[i].push_back({{1, 0}, get(1)});
                  mp[1]+=sum%3;
               }
               mp.erase(it);
               v[i].push_back({{2, 1}, get(2)});
               it=mp.begin();
            }else{
               if (!mp.count(x-2)) v[i].push_back({{x-2, 0}, get(x-2)});
               mp[x-2]+=d;
               if (!mp.count(x+1)) v[i].push_back({{x+1, 0}, get(x+1)});
               mp[x+1]+=d;
               it->second-=d*2;
               if (it->second==0){
                  it=mp.erase(it);
                  v[i].push_back({{x, 1}, get(x)});;
               }
               while (it!=mp.begin() && prev(it)->first>=x-2) --it;
            }
         }else ++it;
      }
   }
   vector<int> vals{-1};
   for (int i=1; i<=n; ++i) for (auto &j:v[i]) vals.push_back(j.first.first);
   sort(vals.begin(), vals.end());
   vals.resize(unique(vals.begin(), vals.end())-vals.begin()+1);
   st.init((int)vals.size()-1);
   auto get_pos=[&](int x) -> int {
      return lower_bound(vals.begin(), vals.end(), x)-vals.begin();
   };
   for (int i=1; i<=n; ++i){
      for (auto &j:v[i]){
         if (j.first.second==0){
            int x=j.first.first, l=j.second.first, r=j.second.second;
            {
               int pos=get_pos(x);
               Matrix d;
               d[0][0]=(x-l+1)/2; d[0][1]=d[0][0]-1; d[1][0]=d[1][1]=(x&1)==(l&1);
               st.update(1, 1, st.n, pos, d);
            }
            if (r){
               int nxt=get_pos(r);
               Matrix d;
               d[0][0]=(r-x+1)/2; d[0][1]=d[0][0]-1; d[1][0]=d[1][1]=(x&1)==(r&1);
               st.update(1, 1, st.n, nxt, d);
            }
         }else{
            int x=j.first.first, l=j.second.first, r=j.second.second;
            {
               int pos=get_pos(x);
               st.update(1, 1, st.n, pos, Matrix(1));
            }
            if (r){
               int nxt=get_pos(r);
               Matrix d;
               d[0][0]=(r-l+1)/2; d[0][1]=d[0][0]-1; d[1][0]=d[1][1]=(l&1)==(r&1);
               st.update(1, 1, st.n, nxt, d);
            }
         }
      }
      cout << st.get() << '\n';
   }
   return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4696 KB Output is correct
2 Correct 2 ms 4700 KB Output is correct
3 Correct 1 ms 4700 KB Output is correct
4 Correct 1 ms 4700 KB Output is correct
5 Correct 2 ms 4700 KB Output is correct
6 Correct 1 ms 4700 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4696 KB Output is correct
2 Correct 2 ms 4700 KB Output is correct
3 Correct 1 ms 4700 KB Output is correct
4 Correct 1 ms 4700 KB Output is correct
5 Correct 2 ms 4700 KB Output is correct
6 Correct 1 ms 4700 KB Output is correct
7 Correct 1 ms 4700 KB Output is correct
8 Correct 2 ms 4704 KB Output is correct
9 Correct 1 ms 4700 KB Output is correct
10 Correct 2 ms 4700 KB Output is correct
11 Correct 2 ms 4700 KB Output is correct
12 Correct 1 ms 4700 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4696 KB Output is correct
2 Correct 2 ms 4700 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4696 KB Output is correct
2 Correct 2 ms 4700 KB Output is correct
3 Correct 1 ms 4700 KB Output is correct
4 Correct 1 ms 4700 KB Output is correct
5 Correct 2 ms 4700 KB Output is correct
6 Correct 1 ms 4700 KB Output is correct
7 Correct 1 ms 4700 KB Output is correct
8 Correct 2 ms 4704 KB Output is correct
9 Correct 1 ms 4700 KB Output is correct
10 Correct 2 ms 4700 KB Output is correct
11 Correct 2 ms 4700 KB Output is correct
12 Correct 1 ms 4700 KB Output is correct
13 Correct 1 ms 4696 KB Output is correct
14 Correct 2 ms 4700 KB Output is correct
15 Correct 2 ms 4700 KB Output is correct
16 Correct 1 ms 4700 KB Output is correct
17 Correct 2 ms 4700 KB Output is correct
18 Correct 1 ms 4700 KB Output is correct
19 Correct 1 ms 4700 KB Output is correct
20 Correct 3 ms 4956 KB Output is correct
21 Correct 2 ms 4700 KB Output is correct
22 Correct 2 ms 4700 KB Output is correct
23 Correct 2 ms 4700 KB Output is correct

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4700 KB Output is correct
2 Execution timed out 4025 ms 7292 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4696 KB Output is correct
2 Correct 2 ms 4700 KB Output is correct
3 Correct 1 ms 4700 KB Output is correct
4 Correct 1 ms 4700 KB Output is correct
5 Correct 2 ms 4700 KB Output is correct
6 Correct 1 ms 4700 KB Output is correct
7 Correct 1 ms 4700 KB Output is correct
8 Correct 2 ms 4704 KB Output is correct
9 Correct 1 ms 4700 KB Output is correct
10 Correct 2 ms 4700 KB Output is correct
11 Correct 2 ms 4700 KB Output is correct
12 Correct 1 ms 4700 KB Output is correct
13 Correct 1 ms 4696 KB Output is correct
14 Correct 2 ms 4700 KB Output is correct
15 Correct 2 ms 4700 KB Output is correct
16 Correct 1 ms 4700 KB Output is correct
17 Correct 2 ms 4700 KB Output is correct
18 Correct 1 ms 4700 KB Output is correct
19 Correct 1 ms 4700 KB Output is correct
20 Correct 3 ms 4956 KB Output is correct
21 Correct 2 ms 4700 KB Output is correct
22 Correct 2 ms 4700 KB Output is correct
23 Correct 2 ms 4700 KB Output is correct
24 Correct 1 ms 4700 KB Output is correct
25 Execution timed out 4025 ms 7292 KB Time limit exceeded
26 Halted 0 ms 0 KB -