fork download 
  1. #include <cmath>
  2. #include <cstdio>
  3. #include <vector>
  4. #include <iostream>
  5. #include <algorithm>
  6. using namespace std;
  7.  
  8. int a[100010], ans[100010];
  9. int cnt[100010];
  10. int sqn, curl=1, curr=0, z=0;
  11. vector<pair<pair<int, int>, int> > v;
  12.  
  13. bool cmp(const pair<pair<int, int>, int> &x, const pair<pair<int, int>, int> &y) {
  14. 	int z1=x.first.first/sqn;
  15. 	int z2=y.first.first/sqn;
  16. 	if(z1!=z2)
  17. 		return z1<z2;
  18. 	return x.first.second<y.first.second;
  19. }
  20.  
  21. int main() {
  22.     /* Enter your code here. Read input from STDIN. Print output to STDOUT */ 
  23.     int i, j, q, k, x, y, n;
  24.     cin>>n>>q;
  25.     for(i=1; i<=n; ++i) {
  26.         cin>>a[i];
  27.     }
  28.     sqn=sqrt(n);
  29.     for(i=1; i<=q; ++i) {
  30.         cin>>x>>y;
  31.         v.push_back({{x,y}, i});
  32.     }
  33.     sort(v.begin(), v.end(), cmp);
  34.     for(i=0; i<v.size(); ++i) {
  35.         int l=v[i].first.first;
  36.         int r=v[i].first.second;
  37.         //cout<<l<<" "<<r<<" "<<v[i].second<<endl;
  38.         while(curr<r) {
  39.             curr++;
  40.             cnt[a[curr]]++;
  41.             if(cnt[a[curr]-1]==0 && cnt[a[curr]+1]==0) {
  42.                 //cout<<curr<<endl;
  43.                 z++;
  44.             }
  45.             else if(cnt[a[curr]-1] && cnt[a[curr]+1])   z--;
  46.         }
  47.         while(curr>r) {
  48.             cnt[a[curr]]--;
  49.             if(cnt[a[curr]-1] && cnt[a[curr]+1])
  50.                 z++;
  51.             else if(cnt[a[curr]-1]==0 && cnt[a[curr]+1]==0) z--;
  52.             curr--;
  53.         }
  54.         while(curl<l) {
  55.             cnt[a[curl]]--;
  56.             if(cnt[a[curl]-1] && cnt[a[curl]+1])
  57.                 z++;
  58.             else if(cnt[a[curl]-1]==0 && cnt[a[curl]+1]==0) z--;
  59.             curl++;
  60.         }
  61.         while(curl>l) {
  62.             curl--;
  63.             cnt[a[curl]]++;
  64.             if(cnt[a[curl]-1]==0 && cnt[a[curl]+1]==0)
  65.                 z++;
  66.             else if(cnt[a[curl]-1] && cnt[a[curl]+1])   z--;
  67.         }
  68.         ans[v[i].second]=z;
  69.     }
  70.     for(i=1; i<=q; ++i)
  71.         cout<<ans[i]<<endl;
  72.     return 0;
  73. }
  74.  
Time limit exceeded #stdin #stdout 5s 4644KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/BwAtvU
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
secret

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!