oj.uz

Submission #260521

# Submission time Handle Problem Language Result Execution time Memory
260521 2020-08-10T12:40:45 Z sckmd Poklon (COCI17_poklon) C++14
140 / 140
 2023 ms 12384 KB 
#include <bits/stdc++.h>

using namespace std;
#define MAXN 500005
int a[MAXN];
map <int,int> mp;
int hsh = 0;
int ans[MAXN];

struct que
{
  int l,r,id;
};
que queries[MAXN];
int BLOCK;
int cnt[MAXN];

bool cmp(que qa,que qb)
{
  if(qa.l/BLOCK != qb.l/BLOCK)return qa.l < qb.l;
  return qa.r < qb.r;
}

int res = 0;

void pl(int br)
{
  //++
  if(cnt[br]==2)res--;
  cnt[br]++;
  if(cnt[br]==2)res++;
}
void mn(int br)
{
  //--
  if(cnt[br]==2)res--;
  cnt[br]--;
  if(cnt[br]==2)res++;
}

int main()
{
  ios_base::sync_with_stdio(false);
  int n,q;
  cin >> n >> q;
  BLOCK = sqrt(n);
  for(int i = 1; i <= n; i++)
  {
	cin >> a[i];
    if(!mp[a[i]])mp[a[i]]=++hsh;
    a[i]=mp[a[i]];
  }
  for(int i = 0; i < q; i++)cin >> queries[i].l >> queries[i].r,queries[i].id=i;
  sort(queries,queries+q,cmp);
  int L = 1;
  int R = n;
  for(int i = 1; i <= n; i++)pl(a[i]);
  for(int i = 0; i < q; i++)
  {
    int l = queries[i].l;
    int r = queries[i].r;
    int idx = queries[i].id;
    while(L < l)mn(a[L]),L++;
    while(L > l)L--,pl(a[L]);
    while(R > r)mn(a[R]),R--;
    while(R < r)R++,pl(a[R]);
    ans[idx]=res;
  }
  for(int i = 0; i < q; i++)cout << ans[i] << "\n";
  return 0;
}

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 6 ms 512 KB Output is correct
5 Correct 224 ms 3960 KB Output is correct
6 Correct 219 ms 3960 KB Output is correct
7 Correct 570 ms 6392 KB Output is correct
8 Correct 1000 ms 8500 KB Output is correct
9 Correct 1470 ms 10588 KB Output is correct
10 Correct 2023 ms 12384 KB Output is correct