oj.uz

답안 #837943

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
837943 2023-08-25T21:03:24 Z caganyanmaz Fish (IOI08_fish) C++17
95 / 100
 848 ms 65536 KB 
#include <bits/stdc++.h>
#define pb push_back
#define mp(x...) array<int, 2>({x})
using namespace std;

//#define DEBUGGING
#ifdef DEBUGGING
#include "../debug.h"
#else
#define debug(x...) void(42)
#endif

constexpr static int MXN = 5e5;
constexpr static int MXST = MXN<<1;
constexpr static int INF = 1e9;
int MOD, n, k;
int add() { return 0; }
int mul() { return 1; }
template<typename... V>
int add(int a, V... v) { return (a+add(v...)) % MOD; }
template<typename... V>
int mul(int64_t a, V... v) { return (a*mul(v...)) % MOD; }
int st[MXST];
int bound[MXN];
array<int, 2> v[MXN];


void update(int i, int val) { for (st[i+=k]+=val;i>1;i>>=1) st[i>>1] = mul(st[i], st[i^1]); }
int query(int l, int r)
{
	int res = 1;
	for (l+=k,r+=k;l<r;l>>=1,r>>=1)
	{
		if (l&1) res = mul(res, st[l++]);
		if (r&1) res = mul(res, st[--r]);
	}
	return res;
}

array<int, 2> last[MXN];
set<int> pos[MXN];
int p[MXN];
void manage_types()
{
	vector<int> a;
	for (int i = 0; i < n; i++)
		a.pb(v[i][1]);
	sort(a.begin(), a.end());
	auto it = unique(a.begin(), a.end());
	a.erase(it, a.end());
	for (int i = 0; i < n; i++)
		v[i][1] = lower_bound(a.begin(), a.end(), v[i][1]) - a.begin();
	for (int i = 0; i < n; i++)
		last[v[i][1]] = {i, v[i][1]};
	sort(last, last + k);
	for (int i = 0; i < k; i++)
		p[last[i][1]] = k-i-1;
	for (int i = 0; i < n; i++)
		v[i][1] = -p[v[i][1]];
	sort(v, v + n);
	for (int i = 0; i < n; i++)
		v[i][1] = -v[i][1];
}

void manage_pos()
{
	for (int i = 0; i < n; i++)
		pos[v[i][1]].insert(v[i][0]);
}

set<array<int, 2>> ee;

int main()
{
	cin >> n;
	cin >> k;
	cin >> MOD;
	for (int i = 0; i < n; i++)
		cin >> v[i][0] >> v[i][1];
	sort(v, v + n);
	fill(st, st + 2*k, 1);
	manage_types();
	manage_pos();
	for (int i = 0; i < n; i++)
		debug(v[i]);
	int r;
	for (r = 0; v[r][0]*2 <= v[n-1][0]; r++)
		update(v[r][1], 1);
	int sum = query(0, k);
	debug(sum);
	ee.insert({v[n-1][0], 0});
	int j = 1; 
	for (int i = n-2; i >= 0; i--)
	{
		debug(v[i][1], j);
		if (v[i][1] != j)
			continue;
		while (v[r-1][0]*2>v[i][0])
		{
			debug(r-1);
			update(v[--r][1], -1);
		}
		int last_point = *pos[v[i][1]].upper_bound(v[i][0] / 2);
		auto it = ee.lower_bound(mp(last_point*2, -INF));
		if (it != ee.begin())
			it--;
		int ls;
		if (it == ee.end())
			ls = 0;
		else
		{
			ls = -(*it)[1];
			if (last_point*2 <= (*it)[0])
				ls++;
		}
		debug(v[i][1], ls, *it, last_point);
		int all_zero = query(j, k);
		debug(ls, j, j+1, k);
		int some_zero = mul(query(ls, j), query(j+1, k));
		int inter = query(j+1, k);
		debug(all_zero, some_zero, inter);
		debug(v[i][0], j, all_zero, some_zero, inter);
		sum = add(sum, all_zero, some_zero, -inter);
		debug(v[i][0], v[i][1]);
		ee.insert(mp(v[i][0], -v[i][1]));// Current point
		j++;
	}
	cout << sum << "\n";
}

Subtask #1
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 23764 KB Output is correct

Subtask #2
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 23888 KB Output is correct

Subtask #3
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 23888 KB Output is correct

Subtask #4
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 23892 KB Output is correct

Subtask #5
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 14 ms 23892 KB Output is correct

Subtask #6
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 23764 KB Output is correct
2 Correct 437 ms 51304 KB Output is correct

Subtask #7
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 23892 KB Output is correct

Subtask #8
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 24020 KB Output is correct

Subtask #9
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 184 ms 32972 KB Output is correct
2 Correct 232 ms 37864 KB Output is correct

Subtask #10
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 24020 KB Output is correct
2 Correct 18 ms 24276 KB Output is correct
3 Correct 21 ms 24148 KB Output is correct

Subtask #11
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 328 ms 40340 KB Output is correct
2 Correct 508 ms 51496 KB Output is correct
3 Correct 490 ms 51604 KB Output is correct

Subtask #12
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 399 ms 30144 KB Output is correct
2 Correct 554 ms 51616 KB Output is correct

Subtask #13
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 242 ms 40580 KB Output is correct
2 Correct 534 ms 51956 KB Output is correct

Subtask #14
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 488 ms 49460 KB Output is correct

Subtask #15
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 577 ms 52096 KB Output is correct

Subtask #16
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 370 ms 49168 KB Output is correct
2 Correct 610 ms 58060 KB Output is correct

Subtask #17
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 706 ms 58684 KB Output is correct
2 Correct 482 ms 50544 KB Output is correct

Subtask #18
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 592 ms 56280 KB Output is correct
2 Correct 819 ms 58188 KB Output is correct
3 Correct 760 ms 65536 KB Output is correct
4 Correct 746 ms 57988 KB Output is correct

Subtask #19
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 848 ms 65536 KB Output is correct
2 Runtime error 641 ms 65536 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -