Submission #1195489

#	Time	Username	Problem	Language	Result	Execution time	Memory
1195489		lopkus	Poklon (COCI17_poklon)	C++20	56 / 140	5093 ms	12228 KiB

poklon

#include <bits/stdc++.h>

#define int int64_t

const int N = 5e5 + 5;

struct fenwick {
  int t[2 * N];
  int query(int i) {
    int ans = 0;
    for(; i > 0; i -= i & - i) {
      ans += t[i];
    }
    return ans;
  }
  void update(int i, int v) {
    for(; i < N; i += i & - i) {
      t[i] += v;
    }
  }
  int query(int l, int r) {
    return query(r) - query(l - 1);
  }
}fenw;

void solve() {
  int n, q;
  std::cin >> n >> q;
  std::vector<int> a(n + 1);
  for(int i = 1; i <= n; i++) {
    std::cin >> a[i];
  }
  std::vector<int> last(n + 1);
  std::map<int,int> lst;
  for(int i = 1; i <= n; i++) {
    last[i] = lst[a[i]];
    lst[a[i]] = i;
  }
  lst.clear();
  std::vector<int> next(n + 1, n + 1);
  for(int i = n; i >= 1; i--) {
    if(lst[a[i]]) {
      next[i] = lst[a[i]];
    }
    lst[a[i]] = i;
  }
  while(q--) {
    int l, r;
    std::cin >> l >> r;
    int ans = 0;
    std::map<int, int> was;
    for(int i = r; i >= l; i--) {
      if(was[a[i]]) {
        continue;
      }
      was[a[i]] = 1;
      if(next[i] > r && last[last[i]] < l && last[i] >= l) {
        ans += 1;
      }
    }
    std::cout << ans << "\n";
  }
}

signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);

  int t = 1;
  //std::cin >> t;
  while (t--) {
      solve();
  }

  return 0;
}

• Subtask 1: 56 / 140