fork(30) download
copy 
  1. #include <vector>
  2. #include <cstdio>
  3. #include <cstring>
  4. #include <queue>
  5. #include <cctype>
  6. #include <cmath>
  7. #include <algorithm>
  8. #include <iostream>
  9. #include <bitset>
  10. #include <map>
  11. #include <complex>
  12. #include <ctime>
  13. #include <numeric>
  14. #include <set>
  15.  
  16. using namespace std;
  17.  
  18. typedef long long ll;
  19.  
  20. typedef struct node{
  21.     int s, e, val, pos;
  22.     bool operator<(const node& n) const{
  23.         if(e != n.e) return e < n.e;
  24.         return val > n.val;
  25.     }
  26.     node(){};
  27.     node(int ss, int ee, int v, int p){
  28.         s = ss, e = ee, val = v, pos = p;
  29.     }
  30. }node;
  31.  
  32. int occs[(int)1e6 + 5], tree[30005], n, ans[200005];
  33.  
  34. void update(int x, int val){
  35.     while(x <= n){
  36.         tree[x] += val;
  37.         x += x & -x;
  38.     }
  39. }
  40.  
  41. int query(int x){
  42.     int ret = 0;
  43.     while(x > 0){
  44.         ret += tree[x];
  45.         x -= x & -x;
  46.     }
  47.     return ret;
  48. }
  49.  
  50. int main()
  51. {
  52. #ifndef ONLINE_JUDGE
  53.     freopen("in.in", "r", stdin);
  54. #endif
  55.  
  56.     int q, s, e;
  57.     vector<node> v;
  58.     scanf("%d", &n);
  59.     for(int i = 1; i <= n; i++){
  60.         scanf("%d", &s);
  61.         v.push_back(node(i, i, s, -1));
  62.     }
  63.     scanf("%d", &q);
  64.     for(int i = 0; i < q; i++){
  65.         scanf("%d %d", &s, &e);
  66.         v.push_back(node(s, e, 0, i));
  67.     }
  68.  
  69.     sort(v.begin(), v.end());
  70.  
  71.     for(int i = 0;i < v.size(); i++){
  72.         if(v[i].val == 0){
  73.             ans[v[i].pos] = query(v[i].e) - query(v[i].s - 1);
  74.         }else{
  75.             if(occs[v[i].val] != 0) update(occs[v[i].val], -1);
  76.             update(v[i].s, 1);
  77.             occs[v[i].val] = v[i].s;
  78.         }
  79.     }
  80.  
  81.     for(int i = 0; i < q; i++){
  82.         printf("%d\n", ans[i]);
  83.     }
  84.  
  85.     return 0;
  86. }
  87.  
  88.  
Time limit exceeded #stdin #stdout 5s 270400KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/eVutNI
language:
C++ (gcc 8.3)
created:
10 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!