# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
837575 |
2023-08-25T12:25:17 Z |
caganyanmaz |
Fish (IOI08_fish) |
C++17 |
|
0 ms |
0 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;
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]];
}
void manage_pos()
{
for (int i = 0; i < n; i++)
pos[v[i][1]].insert(i);
}
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);
ee.insert({n-1, 0});
int j = 1;
for (int i = n-2; i >= 0; i--)
{
if (v[i][1] != j)
continue;
while (v[r-1][0]*2>v[i][0])
update(v[--r][1], -1);
int last_point = *pos[v[i][1]].upper_bound(v[i][0] / 2);
int ls = (*ee.lower_bound(mp(last_point, -1)))[1];
int all_zero = query(j, k);
int some_zero = mul(query(ls+1, j), query(j+1, k));
int inter = query(j+1, k);
debug(v[i][0], j, all_zero, some_zero, inter);
sum = add(sum, all_zero, some_zero, -inter);
ee.insert(mp(i, v[i][1]));// Current point
j++;
}
cout << sum << "\n";
}
Compilation message
fish.cpp:8:10: fatal error: ../debug.h: No such file or directory
8 | #include "../debug.h"
| ^~~~~~~~~~~~
compilation terminated.