fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ii pair<int,int>
  4. #define fi first
  5. #define se second
  6. //#define int long long
  7. #define ll long long
  8. #define ld double
  9. #define mp make_pair
  10. #define lg2 18
  11. #define iii pair<int,ii>
  12. #define iiii pair<ii,ii>
  13. #define base 29
  14. #define eps 1e-8
  15. #define MASK(i) (1LL << (i))
  16. #define BIT(S, i) (((S) >> (i)) & 1)
  17. int dx[]= {0LL,0LL,1,-1,1,1,-1,-1};
  18. int dy[]= {1,-1,0LL,0LL,1,-1,1,-1};
  19. const int maxn=1e5+1;
  20. const int mod=1e9+7;
  21. const int P[]={2,3,5,7,11};
  22. int n,mask[maxn];
  23. ll a[maxn];
  24. vector<ll>nen;
  25. struct FEN
  26. {
  27.     int n;
  28.     int bit[maxn];
  29.     FEN(){};
  30.     FEN(int _n):n(_n+1)
  31.     {
  32.     };
  33.     int get(int r) {
  34.         int ret = 0;
  35.         for (; r >= 0; r = (r & (r + 1)) - 1)
  36.             ret =max(ret, bit[r]);
  37.         return ret;
  38.     }
  39.  
  40.     int get(int l, int r) {
  41.         return get(r) - get(l - 1);
  42.     }
  43.  
  44.     void update(int idx, int delta) {
  45.         for (; idx < n; idx = idx | (idx + 1))
  46.             bit[idx] =max(bit[idx], delta);
  47.     }
  48.     void updateRange(int l,int r,int val)
  49.     {
  50.         update(l,val);
  51.         update(r+1,-val);
  52.     }
  53. }bit[MASK(5)];
  54. signed main()
  55. {
  56.     ios_base::sync_with_stdio(0);
  57.     cin.tie(0);
  58.     cout.tie(0);
  59.     #define task "coprime"
  60.     if(fopen(task".inp","r"))
  61.     {
  62.         freopen(task".inp","r",stdin);
  63.         freopen(task".out","w",stdout);
  64.     }
  65.     cin>>n;
  66.     for(int i=1;i<=n;i++)
  67.     {
  68.         cin>>a[i];
  69.         nen.push_back(a[i]);
  70.     }
  71.     sort(nen.begin(),nen.end());
  72.     nen.erase(unique(nen.begin(),nen.end()),nen.end());
  73.     int k=5;
  74.     for(int i=1;i<=n;i++)
  75.     {
  76.         for(int j=0;j<k;j++)
  77.         {
  78.             if(a[i]%P[j]==0)
  79.             {
  80.                 mask[i]|=MASK(j);
  81.             }
  82.         }
  83.     }
  84.     for(int mask1=0;mask1<MASK(k);mask1++)
  85.     {
  86.         bit[mask1]=FEN(n);
  87.     }
  88.     int ans=1;
  89.     for(int i=1;i<=n;i++)
  90.     {
  91.         int x=0;
  92.         int pos=lower_bound(nen.begin(),nen.end(),a[i])-nen.begin()+1;
  93.         int c=(MASK(k)-1)^mask[i];
  94.         for(int mask1=c;;mask1=(mask1-1)&c)
  95.         {
  96.             x=max(x,bit[mask1].get(pos-1));
  97.             if(mask1==0)break;
  98.         }
  99.         ans=max(ans,x+1);
  100.         bit[mask[i]].update(pos,x+1);
  101.     }
  102.     cout<<ans;
  103.     cerr <<endl<< "TIME : " << clock() * 0.001 << "s" << endl ;
  104. }
  105.  
Success #stdin #stdout #stderr 0.01s 16028KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
stderr
copy 
TIME : 8.489s
https://ideone.com/YLZtSm
language:
C++14 (gcc 8.3)
created:
1 day 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!