fork download
copy 
  1. #pragma GCC optimize("Ofast")
  2. #pragma GCC optimize("unroll-loops")
  3.  
  4. #include <bits/stdc++.h>
  5. #include <ext/pb_ds/assoc_container.hpp>
  6. #include <ext/pb_ds/tree_policy.hpp>
  7.  
  8. using namespace __gnu_pbds;
  9. using namespace std;
  10. using ll = long long;
  11. template <typename T>
  12. using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  13. // s.find_by_order(k) → Returns an iterator to the k-th smallest element (0-based index).
  14. // s.order_of_key(x) → Returns the number of elements strictly less than x.
  15. //abe saale ll ki range 1e18 tak hin hoti hai
  16. //return by reference se time bachta hai 
  17.  
  18. const ll mod = 1e9 + 7;
  19. const ll mod2 = 998244353;
  20.  
  21. ll gcd(ll a, ll b) {
  22.     return b ? gcd(b, a % b) : a;
  23. }
  24.  
  25. ll pow(ll a, ll b) {
  26.     ll ans = 1;
  27.     while (b) {
  28.         if (b & 1) ans *= a;
  29.         b >>= 1;
  30.         a *= a;
  31.     }
  32.     return ans;
  33. }
  34.  
  35. ll pow(ll a, ll b, ll c) {
  36.     ll ans = 1;
  37.     while (b) {
  38.         if (b & 1) ans = (ans * a) % c;
  39.         b >>= 1;
  40.         a = (a * a) % c;
  41.     }
  42.     return ans;
  43. }
  44.  
  45. vector<ll> seiveoferasthones(ll n)
  46. {
  47.     vector<bool> prime(n + 1, true);
  48.     prime[0] = false;
  49.     prime[1] = false;
  50.     for (int i = 2; i * i <= n; i++)
  51.     {
  52.         if (prime[i])
  53.         {
  54.             for (int j = i * i; j <= n; j += i)
  55.             {
  56.                 prime[j] = false;
  57.             }
  58.         }
  59.     }
  60.     vector <ll> primes;
  61.     for(ll i  = 2 ; i <= n ; i++)
  62.     {
  63.         if(prime[i])
  64.         {
  65.             primes.push_back(i);
  66.         }
  67.     }
  68.     return primes;
  69. }
  70.  
  71. void check(bool b) {
  72.     if (b)
  73.         cout << "Yes\n";
  74.     else
  75.         cout << "No\n";
  76. }
  77.  
  78. // DFS
  79. void dfs(vector<vector<ll>> &adj , vector <bool> &visited , ll s)
  80. {
  81.     if(visited[s])
  82.     {
  83.         return;
  84.     }
  85.     visited[s] = true;
  86.     for(auto u : adj[s])
  87.     {
  88.         dfs(adj,visited,u);
  89.     }
  90. }
  91.  
  92. // BFS
  93. // queue <ll> q;
  94. // vector <bool> visited(n+1,false);
  95. // vector <ll> distance(n+1,0);
  96. // visited[x] = true;
  97. // distance[x] = 0;
  98. // q.push(x);
  99. // while(!q.empty())
  100. // {
  101. //     ll s = q.front();
  102. //     q.pop();
  103. //     for(auto u:adj[s])
  104. //     {
  105. //        if(visited[u])
  106. //        {
  107. //           continue;
  108. //        }
  109. //        visited[u] = true;
  110. //        distance[u] = distance[s] + 1;
  111. //        q.push(u);
  112. //     }
  113. // }
  114.  
  115. int main() {
  116.     ios_base::sync_with_stdio(false);
  117.     cin.tie(nullptr);
  118.     cout.tie(nullptr);
  119.     int t;
  120.     cin >> t;
  121.     while (t--) {
  122.         ll n;
  123.         cin >> n;
  124.         vector<ll>vec(n);
  125.         for(int i = 0 ;  i < n ; i++)
  126.         {
  127.            cin >> vec[i] ;
  128.         }
  129.         vector <ll> allowed(n);
  130.         for(int i = 0 ;  i < n ; i++)
  131.         {
  132.          allowed[i] = ceil((double)vec[i]/2)-1;  
  133.         }
  134.         ll count = ((n)*(n+1))/2;
  135.         // cout << count << endl;
  136.         for(int i = 0 ; i < n ; i++)
  137.         {
  138.             ll temp = 0;
  139.             for(int j = i+1 ; j < n ;j++)
  140.             {
  141.                 ll temp2 = 0;
  142.                 if(allowed[j] >= (j-i))
  143.                 {
  144.                     temp2 = j-i;
  145.                 }
  146.                 else
  147.                 {
  148.                     temp2 = allowed[j];     
  149.                 }
  150.                 if(temp2 <= temp)
  151.                 {
  152.                     if(vec[j] <= temp)
  153.                     {
  154.                         count -= n-j;
  155.                         break;
  156.                     }
  157.                     else
  158.                     {
  159.                         temp = vec[j];
  160.                     }
  161.                 }
  162.                 else
  163.                 {
  164.                     temp = temp2;
  165.                 }
  166.             }
  167.         }
  168.         cout << count << endl;
  169.     }
  170.     return 0;
  171. }
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
5
4
2 1 3 3
3
1 2 3
7
8 12 7 5 4 9 3
7
5 3 1 4 2 1 1
3
2 2 2
stdout
copy 
9
6
23
15
5
https://ideone.com/CKOeQ3
language:
C++14 (gcc 8.3)
created:
2 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!