fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define int long long
  5. #define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
  6. #define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; i--)
  7.  
  8. template<typename X, typename Y> bool chmax(X& a, const Y& b) { return a < b ? a = b, 1 : 0; }
  9. template<typename X, typename Y> bool chmin(X& a, const Y& b) { return a > b ? a = b, 1 : 0; }
  10.  
  11. mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
  12. int Rand(int l, int r) { return uniform_int_distribution<int>(l, r)(rng); }
  13.  
  14. constexpr int MAXN = 5005;
  15. constexpr int MAXQ = 1e5 + 5;
  16. constexpr int MAXA = 2e6;
  17. constexpr int inf = 1e9 + 67;
  18. constexpr int INF = 1e18 + 67;
  19.  
  20. int N, Q, A[MAXN];
  21. short freq[2 * MAXA + 5], cnt[MAXN][MAXN]; 
  22. int dp[MAXN][MAXN];
  23.  
  24. void solve() {
  25.     cin >> N >> Q;
  26.     FOR(i, 1, N) cin >> A[i];
  27.     FOR(l, 1, N) {
  28.         FOR(r, l + 1, N) {
  29.             int T = -(A[l] + A[r]) + MAXA;
  30.             if (T >= 0 && T <= 2 * MAXA) cnt[l][r] = freq[T];
  31.             freq[A[r] + MAXA]++;
  32.         }
  33.         FOR(r, l + 1, N) freq[A[r] + MAXA]--;
  34.     }
  35.     FOR(len, 3, N) FOR(l, 1, N - len + 1) {
  36.         int r = l + len - 1;
  37.         dp[l][r] = dp[l + 1][r] + dp[l][r - 1] - dp[l + 1][r - 1] + cnt[l][r];
  38.     }
  39.     FOR(i, 1, Q) {
  40.         int l, r; cin >> l >> r;
  41.         cout << dp[l][r] << "\n";
  42.     }
  43. }
  44.  
  45. int32_t main() {
  46.     ios_base::sync_with_stdio(false); cin.tie(NULL);
  47.  
  48.     #define TASK "blizzing_"
  49.     if (fopen(TASK".INP", "r")) {
  50.         freopen(TASK".INP", "r", stdin);
  51.         freopen(TASK".OUT", "w", stdout);
  52.     }
  53.  
  54.     int tests = 1; // cin >> tests;
  55.     while (tests--) solve();
  56.  
  57.     #ifdef LOCAL
  58.     cerr << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
  59.     #endif
  60.     return 0;
  61. }
  62.  
Success #stdin #stdout 0.01s 5664KB
comments (?)
stdin
copy 
8 2 
1 2 3 0 -2 -3 7 8 
1 5 
1 8
stdout
copy 
1
3
https://ideone.com/l2uvqA
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!