fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define ll long long
  3. #define ull unsigned ll
  4. #define ld long double
  5. #define pb push_back
  6. // #define int long long
  7. #define f first
  8. #define s second
  9. #define pq priority_queue
  10. #define fast ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
  11. #define read_file freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
  12.  
  13. using namespace std;
  14.  
  15. // #include <ext/pb_ds/assoc_container.hpp>
  16. // #include <ext/pb_ds/tree_policy.hpp>
  17. // using namespace __gnu_pbds;
  18.  
  19. // template<class T> using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
  20. // template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  21.  
  22. int M;
  23. struct dsu{
  24.     vector<int> p;
  25.     void init(int n){
  26.         p.assign(n, -1);
  27.     }
  28.     int get(int u){
  29.         return (p[u]<0?u:p[u]=get(p[u]));
  30.     }
  31.     void merge(int u, int v){
  32.         if((u=get(u))==(v=get(v))) return;
  33.         if(-p[u]<-p[v]) swap(u, v);
  34.         p[u]+=p[v];
  35.         p[v]=u;
  36.     }
  37. };
  38.  
  39. struct Matrix{
  40.     ll a[2][2]{};
  41.     int n;
  42.     void init(int n2){
  43.         n=n2;
  44.     }
  45.     void build(){
  46.         for(int i=0; i<n; i++) a[i][i]=1;
  47.     }
  48.     Matrix operator*(const Matrix& m2){
  49.         Matrix prod; prod.init(n);
  50.         for(int i=0; i<n; i++) for(int j=0; j<n; j++) for(int k=0; k<n; k++){
  51.             prod.a[i][k]+=(a[i][j]*m2.a[j][k])%M;
  52.             prod.a[i][k]%=M;
  53.         }
  54.         return prod;
  55.     }
  56. };
  57.  
  58. struct segTree{
  59.     vector<Matrix> prod;
  60.     int n;
  61.     void init(int n2){
  62.         n=1; while(n<n2) n*=2;
  63.         prod.resize(2*n);
  64.         for(int i=0; i<2*n; i++) {prod[i].init(2); prod[i].build();}
  65.     }
  66.     void set(int i, const Matrix& m1, int c, int lc, int rc){
  67.         if(lc+1==rc) {prod[c]=m1; return;}
  68.  
  69.         int m=(lc+rc)/2;
  70.         if(i<m) set(i, m1, 2*c+1, lc, m);
  71.         else set(i, m1, 2*c+2, m, rc);
  72.  
  73.         prod[c]=prod[2*c+2]*prod[2*c+1];
  74.     }
  75.     void set(int i, const Matrix& m1){
  76.         set(i, m1, 0, 0, n);
  77.     }
  78. };
  79.  
  80. void solve(){
  81.     int n; cin>>n>>M;
  82.     int a[n]; for(int i=0; i<n; i++) cin>>a[i];
  83.     int b[n]; for(int i=0; i<n; i++) b[i]=a[i];
  84.     sort(b, b+n);
  85.  
  86.     map<int, int> comp;
  87.     int uncomp[n+1]{};
  88.     int cntr=0;
  89.     for(int i=0; i<n; i++){
  90.         if(comp.count(b[i])) continue;
  91.         comp[b[i]]=cntr;
  92.         uncomp[cntr]=b[i];
  93.         cntr++;
  94.     }
  95.     for(int i=0; i<n; i++) a[i]=comp[a[i]];
  96.  
  97.     vector<vector<int>> inds(cntr);
  98.     for(int i=0; i<n; i++){
  99.         inds[a[i]].pb(i);
  100.     }
  101.  
  102.     dsu d1; d1.init(n);
  103.  
  104.     segTree seg1; seg1.init(n);
  105.  
  106.     Matrix m1; m1.init(2); // normal
  107.     m1.a[0][0]=m1.a[0][1]=m1.a[1][0]=1;
  108.     Matrix m2; m2.init(2); // 3rd 1
  109.     m2.a[0][0]=2; m2.a[1][0]=1;
  110.     Matrix m3; m3.init(2); m3.build(); // useless
  111.  
  112.     ll ans=0, sum=0;
  113.     for(int i=0; i<cntr; i++){
  114.         for(auto j:inds[i]){
  115.             if(j-1>=0&&a[j-1]<=i) d1.merge(j, j-1);
  116.             if(j-2>=0&&a[j-2]<=i) d1.merge(j, j-2);
  117.             if(j+1<n&&a[j+1]<=i) d1.merge(j, j+1);
  118.             if(j+2<n&&a[j+2]<=i) d1.merge(j, j+2);
  119.  
  120.             // check j+1, j+2, j+3
  121.             int cntl=0;
  122.             if(j>=1&&a[j-1]<=i) cntl++;
  123.             if(cntl&&j>=2&&a[j-2]<=i) cntl++;
  124.             if(cntl==2&&j>=3&&a[j-3]<=i) cntl++;
  125.  
  126.             if(cntl<=1) {
  127.                 seg1.set(j, m3);
  128.             }
  129.             else if(cntl==2) {
  130.                 seg1.set(j, m2);
  131.             }
  132.             else seg1.set(j, m1);
  133.  
  134.  
  135.             if(j+1<n&&a[j+1]<=i&&cntl>=2){
  136.                 seg1.set(j+1, m1);
  137.             }
  138.             else if(j+1<n&&a[j+1]<=i&&cntl==1){
  139.                 seg1.set(j+1, m2);
  140.             }
  141.             else if(j+1<n&&a[j+1]<=i){
  142.                 seg1.set(j+1, m3);
  143.             }
  144.  
  145.  
  146.             if(j+2<n&&a[j+1]<=i&&a[j+2]<=i&&cntl>=1){
  147.                 seg1.set(j+2, m1);
  148.             }
  149.             else if(j+2<n&&a[j+1]<=i&&a[j+2]<=i){
  150.                 seg1.set(j+2, m2);
  151.             }
  152.  
  153.             if(j+3<n&&a[j+1]<=i&&a[j+2]<=i&&a[j+3]<=i){
  154.                 seg1.set(j+3, m1);
  155.             }
  156.         }
  157.         ll ansi=(d1.get(0)==d1.get(n-1)?(seg1.prod[0].a[0][0]-sum+M)%M:0);
  158.  
  159.         ans+=(ansi*uncomp[i])%M; ans%=M;
  160.         sum+=ansi; sum%=M;
  161.     }
  162.     cout<<ans<<endl;
  163. }
  164.  
  165. int32_t main() {
  166.     #ifndef ONLINE_JUDGE
  167.         read_file;
  168.     #endif
  169.  
  170.     fast;
  171.  
  172.     int t;
  173.     t=1;
  174.     // cin>>t;
  175.     while(t--){
  176.         solve();
  177.     }
  178.     return 0;
  179. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/kWSGC9
language:
C++14 (gcc 8.3)
created:
16 days 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!