fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include<ext/pb_ds/assoc_container.hpp>
  3. #include<ext/pb_ds/tree_policy.hpp>
  4. using namespace std;
  5. using namespace __gnu_pbds;
  6.  
  7. typedef long long ll;
  8. typedef unsigned long long ull;
  9.  
  10. typedef vector<int> vi;
  11. typedef vector<ll> vll;
  12. typedef vector<vi> vvi;
  13. typedef vector<vll> vvll;
  14. typedef vector<string> vs;
  15. typedef pair<int, int> pi;
  16. typedef pair<ll, ll> pll;
  17. typedef vector<pair<int, int>> vpi;
  18. typedef vector<pair<ll, ll>> vpll;
  19. typedef set<int> si;
  20. typedef set<ll> sll;
  21. typedef set<pair<int, int>> spi;
  22. typedef set<pair<ll, ll>> spll;
  23. typedef multiset<int> msi;
  24. typedef multiset<ll> msll;
  25. typedef multiset<pair<int, int>> mspi;
  26. typedef multiset<pair<ll, ll>> mspll;
  27. typedef map<int, int> mpi;
  28. typedef map<ll, ll> mpll;
  29.  
  30. typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;  // find_by_order, order_of_key, less, greater,less_equal
  31. typedef tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;
  32.  
  33. #include<iomanip>
  34. #define fastio  ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
  35. #define e    "\n"
  36. #define yes cout<<"Yes"<<e;
  37. #define no cout<<"No"<<e;
  38. #define pb   push_back
  39. #define ff     first
  40. #define ss    second
  41. #define sz    size()
  42. #define mod 1000000007  //1e9+7  1000000007 998244353
  43. #define fr(i,a,b) for(ll i=a;i<b;i++)
  44. #define fr2(i,a,b) for(ll i=a;i>=b;i--)
  45. #define coutv(v) for(auto it:v)cout<<it<<' ';cout<<e
  46. #define cinv(v) for(auto &it:v)cin>>it
  47. #define all(a) a.begin(),a.end()
  48. #define rall(a) a.rbegin(),a.rend()
  49. #define Ceil(x,y)  ((x+y-1)/y)
  50. #define INF (1LL<<62)
  51.  
  52. #define read    freopen("binary.in","r",stdin)
  53. #define write   freopen("cricket.out","w",stdout)
  54.  
  55. const double PI = acos(-1);
  56. const ll infll = LLONG_MAX;
  57. const ll mn = LLONG_MIN;
  58. const int inf = INT_MAX;
  59.  
  60. bool cmp1(pair<ll, ll> x1, pair<ll, ll> x2) {
  61.     return x1.ss < x2.ss;
  62. }
  63.  
  64. bool cmp2(pair<ll, ll> x1, pair<ll, ll> x2) {
  65.     if ( x1.ff == x2.ff ) return x1.ss < x2.ss;
  66.     return x1.ff < x2.ff;
  67. }
  68. bool cmp3(pair<ll, ll> x1, pair<ll, ll> x2) {
  69.     if ( x1.ff == x2.ff ) return x1.ss > x2.ss;
  70.     return x1.ff > x2.ff;
  71. }
  72.  
  73. void solve() {
  74.  
  75. }
  76.  
  77. int block_size = 447; //for 2e5
  78. int n, q;
  79.  
  80. struct Query {
  81.     int l, r, idx;
  82.     bool operator<(Query other) const
  83.     {
  84.         return make_pair(l / block_size, r) <
  85.                make_pair(other.l / block_size, other.r);
  86.     }
  87. };
  88.  
  89. vector<Query> Q;
  90. vi v(200005, 0);
  91. vi freq(200005, 0);
  92. int cnt=0;
  93.  
  94. void rem(int idx) {  // TODO: remove value at idx from data structure
  95.     freq[ v[idx] ]--;
  96.     if( freq[ v[idx] ] == 0 ) cnt--;
  97. }
  98. void add(int idx) {  // TODO: add value at idx from data structure
  99.     freq[ v[idx] ]++;
  100.     if( freq[ v[idx] ] == 1 ) cnt++;
  101. }
  102. ll get_answer(int val) {      // TODO: extract the current answer of the data structure
  103.     return val;
  104. }
  105.  
  106. vector<int> mo_s(vector<Query>& queries) {
  107.     vector<int> answers( (int)queries.size());
  108.     sort(queries.begin(), queries.end());
  109.  
  110.     // TODO: initialize data structure
  111.  
  112.     int cur_l = 0;
  113.     int cur_r = -1; // because of query [0, 0]
  114.     // invariant: data structure will always reflect the range [cur_l, cur_r]
  115.     for (Query q : queries) {
  116.         while (cur_l > q.l) {
  117.             cur_l--;
  118.             add(cur_l);
  119.         }
  120.         while (cur_r < q.r) {
  121.             cur_r++;
  122.             add(cur_r);
  123.         }
  124.         while (cur_l < q.l) {
  125.             rem(cur_l);
  126.             cur_l++;
  127.         }
  128.         while (cur_r > q.r) {
  129.             rem(cur_r);
  130.             cur_r--;
  131.         }
  132.         answers[q.idx] = get_answer(cnt);
  133.     }
  134.     return answers;
  135. }
  136.  
  137. int main() {
  138.     fastio
  139.     int t = 1, tc = 1;
  140.     //cin >> t;
  141.  
  142.     while ( t-- ) {
  143.         //ll n;
  144.         cin>>n>>q;
  145.         fr(i, 0, n) cin>>v[i];
  146.  
  147.         mpi mp;
  148.         int num=0;
  149.         fr(i, 0, n) {  // compression
  150.             if( mp.find( v[i] ) != mp.end() ) {
  151.                 v[i] = mp[ v[i] ];
  152.             }
  153.             else {
  154.                 num++;
  155.                 mp[ v[i] ] = num;
  156.                 v[i] = num;
  157.             }
  158.         }
  159.  
  160.  
  161.         fr(i, 0, q) {
  162.             int l, r; cin>>l>>r;
  163.             l--;
  164.             r--;
  165.             Q.pb( {l, r, i} );
  166.         }
  167.  
  168.         vi ans = mo_s( Q );
  169.         fr(i, 0, q) cout<<ans[i]<<e;
  170.  
  171.     }
  172.  
  173.  
  174.     //cout<<"Case "<<tc++<<": "<<ans<<e;
  175.  
  176.     return 0;
  177. }
  178.  
Success #stdin #stdout 0.01s 5272KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/ZQL13M
language:
C++14 (gcc 8.3)
created:
16 days 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!