oj.uz

Submission #410367

# Submission time Handle Problem Language Result Execution time Memory
410367 2021-05-22T15:13:29 Z Jasiekstrz Fish (IOI08_fish) C++17
100 / 100
 610 ms 34896 KB 
#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++;
		ilo%=mod;
		sum++;
		sum%=mod;
		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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 20300 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 20384 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 20284 KB Output is correct

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 20300 KB Output is correct

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 20300 KB Output is correct
2 Correct 14 ms 20300 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 20300 KB Output is correct
2 Correct 223 ms 25172 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 20300 KB Output is correct

Subtask #8
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 20428 KB Output is correct

Subtask #9
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 22824 KB Output is correct
2 Correct 125 ms 23156 KB Output is correct

Subtask #10
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 20428 KB Output is correct
2 Correct 16 ms 20536 KB Output is correct
3 Correct 16 ms 20448 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 23584 KB Output is correct
2 Correct 263 ms 25156 KB Output is correct
3 Correct 267 ms 31072 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 230 ms 25116 KB Output is correct
2 Correct 267 ms 25240 KB Output is correct

Subtask #13
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 23736 KB Output is correct
2 Correct 284 ms 25432 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 249 ms 25156 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 309 ms 25520 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 267 ms 25492 KB Output is correct
2 Correct 334 ms 26316 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 399 ms 29136 KB Output is correct
2 Correct 297 ms 27912 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 345 ms 27716 KB Output is correct
2 Correct 378 ms 28856 KB Output is correct
3 Correct 393 ms 30856 KB Output is correct
4 Correct 381 ms 28864 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 473 ms 31164 KB Output is correct
2 Correct 418 ms 30920 KB Output is correct
3 Correct 405 ms 31028 KB Output is correct
4 Correct 610 ms 34896 KB Output is correct