fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long ll;
  5. typedef unsigned long long int llu;
  6. #define pb push_back
  7. #define mp make_pair
  8. #define X first
  9. #define Y second
  10. #define mem(a, v) memset(a, v, sizeof(a))
  11. #define PI acos(-1)
  12. #define S(a) scanf("%d",&a)
  13. #define SL(a) scanf("%lld",&a)
  14. #define S2(a, b) scanf("%d%d",&a,&b)
  15. #define nl printf("\n")
  16. #define deb(x) cout<<#x<<" : "<<x<<endl;
  17. #define deb2(x, y) cout<<#x<<" : "<<x<<" | "<<#y<<" : "<<y<<endl;
  18. #define deb3(x, y, z) cout<<#x<<" : "<<x<<" | "<<#y<<" : "<<y<<" | "<<#z<<" : "<<z<<endl;
  19. #define debv(x) {cout<<#x<<" : "<<endl; for(int ii =0; ii < x.size(); ii++) cout<<x[ii]<<" "; cout<<endl; }
  20. #define debarr(x, xs) {cout<<#x<<" : "<<endl; for(int ii =0; ii < xs; ii++) cout<<x[ii]<<" "; cout<<endl; }
  21. //auto T=clock(); 
  22. //cout<<double(clock()-T)/CLOCKS_PER_SEC<<'\n';
  23. const ll mod = 1000000007LL;
  24. const int lmt = 100005;
  25.  
  26. bool vis[lmt];
  27. int a[lmt];
  28. ll output[lmt];
  29. int buck = sqrt(100000);
  30.  
  31. struct node {
  32.     int l, r, id;
  33.     node(int a, int b, int c) {
  34.         l = a;
  35.         r = b;
  36.         id = c;
  37.     }
  38. };
  39.  
  40. bool cmp(const node &a, const node &b) {
  41.     if((a.l/buck) != (b.l/buck))
  42.         return (a.l/buck) < (b.l/buck);
  43.     return ((a.r/buck) < (b.r/buck));
  44. }
  45.  
  46. vector<node> query;
  47.  
  48. ll ans = 0;
  49.  
  50. void add(int idx) {
  51.     int ele = a[idx];
  52.     if((vis[ele+1]) && (vis[ele-1]))
  53.         ans--;
  54.     else if((!vis[ele+1]) && (!vis[ele-1]))
  55.         ans++;
  56.     vis[ele] = true;
  57. }
  58.  
  59. void remove(int idx) {
  60.     int ele = a[idx];
  61.     if((vis[ele+1]) && (vis[ele-1]))
  62.         ans++;
  63.     else if((!vis[ele+1]) && (!vis[ele-1]))
  64.         ans--;
  65.     vis[ele] = false;
  66. }
  67.  
  68.  
  69. int main(){
  70.     mem(vis, false);
  71.     int n, q;
  72.  
  73.     S2(n, q);
  74.  
  75.     for(int i = 1; i <= n; i++)
  76.         S(a[i]);
  77.  
  78.     for(int i = 0; i < q; i++) {
  79.         int l, r;
  80.         S2(l, r);
  81.         query.pb(node(l, r, i));
  82.     }
  83.  
  84.     sort(query.begin(), query.end(), cmp);
  85.  
  86.     int _l = 1, _r = 1;
  87.     add(1);
  88.     for(int i = 0; i < q; i++) {
  89.         int L = query[i].l, R = query[i].r;
  90.         //deb2(L, R);
  91.         while(_l > L) {
  92.             _l--;
  93.             add(_l);
  94.         }
  95.         while(_r < R) {
  96.             _r++;
  97.             add(_r);
  98.         }
  99.         while(_r > R) {
  100.             remove(_r);
  101.             _r--;
  102.         }
  103.         while(_l < L) {
  104.             remove(_l);
  105.             _l++;
  106.         }
  107.  
  108.         output[query[i].id] = ans;
  109.     }
  110.  
  111.     for(int i = 0; i < q; i++)
  112.         printf("%lld\n", output[i]);
  113.  
  114.     return 0;
  115. }
Time limit exceeded #stdin #stdout 5s 4740KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/KTg3Ax
language:
C++14 (gcc 8.3)
created:
8 years 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!