이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
#define f first
#define s second
const int maxn = 5e5+10;
int f, k, m, last[maxn];
ll tree[4*maxn];
pii vet[maxn];
void build(int node, int l, int r){
if(l == r){
tree[node] = 1;
return;
}
int mid = (l + r) >> 1;
build(2*node, l, mid), build(2*node+1, mid+1, r);
tree[node] = (tree[2*node] * tree[2*node+1])%m;
}
void update(int node, int l, int r, int idx, int v){
if(l == r){
tree[node] += v;
return;
}
int mid = (l + r) >> 1;
if(idx <= mid) update(2*node, l, mid, idx, v);
else update(2*node+1, mid+1, r, idx, v);
tree[node] = (tree[2*node] * tree[2*node+1])%m;
}
ll query(int node, int tl, int tr, int l, int r){
if(tl > r or tr < l) return 1LL;
if(tl >= l and tr <= r) return tree[node];
int mid = (tl + tr) >> 1;
return (query(2*node, tl, mid, l, r)*query(2*node+1, mid+1, tr, l, r))%m;
}
int main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
cin >> f >> k >> m;
for(int i=1; i<=f; i++){
cin >> vet[i].f >> vet[i].s;
last[vet[i].s] = i;
}
sort(vet+1, vet+f+1);
build(1, 1, f);
ll ans = 0LL;
for(int i=1, j=1; i<=f and j<=f; i++){
if(last[vet[i].s] == i){
update(1, 1, f, vet[j].s, 1);
ans += query(1, 1, f, 1, f);
update(1, 1, f, vet[j].s, -1);
}
while(vet[j].f + vet[j].f <= vet[i].f){
update(1, 1, f, vet[j].s, 1);
j++;
}
}
cout << (ans+m)%m << endl;
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... |