oj.uz

Submission #111578

# Submission time Handle Problem Language Result Execution time Memory
111578 2019-05-15T15:58:01 Z vex Poklon (COCI17_poklon) C++14
140 / 140
 2579 ms 13180 KB 
#include<bits/stdc++.h>
#define maxn 500005
using namespace std;

int blok;
struct qry{
	int sol;
	int l;
	int r;
	int ind;
};
qry up[maxn];
bool cmp1(qry a,qry b)
{
	int bl1=a.l/blok;
	int bl2=b.l/blok;
	pair<int,int> p1={bl1,a.r},p2={bl2,b.r};
	return p1<p2;
}
bool cmp2(qry a,qry b)
{
	return a.ind<b.ind;
}

int n,q;
int a[maxn];

int tre=0;
int poj[maxn];
void dodaj(int x)
{
	if(poj[a[x]]==2)tre--;
	poj[a[x]]++;
	if(poj[a[x]]==2)tre++;
}
void obrisi(int x)
{
	if(poj[a[x]]==2)tre--;
	poj[a[x]]--;
	if(poj[a[x]]==2)tre++;
}

map<int,int>kmpr;
int b[maxn];
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	
	cin>>n>>q;
	blok=sqrt(n);
	for(int i=1;i<=n;i++)cin>>a[i];
  	
  	for(int i=0;i<n;i++)b[i]=a[i+1];
  	sort(b,b+n);
  	int broj=1;
  	for(int i=0;i<n;i++)
    {
      	if(!kmpr[a[i]])
        {
          	kmpr[a[i]]=broj;
         	broj++;
        }
    }
  	for(int i=1;i<=n;i++)a[i]=kmpr[a[i]];
	
    for(int i=0;i<q;i++)
	{
		cin>>up[i].l>>up[i].r;
		up[i].ind=i;	
	}
	
	sort(up,up+q,cmp1);
	int currL=1;
	int currR=n;
	for(int i=1;i<=n;i++)dodaj(i);
	for(int i=0;i<q;i++)
	{
		while(currL<up[i].l)
		{
			obrisi(currL);
			currL++;
		}
		while(currL>up[i].l)
		{
			currL--;
			dodaj(currL);
		}
		while(currR<up[i].r)
		{
			currR++;
			dodaj(currR);
		}
		while(currR>up[i].r)
		{
			obrisi(currR);
			currR--;
		}
		up[i].sol=tre;
		
		//cout<<up[i].l<<","<<up[i].r<<" "<<currL<<","<<currR<<" "<<tre<<endl;
		//for(auto x:poj)cout<<x.first<<","<<x.second<<" ";
		//cout<<endl<<endl;
	}
	
	sort(up,up+q,cmp2);
	for(int i=0;i<q;i++)cout<<up[i].sol<<endl;
	return 0;
}

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 17 ms 512 KB Output is correct
5 Correct 359 ms 2936 KB Output is correct
6 Correct 355 ms 2892 KB Output is correct
7 Correct 754 ms 5520 KB Output is correct
8 Correct 1192 ms 8192 KB Output is correct
9 Correct 1933 ms 10636 KB Output is correct
10 Correct 2579 ms 13180 KB Output is correct