oj.uz

Submission #521353

# Submission time Handle Problem Language Result Execution time Memory
521353 2022-02-01T22:34:22 Z arnav2004 Poklon (COCI17_poklon) C++17
140 / 140
 1162 ms 19512 KB 
#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.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 2 ms 324 KB Output is correct
4 Correct 7 ms 452 KB Output is correct
5 Correct 135 ms 3800 KB Output is correct
6 Correct 137 ms 3852 KB Output is correct
7 Correct 341 ms 7872 KB Output is correct
8 Correct 582 ms 11844 KB Output is correct
9 Correct 830 ms 15684 KB Output is correct
10 Correct 1162 ms 19512 KB Output is correct