Submission #226510

#	Time	Username	Problem	Language	Result	Execution time	Memory
226510		quocnguyen1012	Poklon (COCI17_poklon)	C++14	140 / 140	2078 ms	21868 KiB

poklon

#include <bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define ar array

using namespace std;
typedef long long ll;
typedef pair<int, int> ii;

const int maxn = 5e5 + 5, inf = 1e9;

vector<ar<int, 3>> query;
int N, Q;
int a[maxn], cnt[maxn], res[maxn], ans = 0;
vector<int> val;

void add(int i)
{
  if(cnt[a[i]] == 2) --ans;
  cnt[a[i]]++;
  if(cnt[a[i]] == 2) ++ans;
}

void del(int i)
{
  if(cnt[a[i]] == 3) ++ans;
  cnt[a[i]]--;
  if(cnt[a[i]] == 1) --ans;
}

void answer(int l, int r)
{
  static int nl = 0, nr = 0;
  if(nl == 0){
    for(int i = l; i <= r; ++i)
      add(i);
    nl = l; nr = r;
    return;
  }
  for(int i = l; i < nl; ++i)
    add(i);
  for(int i = nl; i < l; ++i)
    del(i);
  for(int i = nr + 1; i <= r; ++i)
    add(i);
  for(int i = r + 1; i <= nr; ++i)
    del(i);
  nl = l; nr = r;
}

signed main(void)
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  #ifdef LOCAL
    freopen("A.INP", "r", stdin);
    freopen("A.OUT", "w", stdout);
  #endif // LOCAL
  cin >> N >> Q; query.resize(Q);
  for(int i = 1; i <= N; ++i){
    cin >> a[i];
    val.eb(a[i]);
  }
  for(int i = 0; i < Q; ++i){
    cin >> query[i][0] >> query[i][1];
    query[i][2] = i;
  }
  sort(val.begin(), val.end()); val.erase(unique(val.begin(), val.end()), val.end());
  for(int i = 1; i <= N; ++i){
    a[i] = lower_bound(val.begin(), val.end(), a[i]) - val.begin();
  }
  int sq = sqrt(N);
  sort(query.begin(), query.end(), [&](ar<int, 3> x, ar<int, 3> y){
    if(x[0] / sq == y[0] / sq) return x[1] < y[1];
    return x[0] / sq < y[0] / sq;
  });
  for(auto & all : query){
    answer(all[0], all[1]);
    res[all[2]] = ans;
  }
  for(int i = 0; i < Q; ++i)
    cout << res[i] << '\n';
}

• Subtask 1: 140 / 140