This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <numeric>
#include <cassert>
#include <vector>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<int,P> pip;
typedef vector<pip> vip;
const int inf=1<<29;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-8;
//const ll mod=998244353;
const int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};
int mod;
class Segment_Tree{
private:
int n;
vi date;
public:
Segment_Tree(int n_){
n=1;
while(n<n_) n*=2;
date=vi(2*n-1);
}
void Update(int k,int x){
k+=n-1;
date[k]+=x;
while(k>0){
k=(k-1)/2;
date[k]=date[k*2+1]*date[k*2+2]%mod;
}
}
int Query(int a,int b){
a+=n-1;b+=n-1;
int m=1;
while(a<b){
if(a%2==0) (m*=date[a++])%=mod;
if(b%2==0) (m*=date[--b])%=mod;
a/=2;b/=2;
}
return m;
}
int Open(int k){return date[k+n-1];}
};
const int M=500001;
int n,m,c[M],perm[M];
P a[M];
pip b[M];
Segment_Tree st(M);
int main(){
scanf("%d%d%d",&m,&n,&mod);
for(int i=0;i<m;i++){
int x,y;
scanf("%d%d",&x,&y);
y--;
a[i]={x,y};
b[y].first=max(b[y].first,x);
b[y].second.first++;
b[y].second.second=y;
}
sort(a,a+m);sort(b,b+n);
fill(c,c+M,inf);
for(int i=0;i<n;i++){
st.Update(i,b[i].second.first+1);
perm[b[i].second.second]=i;
}
int I=m-1,res=0;
for(int i=n-1;i>=0;i--){
while(I>=0&&a[I].first*2>b[i].first){
int id=perm[a[I].second];
st.Update(id,-1);
c[id]=i;
I--;
}
int x=st.Query(0,i),t=c[b[i].second.second];
if(t<inf){
(res+=x*st.Query(i+1,t))%=mod;
(res+=x*(st.Open(i)-1))%=mod;
}
else (res+=x*st.Open(i))%=mod;
}
printf("%d\n",res);
}
Compilation message (stderr)
fish.cpp: In function 'int main()':
fish.cpp:78:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
78 | scanf("%d%d%d",&m,&n,&mod);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~
fish.cpp:81:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
81 | scanf("%d%d",&x,&y);
| ~~~~~^~~~~~~~~~~~~~
# | 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... |