fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define fi first
  3. #define endl '\n'
  4. #define se second
  5. #define int long long
  6. #define getName(x) #x
  7. #define vi std::vector<int>
  8. #define isz(v) (int) v.size()
  9. #define pii std::pair<int, int>
  10. #define all(v) v.begin(), v.end()
  11. #define loop cerr << "here" << endl;
  12. #define breakLoop if(TIME > 1) break;
  13. #define TIME 1.0 * clock() / CLOCKS_PER_SEC
  14. using namespace std;
  15. typedef long long ll;
  16. const int inf32 = 1e18 + 7;
  17.  
  18. template <typename T> void maximize(T &a, T b){if(a < b) a = b;}
  19. template <typename T> void minimize(T &a, T b){if(a > b) a = b;}
  20. int tc, n, t, f[500005][20][2][2], a[500005], dp[20][2][2];
  21.  
  22. int cost(int i, int k, bool t1, bool t2){
  23.     int x = a[i - (1 << k) + (t1 ? 1 : 2)], y = a[i - (1 << k) - (t2 ? 0 : 1)];
  24.     return abs(x - y);
  25. }
  26. int cost2(int i, bool t1, bool t2){return abs(a[i - (t1 ? 0 : 1)] - a[i + (t2 ? 1 : 2)]);}
  27.  
  28.  
  29. signed main(){
  30.     ios::sync_with_stdio(false);
  31.     cin.tie(nullptr);
  32.     #define task "FROGQUERIES"
  33.     if (fopen(task".inp", "r")){
  34.         freopen(task".inp", "r", stdin);
  35.         freopen(task".out", "w", stdout);
  36.     }
  37.     cin >> tc;
  38.     while(tc--){
  39.         cin >> n >> t;
  40.         for(int i = 1; i <= n; i++){
  41.             cin >> a[i];
  42.             f[i][1][1][1] = abs(a[i] - a[i - 1]); f[i][0][0][0] = f[i][0][1][0] = f[i][1][0][0] = inf32;
  43.  
  44.             for(int k = 2; (1 << k) <= i; k++){
  45.                 for(int x = 0; x < 2; x++){
  46.                     for(int y = 0; y < 2; y++){
  47.                         int nxt = i - (1 << (k - 1));
  48.                         int res1 = f[i][k - 1][0][y] + f[nxt][k - 1][x][1] + cost(i, k - 1, 0, 1);
  49.                         int res2 = f[i][k - 1][1][y] + f[nxt][k - 1][x][1] + cost(i, k - 1, 1, 1);
  50.                         int res3 = f[i][k - 1][1][y] + f[nxt][k - 1][x][0] + cost(i, k - 1, 1, 0);
  51.                         f[i][k][x][y] = min({res1, res2, res3});
  52.                     }
  53.                 }
  54.             }
  55.         }
  56.  
  57.         while(t--){
  58.             int L, R;
  59.             cin >> L >> R;
  60.             int las = -1;
  61.             for(int bit = 19; bit >= 0; bit--){
  62.                 if(R - (1 << bit) < L - 1) continue;
  63.                 for(int x = 0; x < 2; x++){
  64.                     for(int y = 0; y < 2; y++){
  65.                         int res1 = las == -1 ? inf32 : f[R][bit][x][0] + dp[las][1][y] + cost2(R, 0, 1);
  66.                         int res2 = las == -1 ? f[R][bit][x][1] : f[R][bit][x][1] + dp[las][1][y] + cost2(R, 1, 1);
  67.                         int res3 = las == -1 ? f[R][bit][x][1] : f[R][bit][x][1] + dp[las][0][y] + cost2(R, 1, 0);
  68.                         dp[bit][x][y] = min({res1, res2, res3});
  69.  
  70.                     }
  71.                 }
  72.                 las = bit; R -= (1 << bit);
  73.             }
  74.             cout << min(dp[las][1][0], dp[las][1][1]) << ' ';
  75.         }
  76.         cout << endl;
  77.     }
  78.  
  79.  
  80.  
  81. }
  82. /*
  83. Na, na, na-na-na-na-na
  84. Đừng đóng vai anh, đừng, đừng đóng vai anh
  85. Đừng đóng vai anh nữa, nghe mỏi tai lắm anh
  86. Đừng đóng vai anh, đừng, đừng đóng vai anh
  87. Mồm thì như gió bấc, làm thì chẳng ra gì
  88. */
  89.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/55YC1L
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!