이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
using namespace std;
typedef long long ll;
typedef pair <ll, ll> pii;
const int F = 5e5 + 7, ofs = (1 << 19);
int f, k, mod;
int h[F], c[F], gr[F], fi[F], la[F], cnt[F], ha[F], bio[F], did[F];
vector <int> po[F];
struct T {
vector <int> t;
void init() {
t.clear(); t.resize(2*ofs, 1);
}
void update(int x, int val) {
x += ofs;
t[x] = val;
while (x /= 2) t[x] = (ll)t[2*x]*t[2*x+1]%mod;
}
int query(int x, int a, int b, int lo = 0, int hi = ofs-1) {
if (b < lo || hi < a) return 1;
if (a <= lo && hi <= b) return t[x];
int mid = (lo + hi) / 2;
return (ll)query(2*x, a, b, lo, mid)*query(2*x+1, a, b, mid+1, hi)%mod;
}
} t1, t2;
int main () {
FIO;
memset(fi, -1, sizeof fi);
memset(la, -1, sizeof la);
memset(ha, -1, sizeof ha);
cin >> f >> k >> mod;
vector <pii> v;
for (int i = 0; i < f; i++) {
cin >> h[i] >> c[i]; c[i]--;
v.pb({h[i], c[i]});
}
sort(all(v));
for (int i = 0; i < f; i++) h[i] = v[i].F, c[i] = v[i].S;
t1.init(); t2.init();
for (int i = f-1, j = f-1; i >= 0; i--) {
while (2*h[i] <= h[j]) ha[j--] = i;
gr[i] = j;
if (la[c[i]] == -1) la[c[i]] = i;
fi[c[i]] = i;
cnt[c[i]]++;
}
for (int i = 0; i < f; i++) po[c[i]].pb(i);
for (int i = 0; i < k; i++) {
bio[i] = 1;
if (la[i] == -1) continue;
t1.update(fi[i], cnt[i]+1);
}
int res = 0;
for (int i = f-1, j = f-1; i >= 0; i--) {
while (j > ha[i]) {
if (fi[c[j]] == j) {
t2.update(la[c[j]], 1);
bio[c[j]] = 0;
}
cnt[c[j]]--;
if (bio[c[j]]) {
if (did[c[j]]) t2.update(la[c[j]], cnt[c[j]]+1);
else t1.update(fi[c[j]], cnt[c[j]]+1);
}
j--;
}
if (la[c[i]] == i) {
t1.update(fi[c[i]], 1);
ll dod = (ll)t1.query(1, 0, j)*t2.query(1, i, gr[*upper_bound(all(po[c[i]]), ha[i])]);
if (cnt[c[i]]) {
t1.update(fi[c[i]], cnt[c[i]]);
dod += t1.query(1, 0, j);
}
res = (res + dod) % mod;
t1.update(fi[c[i]], 1);
if (bio[c[i]]) t2.update(i, cnt[c[i]]+1);
did[c[i]] = 1;
}
}
cout << res;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |