Submission #521353

#	Time	Username	Problem	Language	Result	Execution time	Memory
521353		arnav2004	Poklon (COCI17_poklon)	C++17	140 / 140	1162 ms	19512 KiB

poklon

#include <bits/stdc++.h>
using namespace std;
const int MX = 5e5 + 5;
const int sz = 705;
int ans = 0;
struct Node{
  int l,r,idx;
};
int A[MX];
int cnt[MX];
void add(int idx){
  cnt[A[idx]]++;
  if(cnt[A[idx]] == 2)
    ans++;
  if(cnt[A[idx]] == 3)
    ans--;
}

void remove(int idx){
  cnt[A[idx]]--;
  if(cnt[A[idx]] == 2)
    ans++;
  if(cnt[A[idx]] == 1)
    ans--;
}
signed main(){
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int N,M; cin >> N >> M;
  map<int,int> mp;
  for(int i = 0; i < N; i++){
    cin >> A[i];
    mp[A[i]];
  }
  int cur = 0;
  for(auto it : mp){
    mp[it.first] = cur++;
  }
  for(int i = 0; i < N; i++)
    A[i] = mp[A[i]];

  vector<Node> Q(M);
  for(int i = 0; i < M; i++){
    cin >> Q[i].l >> Q[i].r;
    Q[i].l--; Q[i].r--;
    Q[i].idx = i;
  }

  sort(Q.begin(), Q.end(), [&](const Node &a, const Node &b){
    if((a.l / sz) != (b.l / sz)) return (a.l / sz) < (b.l / sz);
    return ((a.l / sz) & 1 ? a.r < b.r : a.r > b.r);
  });

  int L = 0, R = -1;
  vector<int> out(M);

  for(int i = 0; i < M; i++){
    while(R < Q[i].r) add(++R);
    while(L > Q[i].l) add(--L);
    while(R > Q[i].r) remove(R--);
    while(L < Q[i].l) remove(L++);

    out[Q[i].idx] = ans;
  }
  for(int i = 0; i < M; i++)
    cout << out[i] << '\n';
  return 0;
}

• Subtask 1: 140 / 140