#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define all(vr) vr.begin(),vr.end()
#define vi vector<int>
#define vll vector<ll>
const int N = 1e6 + 10;
int mod, n;
struct segment_tree
{
int it[N * 4], lazy[N * 4];
void down(int id)
{
int tmp = lazy[id];
it[id * 2] = it[id * 2] * tmp % mod;
it[id * 2 + 1] = it[id * 2 + 1] * tmp % mod;
lazy[id * 2] = lazy[id * 2] * tmp % mod;
lazy[id * 2 + 1] = lazy[id * 2 + 1] * tmp % mod;
lazy[id] = 1;
}
void init()
{
memset(lazy, 1, sizeof(lazy));
}
void update_single(int pos, int val, int id = 1, int l = 0, int r = n)
{
if (l == r)
{
it[id] = val;
return;
}
int mid = (l + r) / 2;
down(id);
if (pos <= mid) update_single(pos, val, id * 2, l, mid);
else update_single(pos, val, id * 2 + 1, mid + 1, r);
it[id] = (it[id * 2] + it[id * 2 + 1]) % mod;
}
void update_range(int u, int v, int coef, int id = 1, int l = 0, int r = n)
{
if (l > v || r < u) return;
if (u <= l && r <= v)
{
it[id] = it[id] * coef % mod;
lazy[id] = lazy[id] * coef % mod;
return;
}
int mid = (l + r) / 2;
down(id);
update_range(u, v, coef, id * 2, l, mid);
update_range(u, v, coef, id * 2 + 1, mid + 1, r);
it[id] = (it[id * 2] + it[id * 2 + 1]) % mod;
}
int get(int u, int v, int id = 1, int l = 0, int r = n)
{
if (l > v || r < u) return 0;
if (u <= l && r <= v) return it[id];
int mid = (l + r) / 2;
down(id);
return get(u, v, id * 2, l, mid) + get(u, v, id * 2 + 1, mid + 1, r);
}
} seg;
int k, lim[N], p[N];
pii a[N];
vi vt[N];
bool cmp(int c1, int c2) { return vt[c1].back() < vt[c2].back(); }
int main()
{
//freopen("ss.inp", "r", stdin);
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> k >> mod;
for (int i = 1; i <= n; ++i) cin >> a[i].fi >> a[i].se;
sort(a + 1, a + n + 1);
int j = 0;
for (int i = 1; i <= n; ++i)
{
while (a[j].fi * 2 <= a[i].fi) ++j;
lim[i] = j - 1;
}
for (int i = 1; i <= n; ++i) vt[a[i].se].eb(i);
for (int i = 1; i <= k; ++i) p[i] = i;
sort(p + 1, p + k + 1, cmp);
seg.init();
seg.update_single(0, 1);
int res = 0;
for (int i = 1; i <= k; ++i)
{
int c = p[i];
int mx = vt[c].back();
int coef = 1;
for (int x : vt[c])
if (x <= lim[mx]) coef++;
res = (res + seg.get(0, lim[mx]) % mod * coef) % mod;
reverse(all(vt[c]));
for (int x : vt[c]) seg.update_single(x, seg.get(0, x) % mod);
reverse(all(vt[c]));
coef = 1;
for (int i = 0; i < (int)vt[c].size() - 1; ++i)
{
int l = vt[c][i] + 1, r = vt[c][i + 1] - 1;
if (l <= r) seg.update_range(l, r, coef);
coef++;
}
if ((int)vt[c].back() <n) seg.update_range(vt[c].back() + 1, n, coef);
}
cout << res;
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
22 ms |
39372 KB |
Output isn't correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
22 ms |
39460 KB |
Output isn't correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
20 ms |
39432 KB |
Output isn't correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
20 ms |
39500 KB |
Output isn't correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
22 ms |
39444 KB |
Output is correct |
2 |
Incorrect |
22 ms |
39448 KB |
Output isn't correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
23 ms |
39440 KB |
Output is correct |
2 |
Incorrect |
1010 ms |
58136 KB |
Output isn't correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
22 ms |
39500 KB |
Output isn't correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
26 ms |
39668 KB |
Output isn't correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
429 ms |
47592 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
23 ms |
39676 KB |
Output is correct |
2 |
Incorrect |
32 ms |
39668 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
702 ms |
53312 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
673 ms |
58352 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
420 ms |
53400 KB |
Output is correct |
2 |
Incorrect |
1216 ms |
59316 KB |
Output isn't correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1202 ms |
58204 KB |
Output isn't correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1344 ms |
60624 KB |
Output isn't correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1027 ms |
57000 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1394 ms |
61896 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1155 ms |
60696 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1541 ms |
64592 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |