이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#define dbg(...) printf(__VA_ARGS__);
#define getchar_unlocked getchar
#else
#define dbg(...)
#endif
#define sf scanf
#define pf printf
#define fi first
#define se second
#define pb push_back
#define psf push_front
#define ppb pop_back
#define ppf pop_front
#define sz(x) (int)x.size()
#define mnto(x,y) x=min(x,(__typeof__(x))y)
#define mxto(x,y) x=max(x,(__typeof__(x))y)
#define INF 1023456789
#define LINF 1023456789123456789
#define all(x) x.begin(),x.end()
#define lb(x,v) (lower_bound(all(x),v)-x.begin())
#define ub(x,v) (upper_bound(all(x),v)-x.begin())
#define disc(x) sort(all(x));x.resize(unique(all(x))-x.begin());
typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;
typedef pair<ll,ll> pll;
typedef tuple<int,int,int> iii;
typedef tuple<int,int,int,int> iiii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
mt19937 rng(time(0));
inline int rd(){
int x=0;
char ch=getchar_unlocked();
while(!(ch&16))ch=getchar_unlocked();//keep reading while current character is whitespace
while(ch&16){//this will break when ‘\n’ or ‘ ‘ is encountered
x=(x<<3)+(x<<1)+(ch&15);
ch=getchar_unlocked();
}
return x;
}
#define maxn 500005
int n,k,mod;
vector<ii> v;
struct node{
int s,e,m,v;
node *l,*r;
node(int _s,int _e){
s=_s,e=_e,m=(s+e)>>1,v=1;
if(s!=e)l=new node(s,m),r=new node(m+1,e);
}
void add(int x){
if(s==x&&e==x){
v=(v+1)%mod;
return;
}
if(x<=m)l->add(x);
else r->add(x);
v=(l->v*r->v)%mod;
}
int qry(int x,int y){
if(s==x&&e==y)return v;
if(y<=m)return l->qry(x,y);
if(x>m)return r->qry(x,y);
return (l->qry(x,m)*r->qry(m+1,y))%mod;
}
}*rt;
int la[maxn],ord[maxn],num[maxn],pos[maxn],e[maxn],bad[maxn];
vi stuff;
int main(){
sf("%d%d%d",&n,&k,&mod);
for(int i=0;i<n;++i){
int l,t;
sf("%d%d",&l,&t);
v.pb({l,t});
}
sort(all(v));
rt=new node(0,k-1);
memset(la,-1,sizeof la);
int cnt=k-1;
for(int i=n-1;i>=0;--i){
auto[l,t]=v[i];
if(la[t]==-1){
stuff.pb(l);
la[t]=i;
ord[t]=cnt--;
}
}
for(int i=0;i<n;++i){
auto[l,t]=v[i];
int ml=v[la[t]].fi;
if(2*l<=ml)++e[t];
pos[i]=num[t]++;
}
memset(bad,-1,sizeof bad);
for(int i=0;i<n;++i){
auto[l,t]=v[i];
if(pos[i]==e[t])bad[t]=l;
}
int ptr=0;
reverse(all(stuff));
int ans=0;
for(int i=0;i<n;++i){
auto[l,t]=v[i];
while(ptr<=i&&v[ptr].fi*2<=l){
rt->add(ord[v[ptr].se]);
++ptr;
}
if(la[t]!=i)continue;
int r=(bad[t]==-1)?k-1:(lb(stuff,2*bad[t])-1);
int m=lb(stuff,l+1);
//pf("%d %d, %d\n",m,r,ord[t]);
if(0<=m-1){//partial
int tmp=1;
if(ord[t]!=0)tmp*=rt->qry(0,ord[t]-1);
tmp%=mod;
if(ord[t]!=m-1)tmp*=rt->qry(ord[t]+1,m-1);
tmp%=mod;
tmp*=e[t];
tmp%=mod;
ans+=tmp;
ans%=mod;
}
if(0<=r){//full
int tmp=1;
if(ord[t]!=0)tmp*=rt->qry(0,ord[t]-1);
tmp%=mod;
if(ord[t]!=r)tmp*=rt->qry(ord[t]+1,r);
tmp%=mod;
ans+=tmp;
ans%=mod;
}
//pf("%d: %d\n",t,ans);
}
pf("%d\n",ans);
}
컴파일 시 표준 에러 (stderr) 메시지
fish.cpp: In function 'int main()':
fish.cpp:82:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
82 | sf("%d%d%d",&n,&k,&mod);
| ^
fish.cpp:85:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
85 | sf("%d%d",&l,&t);
| ^
# | 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... |