제출 #363472

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
363472		hivakarami	Fish (IOI08_fish)	C++14	0 / 100	367 ms	65540 KiB

fish

#include<bits/stdc++.h>
 
using namespace std;
 
typedef long long int ll;
typedef long double ld;
#define f first
#define s second
 
const int N = 5e5 + 100;
const int sq = 100;
const ll mod = 1e9 + 7;
const int inf = 1e9;

ll seg[4*N];
int n, k, m, f[N], cnt[N];
bool last[N];
vector<int> ind[N], v;
vector<pair<int, int>> all;

ll get(int l, int r, int b = 0, int e = k, int id = 1)
{
	if(r <= b || e <= l)
		return 1;
	
	if(l <= b && r <= e)
		return seg[id];
	
	int mid = (b + e) / 2;
	return (get(l, r, b, mid, id*2) * get(l, r, mid, e, id*2+1))%m;	
		
}


void upd(int x, int val, int b = 0, int e = k, int id = 1)
{
	if(b + 1 == e)
	{
		seg[id] = val%m;
		return;
	}
	
	int mid = (b + e) / 2;
	if(x < mid)
		upd(x, val, b, mid, id*2);
	else
		upd(x, val, mid, e, id*2+1);

	seg[id] = (seg[id*2] * seg[id*2+1]) % m;		
}



inline void add(int r)
{
	cnt[f[r]]++;
	upd(f[r], cnt[f[r]]);
}

inline int find(int p, int r)
{
	p = all[p].f;

	int l = 0;
	
	while(l + 1 < r)
	{
		int mid = (l + r) / 2;
		int len = v[mid];
		if(len >= 2*p)
			l = mid;
		else
			r = mid;
	}
	return l+1;
	
}

 
int main()
{
    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);	

	cin >> n >> k >> m;
	//m = mod;

	for(int i = 0; i < n; i++)
	{	
		int l, c;
		cin >> l >> c;
		
		all.push_back({l, c});
		f[c] = -1;
	}
	
	sort(all.begin(), all.end());
	reverse(all.begin(), all.end());
	
	//cout << "////////" << endl;
	for(int i = 0; i < n; i++)
	{
		int c = all[i].s;
		ind[c].push_back(i);
		if(f[c] == -1)
		{
			f[c] = v.size();
			v.push_back(all[i].f);
			//cout << c << ' ' << f[c] << ' ' << all[i].f << endl;
			add(c);
			last[i] = true;
		}
		
		//cout << all[i].f << ' ' << c << endl;
	}
	//cout << "///////" << endl;
		
	ll ans = 0;
	
	int j = n-1;
	for(int i = n-1; i >= 0; i--)
	{
		int c = all[i].s;
		while(j >= 0 && all[i].f >= 2 * all[j].f)
		{
			add(all[j].s);
			j--;
		}
		
		if(!last[i])
			continue;
		
		
		int x = upper_bound(ind[c].begin(), ind[c].end(), j) - ind[c].begin();
		x--;
		x = ind[c][x];
		x = find(x, f[c]+1);	
		
		
		ll p1 = get(f[c]+1, k), p2 = get(x, f[c]);
		ll t = (cnt[f[c]] - 1);
		ll res = (p1 * t)%m + (p1 * p2)%m;
		
		
		//cout << p1 << ' ' <<  p2  << ' ' << t << ' ' << res << endl << endl; 
		
		ans = (ans + res) % m;
		
		
		
		
	}
		

	cout << ans << endl;	
 	
	return 0;
}

• 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