oj.uz

Submission #111575

# Submission time Handle Problem Language Result Execution time Memory
111575 2019-05-15T15:51:57 Z vex Poklon (COCI17_poklon) C++14
84 / 140
 5000 ms 10232 KB 
/**17:22**/
#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;
unordered_map<int,int>poj;
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++;
}

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<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
84.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 29 ms 640 KB Output is correct
5 Correct 2044 ms 2488 KB Output is correct
6 Correct 2153 ms 2472 KB Output is correct
7 Execution timed out 5080 ms 4708 KB Time limit exceeded
8 Execution timed out 5088 ms 6352 KB Time limit exceeded
9 Execution timed out 5006 ms 8312 KB Time limit exceeded
10 Execution timed out 5014 ms 10232 KB Time limit exceeded