oj.uz

답안 #543565

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
543565 2022-03-30T21:50:21 Z MilosMilutinovic Poklon (COCI17_poklon) C++14
140 / 140
 730 ms 45248 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);
		if(pos[v].size()>=4) st.modify(pos[v][pos[v].size()-4],0);
		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);
      |   ~~~~~^~~~~~~~~~~~~~~

Subtask #1
140.0 / 140.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 23792 KB Output is correct
2 Correct 13 ms 23764 KB Output is correct
3 Correct 12 ms 23764 KB Output is correct
4 Correct 16 ms 24052 KB Output is correct
5 Correct 117 ms 28080 KB Output is correct
6 Correct 119 ms 28140 KB Output is correct
7 Correct 282 ms 32440 KB Output is correct
8 Correct 426 ms 37240 KB Output is correct
9 Correct 561 ms 41576 KB Output is correct
10 Correct 730 ms 45248 KB Output is correct