Submission #1103786

#	Time	Username	Problem	Language	Result	Execution time	Memory
1103786		_rain_	Fish (IOI08_fish)	C++14	0 / 100	239 ms	32596 KiB

fish

#include<bits/stdc++.h>
using namespace std;

#define name "main"
typedef long long ll;

const int N = (int)5e5;
struct Node{
	int len;
	int gem;
	bool operator < (const Node& other) const{
		return len < other.len;
	}
} p[N+2];
int n,k,MOD;
	int add(int a , int b){
		return a + b >= MOD ? a + b - MOD : a + b;
	}
	int sub(int a,int b){
		return a - b < 0 ? a - b + MOD : a - b;
	}
	int mul(int a, int b){
		return (ll)a*b%MOD;
	}
int id[N+2];
bool last[N+2]={},vis[N+2]={};
vector<int> bag[N+2];
int st[N*4+2];
#define lef(id) id*2
#define rig(id) id*2+1
void build(int id,int l,int r){
	if (l==r) st[id]=1;
	else{
		int m=l+r>>1;
		build(lef(id),l,m);
		build(rig(id),m+1,r);
		st[id]=1;
	}
	return;
}
void upd(int id,int l,int r,int pos,int t){
	if (l>pos||r<pos) return;
	if (l==r){
		st[id] = add(st[id],t);
	}
	else{
		int m=l+r>>1;
		if (l<=m) upd(lef(id),l,m,pos,t);
		if (m<r) upd(rig(id),m+1,r,pos,t);
		st[id]=mul(st[lef(id)],st[rig(id)]);
	}
	return;
}
int Get(int id,int l,int r,int u,int v){
	if (l>v||r<u) return 1;
	if (u<=l&&r<=v) return st[id];
	int m=l+r>>1;
	return mul(Get(lef(id),l,m,u,v),Get(rig(id),m+1,r,u,v));
}

int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin>>n>>k>>MOD;
	for (int i = 1; i <= n; ++i){
		cin>>p[i].len>>p[i].gem;
	}
	sort(p+1,p+n+1);
	int cnt=n;
	for (int i = n; i >= 1; --i){
		if (!vis[p[i].gem]) {
			id[p[i].gem] = cnt--;
			vis[p[i].gem] = true;
			last[i] = true;
		}
	}
	build(1,1,n);
	int ans=0;
	// cout<<"(DEBUG)\n";
	// for (int i=1;i<=n;++i) cout << p[i].len << ' ' << p[i].gem << ' ' << id[p[i].gem] << '\n';
	// cout<<"(END-DEBUGGING)\n";
	for (int i = 1 , l = 1; i <= n; ++i){
		while (l <= i && p[l].len * 2 <= p[i].len){
			upd(1,1,n,id[p[l].gem],1);
			++l;
		}
		if (last[i]) ans=add(ans,Get(1,1,n,1,id[p[i].gem]));
	}
	cout<<ans;
	exit(0);
}

Compilation message (stderr)

fish.cpp: In function 'void build(int, int, int)':
fish.cpp:34:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   34 |   int m=l+r>>1;
      |         ~^~
fish.cpp: In function 'void upd(int, int, int, int, int)':
fish.cpp:47:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   47 |   int m=l+r>>1;
      |         ~^~
fish.cpp: In function 'int Get(int, int, int, int, int)':
fish.cpp:57:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   57 |  int m=l+r>>1;
      |        ~^~

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