oj.uz

Submission #363478

# Submission time Handle Problem Language Result Execution time Memory
363478 2021-02-06T08:31:49 Z hivakarami Fish (IOI08_fish) C++14
13 / 100
 761 ms 45264 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, int r)
{
	p = all[p].f;

	int l = 0;
	
	while(l + 1 < r)
	{
		int mid = (l + r) / 2;
		ll len = v[mid];
		if(len >= 2ll*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++)
	{	
		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, 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.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 12140 KB Output isn't correct

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 12140 KB Output isn't correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 12140 KB Output is correct

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12140 KB Output is correct

Subtask #5
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12140 KB Output is correct
2 Incorrect 10 ms 12140 KB Output isn't correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12140 KB Output is correct
2 Incorrect 193 ms 31208 KB Output isn't correct

Subtask #7
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 12156 KB Output isn't correct

Subtask #8
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 12268 KB Output isn't correct

Subtask #9
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 103 ms 20572 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 6.0

# 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 12544 KB Output isn't correct

Subtask #11
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 24972 KB Output is correct
2 Incorrect 246 ms 32356 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #12
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 232 ms 32096 KB Output is correct
2 Incorrect 241 ms 33232 KB Output isn't correct

Subtask #13
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 25552 KB Output is correct
2 Incorrect 275 ms 33360 KB Output isn't correct

Subtask #14
5.0 / 5.0

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

Subtask #15
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 293 ms 34896 KB Output isn't correct

Subtask #16
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 238 ms 30544 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #17
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 612 ms 41424 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #18
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 470 ms 40144 KB Output is correct
2 Incorrect 513 ms 39888 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #19
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 761 ms 45264 KB Output isn't correct
2 Halted 0 ms 0 KB -