fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using ll = long long;
  5.  
  6. const int n = 1e5 + 5;
  7. const int max_a = 1000;
  8.  
  9. int level[n], pos[n], first[500];
  10. vector<int> row[500];
  11.  
  12. ll sttLv(int lv) {
  13.     return 1LL * lv * (lv - 1) / 2 + 1;
  14. }
  15.  
  16. ll endLv(int lv) {
  17.     return 1LL * lv * (lv + 1) / 2;
  18. }
  19.  
  20. int timLv(ll a) {
  21.     ll l = 1, r = 2e9, ans = -1;
  22.     while (l <= r) {
  23.         ll m = (l + r) / 2;
  24.         if (endLv(m) >= a) {
  25.             ans = m;
  26.             r = m - 1;
  27.         } else {
  28.             l = m + 1;
  29.         }
  30.     }
  31.     return (int)ans;
  32. }
  33.  
  34. ll sub1(int a) {
  35.     vector<vector<int>> tam;
  36.     int cur = 1, lv = 1;
  37.     while (cur <= max_a) {
  38.         vector<int> row;
  39.         for (int j = 0; j < lv && cur <= max_a; ++j) {
  40.             row.push_back(cur++);
  41.         }
  42.         tam.push_back(row);
  43.         ++lv;
  44.     }
  45.  
  46.     int r = -1, c = -1;
  47.     for (int i = 0; i < tam.size(); ++i) {
  48.         for (int j = 0; j < tam[i].size(); ++j) {
  49.             if (tam[i][j] == a) {
  50.                 r = i, c = j;
  51.             }
  52.         }
  53.     }
  54.  
  55.     ll res = 0;
  56.     for (int i = 0; i <= r; ++i) {
  57.         int left = max(0, c - (r - i));
  58.         int right = min((int)tam[i].size() - 1, c);
  59.         for (int j = left; j <= right; ++j) {
  60.             res += tam[i][j];
  61.         }
  62.     }
  63.     return res;
  64. }
  65.  
  66. ll sub2(int a) {
  67.     int lv = level[a];
  68.     int r = pos[a];
  69.  
  70.     ll res = 0;
  71.     for (int i = 1; i <= lv; ++i) {
  72.         int left = max(1, r - (lv - i));
  73.         int right = min(i, r);
  74.  
  75.         for (int j = left - 1; j <= right - 1; ++j) {
  76.             res += row[i][j];
  77.         }
  78.     }
  79.     return res;
  80. }
  81.  
  82. ll sub3(ll a) {
  83.     int lv = timLv(a);
  84.     ll start = sttLv(lv);
  85.     ll r = a - start + 1;
  86.  
  87.     ll res = 0;
  88.     for (int i = 1; i <= lv; ++i) {
  89.         ll l1 = max(1LL, r - (lv - i));
  90.         ll r1 = min(1LL * i, r);
  91.  
  92.         ll len = r1 - l1 + 1;
  93.         if (len > 0) {
  94.             ll row_start = sttLv(i);
  95.             res += (2 * row_start + l1 + r1 - 2) * len / 2;
  96.         }
  97.     }
  98.     return res;
  99. }
  100.  
  101. int main() {
  102.     ios::sync_with_stdio(false);
  103.     cin.tie(nullptr);
  104.  
  105.     int cur = 1, lv = 1;
  106.     while (cur <= n) {
  107.         first[lv] = cur;
  108.         for (int j = 0; j < lv && cur <= n; ++j, ++cur) {
  109.             row[lv].push_back(cur);
  110.             level[cur] = lv;
  111.             pos[cur] = j + 1;
  112.         }
  113.         ++lv;
  114.     }
  115.  
  116.     int q;
  117.     cin >> q;
  118.     while (q--) {
  119.         ll a;
  120.         cin >> a;
  121.  
  122.         if (a <= max_a) {
  123.             cout << sub1((int)a) << '\n';
  124.         } else if (a <= n) {
  125.             cout << sub2((int)a) << '\n';
  126.         } else {
  127.             cout << sub3(a) << '\n';
  128.         }
  129.     }
  130.  
  131.     return 0;
  132. }
  133.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/3miZVc
language:
C++14 (gcc 8.3)
created:
9 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!