제출 #543561

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
543561		MilosMilutinovic	Poklon (COCI17_poklon)	C++14	0 / 140	680 ms	56480 KiB

poklon

#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;
}

컴파일 시 표준 에러 (stderr) 메시지

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);
      |   ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 0 / 140