Submission #410362

#	Time	Username	Problem	Language	Result	Execution time	Memory
410362		Jasiekstrz	Fish (IOI08_fish)	C++17	93 / 100	617 ms	42044 KiB

fish

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N=5e5;
const int P=53e4;
int mod;
struct T
{
	int ilo,sum;
	T() : ilo(1),sum(0) {};
	void operator++()
	{
		ilo++;
		sum++;
		return;
	}
	T operator+(const T &oth)
	{
		T tmp;
		tmp.ilo=(ilo*oth.ilo)%mod;
		tmp.sum=(sum*oth.ilo+oth.sum)%mod;
		return tmp;
	}
};
pair<int,int> t[N+10];
int ch[N+10];
vector<int> first_inter[N+10];
int first_val[N+10];
int nxt_tmp[N+10];
int nxt[N+10];
int pot;
T tree[2*P+10];
void add(int x)
{
	x+=pot-1;
	++tree[x];
	for(x/=2;x>0;x/=2)
		tree[x]=tree[2*x]+tree[2*x+1];
	return;
}
T read(int l,int r)
{
	T ansl,ansr;
	for(l+=pot-1,r+=pot-1;l<=r;l/=2,r/=2)
	{
		if(l%2==1)
			ansl=ansl+tree[l++];
		if(r%2==0)
			ansr=tree[r--]+ansr;
	}
	return ansl+ansr;
}
int solve(int x)
{
	int ans=read(x,pot).ilo%mod;
	int bg=1,en=x-1;
	while(bg<en)
	{
		int mid=(bg+en)/2;
		if(first_val[mid]>=2*nxt[x])
			bg=mid+1;
		else
			en=mid;
	}
	if(first_val[bg]<2*nxt[x])
		ans+=read(bg,x-1).sum*read(x+1,pot).ilo;
	//cerr<<x<<" "<<ans<<"\n";
	return ans%mod;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n,k;
	cin>>n>>k>>mod;
	for(pot=1;pot<k;pot*=2);
	for(int i=1;i<=n;i++)
		cin>>t[i].fi>>t[i].se;
	sort(t+1,t+n+1);
	reverse(t+1,t+n+1);
	for(int i=1,j=0;i<=n;i++)
	{
		if(ch[t[i].se]==0)
		{
			ch[t[i].se]=++j;
			first_val[j]=t[i].fi;
		}
		t[i].se=ch[t[i].se];
	}
	int jj=1;
	for(int i=1;i<=n;i++)
	{
		while(jj<=k && t[i].fi*2<=first_val[jj])
		{
			first_inter[i].push_back(jj);
			nxt[jj]=nxt_tmp[jj];
			jj++;
		}
		nxt_tmp[t[i].se]=t[i].fi;
	}
	int ans=0;
	while(jj<=k)
		ans=(ans+solve(jj++))%mod;
	for(int i=n;i>=1;i--)
	{
		add(t[i].se);
		for(auto v:first_inter[i])
		{
			ans+=solve(v);
			ans%=mod;
		}
	}
	cout<<ans<<"\n";
	return 0;
}

• Subtask 1: 4 / 4
• Subtask 2: 4 / 4
• Subtask 3: 4 / 4
• Subtask 4: 4 / 4
• Subtask 5: 4 / 4
• Subtask 6: 5 / 5
• Subtask 7: 6 / 6
• Subtask 8: 6 / 6
• Subtask 9: 6 / 6
• Subtask 10: 6 / 6
• Subtask 11: 0 / 7
• Subtask 12: 7 / 7
• Subtask 13: 7 / 7
• Subtask 14: 5 / 5
• Subtask 15: 5 / 5
• Subtask 16: 5 / 5
• Subtask 17: 5 / 5
• Subtask 18: 5 / 5
• Subtask 19: 5 / 5