Submission #1182723

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182723		zNatsumi	Poklon (COCI17_poklon)	C++20	140 / 140	295 ms	32788 KiB

poklon

#include <bits/stdc++.h>

using namespace std;

using ii = pair<int, int>;

const int N = 5e5 + 5;

int n, q, a[N], res[N], pre[N];
vector<ii> query[N];

namespace bit{
  int bit[N], cur[N];

  void update(int i, int x){
    if(!i) return;
    int tmp = x - cur[i]; cur[i] = x;
    for(; i <= n; i += i & -i) bit[i] += tmp;
  }
  int pref(int i){
    int res = 0;
    for(; i > 0; i -= i & -i) res += bit[i];
    return res;
  }
  int get(int l, int r){ return pref(r) - pref(l - 1); }
}

int32_t main(){
  cin.tie(0)->sync_with_stdio(0);
 
  cin >> n >> q;
  for(int i = 1; i <= n; i++) cin >> a[i];
  for(int i = 1; i <= q; i++){
    int l, r; cin >> l >> r;
    query[r].push_back({l, i});
  }
  map<int, int> lst;
  for(int i = 1; i <= n; i++){
    pre[i] = lst[a[i]];
    lst[a[i]] = i;
  }

  for(int i = 1; i <= n; i++){
    bit::update(pre[i], 1);
    bit::update(pre[pre[i]], -1);
    bit::update(pre[pre[pre[i]]], 0);
    for(auto [l, id] : query[i]) res[id] = bit::get(l, i);
  }
  for(int i = 1; i <= q; i++) cout << res[i] << "\n";
}

• Subtask 1: 140 / 140