제출 #891701

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
891701		ind1v	Poklon (COCI17_poklon)	C++11	140 / 140	296 ms	57796 KiB

poklon

#include <bits/stdc++.h>

using namespace std;

const int N = 5e5 + 5;

struct fenwick_tree {
  int f[N];
  
  fenwick_tree() {
    memset(f, 0, sizeof(f));
  }
  
  void upd(int i, int x) {
    for (; i < N; i += i & -i) {
      f[i] += x;
    }
  }
  
  int get(int i) {
    int res = 0;
    for (; i >= 1; i -= i & -i) {
      res += f[i];
    }
    return res;
  }
  
  int get(int l, int r) {
    return get(r) - get(l - 1);
  }
};

int n, q;
int a[N];
int ans[N];
vector<int> v;
pair<int, int> p[N];
vector<pair<int, int>> que[N];
fenwick_tree ft;
vector<int> idx[N];

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> q;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  copy(a + 1, a + n + 1, back_inserter(v));
  sort(v.begin(), v.end());
  v.erase(unique(v.begin(), v.end()), v.end());
  for (int i = 1; i <= n; i++) {
    a[i] = lower_bound(v.begin(), v.end(), a[i]) - v.begin();
  }
  for (int i = 0; i < N; i++) {
    p[i] = {-1, -1};
  }
  for (int i = 1; i <= q; i++) {
    int l, r;
    cin >> l >> r;
    que[r].emplace_back(l, i);
  }
  for (int i = 1; i <= n; i++) {
    if (idx[a[i]].size() >= 2) {
      ft.upd(idx[a[i]][idx[a[i]].size() - 2], -1);
    }
    if (idx[a[i]].size() >= 3) {
      ft.upd(idx[a[i]][idx[a[i]].size() - 3], +1);
    }
    idx[a[i]].emplace_back(i);
    if (idx[a[i]].size() >= 2) {
      ft.upd(idx[a[i]][idx[a[i]].size() - 2], +1);
    }
    if (idx[a[i]].size() >= 3) {
      ft.upd(idx[a[i]][idx[a[i]].size() - 3], -1);
    }
    for (auto x : que[i]) {
      ans[x.second] = ft.get(x.first, i);
    }
  }
  for (int i = 1; i <= q; i++) {
    cout << ans[i] << '\n';
  }
  return 0;
}

• Subtask 1: 140 / 140