Submission #111578

#	Time	Username	Problem	Language	Result	Execution time	Memory
111578		vex	Poklon (COCI17_poklon)	C++14	140 / 140	2579 ms	13180 KiB

poklon

#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 / 140