fork download
copy 
  1. //Hoang1264589
  2. #include "bits/stdc++.h"
  3. #define Task "TRIANGLE"
  4. #define up(i,a,b) for (int i = (int)a; i <= (int)b; i++)
  5. #define pii pair<int, int>
  6. #define f first
  7. #define s second
  8. #define ep emplace_back
  9. #define bit(x,i) ((x >> i) & 1)
  10. using namespace std;
  11.  
  12. const int maxn = 1e5 + 10;
  13. int a[maxn];
  14. int n;
  15.  
  16. int spmax[17][maxn];
  17. int spmin[17][maxn];
  18. int tmin[17][maxn];
  19. namespace Sub4{
  20.     bool compare_max(int x, int y){ return a[x] > a[y]; }
  21.     bool compare_min(int x, int y){ return a[x] < a[y]; }
  22.  
  23.     void make_sparse(){
  24.         up(i,1,n){
  25.             spmax[0][i] = spmin[0][i] = i;
  26.             tmin[0][i] = 0;
  27.         }
  28.         for (int i = 1; (1 << i) <= n; i++){
  29.             for (int j = 1; j + (1 << i) - 1 <= n; j++){
  30.                 if (compare_max(spmax[i-1][j], spmax[i-1][j + (1 << (i-1))])){
  31.                     spmax[i][j] = spmax[i-1][j];
  32.                 }
  33.                 else spmax[i][j] = spmax[i-1][j + (1 << (i-1))];
  34.  
  35.                 int Lm = spmin[i-1][j];
  36.                 int Rm = spmin[i-1][j + (1 << (i-1))];
  37.                 int Lt = tmin[i-1][j];
  38.                 int Rt = tmin[i-1][j + (1 << (i-1))];
  39.  
  40.                 if (compare_min(Lm, Rm)) spmin[i][j] = Lm;
  41.                 else spmin[i][j] = Rm;
  42.  
  43.                 vector<int> temp = {};
  44.                 temp.ep(Lm), temp.ep(Rm), temp.ep(Lt), temp.ep(Rt);
  45.                 sort(temp.begin(), temp.end(), compare_min);
  46.                 tmin[i][j] = temp[1];
  47.             }
  48.         }
  49.     }
  50.  
  51.     int querymax(int L, int R){
  52.         int k = 31 - __builtin_clz(R - L + 1);
  53.         if (compare_max(spmax[k][L], spmax[k][R - (1 << k) + 1])){
  54.             return spmax[k][L];
  55.         }
  56.         return spmax[k][R - (1 << k) + 1];
  57.     }
  58.     pii querymin(int L, int R){
  59.         int k = 31 - __builtin_clz(R - L + 1);
  60.         const int& Lmin = spmin[k][L];
  61.         const int& Rmin = spmin[k][R - (1 << k) + 1];
  62.  
  63.         int len = R - L + 1;
  64.         vector<int> save;
  65.         up(i,0,16){
  66.             if (bit(len, i)){
  67.                 save.ep(spmin[i][L]);
  68.                 save.ep(tmin[i][L]);
  69.                 L += (1 << i);
  70.             }
  71.         }
  72.         sort(save.begin(), save.end(), compare_min);
  73.         if (compare_min(Lmin, Rmin)) return make_pair(Lmin, save[1]);
  74.         return make_pair(Rmin, save[1]);
  75.     }
  76.  
  77.     bool check_longest(int len){
  78.         up(l,1,n){
  79.             int r = l+len;
  80.             if (r > n) break;
  81.             int MaxEle = querymax(l, r);
  82.             pii MinEle = querymin(l, r);
  83.             if (a[MinEle.f] + a[MinEle.s] > a[MaxEle]) return true;
  84.         }
  85.         return false;
  86.     }
  87.  
  88.     void MAIN(){
  89.         make_sparse();
  90.         int L = 0;
  91.         int R = n+1;
  92.         while (R - L > 1){
  93.             int mid = (R+L) >> 1;
  94.             if (check_longest(mid)) L = mid;
  95.             else R = mid;
  96.         }
  97.         cout << R;
  98.     }
  99. }
  100.  
  101. namespace Sub3{
  102.     void MAIN(){
  103.         int l = 1;
  104.         int r = 3;
  105.         int maxx = 0;
  106.         while (r != n){
  107.             if (r - l <= 2) ++r;
  108.             else if (a[l] + a[l+1] > a[r]){
  109.                 maxx = max(maxx, r - l + 1);
  110.                 ++r;
  111.             }
  112.             else ++l;
  113.         }
  114.         if (a[l] + a[l+1] > a[r]) maxx = max(maxx, r - l + 1);
  115.         cout << maxx;
  116.     }
  117. }
  118.  
  119. signed main(){
  120.     ios_base::sync_with_stdio(false);
  121.     cin.tie(0);
  122.     if (fopen(Task".inp", "r")){
  123.         freopen (Task".inp", "r", stdin);
  124.         freopen (Task".out", "w", stdout);
  125.     }
  126.  
  127.     bool sorted = 1;
  128.     cin >> n;
  129.     up(i,1,n){
  130.         cin >> a[i];
  131.         if (i > 1 && a[i] < a[i-1]) sorted = 0;
  132.     }
  133.     a[0] = 1e9 + 7;
  134.  
  135.     if (sorted) Sub3::MAIN();
  136.     else Sub4::MAIN();
  137. }
Runtime error #stdin #stdout 0.01s 5532KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/4xTeF0
language:
C++14 (gcc 8.3)
created:
2 years 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!