kokokozhina

http://codeforces.com/group/E63wP21Jn2/contest/209780/proble

Nov 2nd, 2016
56
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.20 KB | None | 0 0
  1.  
  2.  #include <iostream>
  3. #include <map>
  4. #include <string>
  5. #include <fstream>
  6. #include <stdio.h>
  7. #include <set>
  8. #include <vector>
  9. #include <algorithm>
  10. #include <queue>
  11.  
  12. using namespace std;
  13.  
  14. #define ll long long
  15. #define pb push_back
  16. #define mp make_pair
  17.  
  18. //inc f(ll pos, ll x){
  19. //
  20. //}
  21.  
  22. int main()
  23. {
  24. #ifdef _DEBUG
  25.     freopen("in.txt", "r", stdin);
  26.     freopen("out.txt", "w", stdout);
  27. #endif
  28.  
  29.  
  30.     ll n, m;
  31.     scanf("%I64d%I64d", &n, &m);
  32.  
  33.     vector<ll> a(n);
  34.     for(ll i = 0; i < n; i++){
  35.         scanf("%I64d", &a[i]);
  36.  
  37.     }
  38.  
  39.     vector<map<int, int>> f(n);
  40.     for(ll i = 0; i < n; i++){
  41.         for(ll pos = i; pos < n; pos |= pos + 1)
  42.             f[pos][a[i]]++;
  43.     }
  44.  
  45.    
  46.     for(ll i = 0; i < m; i++){
  47.         ll pos, l, r, x;
  48.  
  49.         scanf("%I64d%I64d%I64d", &l, &r, &x);
  50.         l--, r--;
  51.         ll sumy = 0, sumx  = 0;
  52.        
  53.         for(ll pos = r; pos >= 0; pos = (pos & (pos + 1)) - 1){
  54.             auto itt = f[pos].find(x);
  55.             for(auto it = f[pos].begin(); it != itt; it++)
  56.                 sumy += it->second;
  57.         }
  58.  
  59.         for(ll pos = l - 1; pos >= 0; pos = (pos & (pos + 1)) - 1){
  60.             auto itt = f[pos].find(x);
  61.             for(auto it = f[pos].begin(); it != itt; it++)
  62.                 sumx += it->second;
  63.         }
  64.  
  65.  
  66.         printf("%I64d\n", sumy - sumx);
  67.        
  68.  
  69.     }
  70.  
  71.  
  72.     return 0;
  73. }
Add Comment
Please, Sign In to add comment