Submission #521354

#	Time	Username	Problem	Language	Result	Execution time	Memory
521354		arnav2004	Poklon (COCI17_poklon)	C++17	140 / 140	1131 ms	13124 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;
  vector<int> B(N);
  for(int i = 0; i < N; i++){
    cin >> A[i];
    B[i] = A[i];
  }

  sort(B.begin(), B.end());
  B.erase(unique(B.begin(), B.end()), B.end());
  
  for(int i = 0; i < N; i++)
    A[i] = lower_bound(B.begin(), B.end(), A[i]) - B.begin();

  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