fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3.     using namespace std;
  4.  
  5.     const int MAX_N = 1000005;
  6.  
  7.     struct FenwickTree {
  8.         int treeSize;
  9.         vector<int> nodes;
  10.  
  11.         void init(int treeSize) {
  12.             this->treeSize = treeSize;
  13.             nodes.assign(treeSize + 1, 0);
  14.         }
  15.  
  16.         void update(int id, int val) {
  17.             for (++id; id <= treeSize; id += (id & -id)) {
  18.                 nodes[id] = max(nodes[id], val);
  19.             }
  20.         }
  21.  
  22.         int get(int id) {
  23.             int result = 0;
  24.             for (++id; id >= 1; id -= (id & -id)) {
  25.                 result = max(result, nodes[id]);
  26.             }
  27.             return result;
  28.         }
  29.     };
  30.  
  31.     int n, mod;
  32.     int fibonacci[MAX_N];
  33.     FenwickTree fenwickTree;
  34.  
  35.     int main() {
  36.         ios::sync_with_stdio(false);
  37.         cin.tie(0);
  38.         cout.tie(0);
  39.  
  40.         freopen("LISFIBO.inp", "r", stdin);
  41.         freopen("LISFIBO.out", "w", stdout);
  42.  
  43.         cin >> n >> mod;
  44.  
  45.         fibonacci[1] = fibonacci[2] = 1;
  46.         for (int i = 3; i <= n; ++i) {
  47.             fibonacci[i] = (fibonacci[i - 2] + fibonacci[i - 1]) % mod;
  48.         }
  49.  
  50.         fenwickTree.init(mod + 1);
  51.         for (int i = 1; i <= n; ++i) {
  52.             fenwickTree.update(fibonacci[i], fenwickTree.get(fibonacci[i]) + 1);
  53.         }
  54.  
  55.         cout << fenwickTree.get(mod) << '\n';
  56.  
  57.         return 0;
  58.     }
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/TFDTlD
language:
C++14 (gcc 8.3)
created:
5 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!