Submission #543561

# Submission time Handle Problem Language Result Execution time Memory
543561 2022-03-30T21:48:09 Z MilosMilutinovic Poklon (COCI17_poklon) C++14
0 / 140
680 ms 56480 KB
#include <bits/stdc++.h>
#define SZ 500005
#define BT 512*1024*2
using namespace std;
typedef pair <int,int> P;

struct segtree
{
	int st[BT];
	int mum=1;
	void init(int n)
	{
		while(mum<n) mum<<=1;
	}
	void modify(int v,int l,int r,int i,int x)
	{
		if(l==r) { st[v]=x; return; }
		int m=(l+r)/2;
		if(i<=m) modify(v*2+1,l,m,i,x);
		else modify(v*2+2,m+1,r,i,x);
		st[v]=st[v*2+1]+st[v*2+2];
	}
	void modify(int i,int v)
	{
		modify(0,1,mum,i,v);
	}
	int query(int ql,int qr,int v,int l,int r)
	{
		if(l>qr||r<ql) return 0;
		if(ql<=l&&r<=qr) return st[v];
		int m=(l+r)/2;
		return query(ql,qr,v*2+1,l,m)+query(ql,qr,v*2+2,m+1,r);
	}
	int query(int l,int r)
	{
		return query(l,r,0,1,mum);
	}
};
segtree st;
int n,q,a[SZ],ans[SZ];
vector <P> Qs[SZ];
vector <int> pos[SZ];
void compress()
{
	vector <int> vec;
	for(int i=1;i<=n;i++) vec.push_back(a[i]);
	sort(vec.begin(),vec.end());
	vec.erase(unique(vec.begin(),vec.end()),vec.end());
	for(int i=1;i<=n;i++)
	{
		a[i]=lower_bound(vec.begin(),vec.end(),a[i])-vec.begin();
	}
}
int main()
{
	scanf("%d %d",&n,&q);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=q;i++)
	{
		int l,r;
		scanf("%d %d",&l,&r);
		Qs[r].push_back(P(l,i));
	}
	compress();
	st.init(n);
	for(int i=1;i<=n;i++)
	{
		int v=a[i];
		pos[v].push_back(i);
		if(pos[v].size()>=2) st.modify(pos[v][pos[v].size()-2],1);
		if(pos[v].size()>=3) st.modify(pos[v][pos[v].size()-3],-1);
		for(auto qq:Qs[i]) ans[qq.second]=st.query(qq.first,i);
	}
	for(int i=1;i<=q;i++) printf("%d\n",ans[i]);
	return 0;
}

Compilation message

poklon.cpp: In function 'int main()':
poklon.cpp:56:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |  scanf("%d %d",&n,&q);
      |  ~~~~~^~~~~~~~~~~~~~~
poklon.cpp:57:29: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |  for(int i=1;i<=n;i++) scanf("%d",&a[i]);
      |                        ~~~~~^~~~~~~~~~~~
poklon.cpp:61:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |   scanf("%d %d",&l,&r);
      |   ~~~~~^~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 23760 KB Output isn't correct
2 Incorrect 13 ms 23764 KB Output isn't correct
3 Incorrect 12 ms 23788 KB Output isn't correct
4 Incorrect 16 ms 24064 KB Output isn't correct
5 Incorrect 114 ms 29948 KB Output isn't correct
6 Incorrect 156 ms 30004 KB Output isn't correct
7 Incorrect 250 ms 36644 KB Output isn't correct
8 Incorrect 390 ms 43920 KB Output isn't correct
9 Incorrect 536 ms 50380 KB Output isn't correct
10 Incorrect 680 ms 56480 KB Output isn't correct