fork download
copy 
  1. //NiceDuck
  2. #include "bits/stdc++.h"
  3. typedef long long ll;
  4. using namespace std;
  5. #define FILE "000"
  6. #define foru(i,a,b) for(int i=(int)(a); i<=(int)(b); ++i)
  7. #define ford(i,a,b) for(int i=(int)(a); i>=(int)(b); --i)
  8. #define fastio ios_base::sync_with_stdio(0);cin.tie(0);
  9. #define pb push_back
  10. #define fi first
  11. #define se second
  12. #define pii pair<int,int>
  13. #define pil pair<int,ll>
  14. #define pli pair<ll,int>
  15. #define MOD 1000000007
  16. #define el "\n"
  17.  
  18. const int MAX=5e3+4,CORD=2e6;
  19. int n,q,a[MAX];
  20. ll f[MAX][MAX];
  21. int fre[4000006];
  22.  
  23. void pre()
  24. {
  25.     ford(l,n,1)
  26.     {
  27.         foru(r,l+1,n)
  28.         {
  29.             if(r-l+1>=3) 
  30.             {
  31.                 int tmp=-(a[l]+a[r])+CORD;
  32.                 f[l][r]=f[l][r-1]+f[l+1][r]-f[l+1][r-1]+fre[tmp];
  33.             }
  34.             fre[a[r]+CORD]++;
  35.         }
  36.         foru(r,l+1,n) fre[a[r]+CORD]--;
  37.     }
  38. }
  39.  
  40. int main()
  41. {
  42.     fastio
  43.     if(fopen(FILE ".inp","r"))
  44.     {
  45.         freopen(FILE ".inp","r",stdin);
  46.         freopen(FILE ".out","w",stdout);
  47.     }
  48.  
  49.     cin>>n>>q;
  50.     foru(i,1,n) 
  51.     {
  52.         cin>>a[i];
  53.     }
  54.     pre();
  55.     while(q--)
  56.     {
  57.         int l,r; cin>>l>>r;
  58.         cout<<f[l][r]<<el;
  59.     }
  60.  
  61.     return 0;
  62. }
Success #stdin #stdout 0s 5308KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/jAI8HE
language:
C++14 (gcc 8.3)
created:
21 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!