Submission #363486

# Submission time Handle Problem Language Result Execution time Memory
363486 2021-02-06T08:42:03 Z hivakarami Fish (IOI08_fish) C++14
13 / 100
779 ms 38480 KB
#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 + 10;
const int sq = 100;
const ll mod = 1e9 + 7;
const int inf = 1e9;

ll seg[4*N], m, cnt[N];
int n, k, f[N];
bool last[N];
vector<ll> ind[N], v;
vector<pair<ll, 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 && e <= r)
		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, ll 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(ll p)
{
	p = all[p].f;

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

 
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++)
	{	
		ll 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 >= i && all[i].f >= 2ll * 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);	
		
		
		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;
}
# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 12140 KB Output isn't correct
# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 12140 KB Output isn't correct
# Verdict Execution time Memory Grader output
1 Correct 9 ms 12140 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 9 ms 12140 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 9 ms 12268 KB Output is correct
2 Incorrect 11 ms 12140 KB Output isn't correct
# Verdict Execution time Memory Grader output
1 Correct 11 ms 12140 KB Output is correct
2 Incorrect 184 ms 26064 KB Output isn't correct
# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 12160 KB Output isn't correct
# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 12268 KB Output isn't correct
# Verdict Execution time Memory Grader output
1 Incorrect 96 ms 18908 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 11 ms 12268 KB Output is correct
2 Correct 12 ms 12396 KB Output is correct
3 Incorrect 13 ms 12396 KB Output isn't correct
# Verdict Execution time Memory Grader output
1 Correct 153 ms 21672 KB Output is correct
2 Incorrect 255 ms 26192 KB Output isn't correct
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 255 ms 26576 KB Output is correct
2 Incorrect 245 ms 27088 KB Output isn't correct
# Verdict Execution time Memory Grader output
1 Correct 132 ms 21972 KB Output is correct
2 Incorrect 252 ms 27216 KB Output isn't correct
# Verdict Execution time Memory Grader output
1 Correct 246 ms 26192 KB Output is correct
# Verdict Execution time Memory Grader output
1 Incorrect 291 ms 28376 KB Output isn't correct
# Verdict Execution time Memory Grader output
1 Incorrect 240 ms 25296 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 680 ms 34940 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 455 ms 35764 KB Output is correct
2 Incorrect 532 ms 32720 KB Output isn't correct
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 779 ms 38480 KB Output isn't correct
2 Halted 0 ms 0 KB -