제출 #132124

#제출 시각아이디문제언어결과실행 시간메모리
132124IC_COLDSTOPPort Facility (JOI17_port_facility)C++17
0 / 100
2 ms376 KiB
#include<bits/stdc++.h>
using namespace std;
ofstream fout ("out.txt");
#define ll long long
#define int ll
#define F first
#define S second
#define MP make_pair
#define pb push_back
#define pii pair<int,int>
#define REP(i,a,b) for(int i=a; i<b; i++)
 
const int MX=2e6+3, mod=1e9+7;
 
int n, arr[MX], pp[MX], ans=1, ps[MX], fen[MX];
 
void ADD(int pl, int val){
    for(; pl<MX; pl+=pl&-pl) fen[pl]+=val;
}
 
int ASK(int pl){
    int sum=0;
    for(; pl>0; pl-=pl&-pl) sum+=fen[pl];
    return sum;
}
 
int pw(int a, int b){
    if(!b) return 1;
    int nsf=pw(a,b/2);
    nsf=nsf*nsf%mod;
    if(b&1) nsf*=a;
    return nsf%mod;
}
 
int32_t main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //cout<<(1&-1)<<endl;
    cin>>n;
    REP(i,0,n){
        int a, b;
        cin>>a>>b;
        arr[a]=b;
    }
    stack<int> a, b;
    REP(i,1,2*n+1){
        //cout<<i<<endl;
        if(a.size() && i==a.top()) a.pop();
        if(b.size() && i==b.top()) b.pop();
        //cout<<i<<endl;
        if(arr[i]){
            ans=ans*2%mod;
            int cnt=ASK(arr[i])-ASK(i);
            ans=ans*pw(pw(2,cnt),mod-2)%mod;
            ADD(arr[i],1);
            //cout<<i<<endl;
            //if(a.size()) cout<<" A "<<a.top()<<endl;
            //if(b.size()) cout<<" B "<<b.top()<<endl;
            if(!a.size()){
                    //cout<<i<<endl;
                if(!b.size()) b.push(arr[i]);
                else{
                    int cnt=b.top();
                    if(cnt>arr[i]) b.push(arr[i]);
                    else a.push(arr[i]);
                }
            }
            else{
                if(!b.size()){
                    if(a.top()>arr[i]) a.push(arr[i]);
                    else b.push(arr[i]);
                    continue;
                }
                int cnta=a.top(), cntb=b.top();
                if(arr[i]<cnta && arr[i]<cntb){
                    if(cnta<cntb) a.push(arr[i]);
                    else b.push(arr[i]);
                }
                else if(arr[i]<cnta){
                    a.push(arr[i]);
                }
                else if(arr[i]<cntb){
                    b.push(arr[i]);
                }
                else{
                    //return cout<<0<<endl, 0;
                }
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...