oj.uz

Submission #410362

# Submission time Handle Problem Language Result Execution time Memory
410362 2021-05-22T15:07:42 Z Jasiekstrz Fish (IOI08_fish) C++17
93 / 100
 617 ms 42044 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++;
		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.0 / 4.0

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

Subtask #2
4.0 / 4.0

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

Subtask #3
4.0 / 4.0

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

Subtask #4
4.0 / 4.0

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

Subtask #5
4.0 / 4.0

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

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 20416 KB Output is correct
2 Correct 199 ms 30312 KB Output is correct

Subtask #7
6.0 / 6.0

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

Subtask #8
6.0 / 6.0

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

Subtask #9
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 24344 KB Output is correct
2 Correct 117 ms 25412 KB Output is correct

Subtask #10
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 20428 KB Output is correct
2 Correct 15 ms 20452 KB Output is correct
3 Correct 15 ms 20536 KB Output is correct

Subtask #11
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 26720 KB Output is correct
2 Incorrect 265 ms 30944 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 225 ms 30300 KB Output is correct
2 Correct 269 ms 31408 KB Output is correct

Subtask #13
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 27152 KB Output is correct
2 Correct 291 ms 31428 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 247 ms 30632 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 302 ms 32100 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 280 ms 30756 KB Output is correct
2 Correct 361 ms 33220 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 415 ms 35584 KB Output is correct
2 Correct 300 ms 31548 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 344 ms 32116 KB Output is correct
2 Correct 377 ms 35816 KB Output is correct
3 Correct 401 ms 36500 KB Output is correct
4 Correct 387 ms 35520 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 478 ms 38284 KB Output is correct
2 Correct 399 ms 37360 KB Output is correct
3 Correct 420 ms 38436 KB Output is correct
4 Correct 617 ms 42044 KB Output is correct