Submission #132123

#	Time	Username	Problem	Language	Result	Execution time	Memory
132123		IC_COLDSTOP	Port Facility (JOI17_port_facility)	C++17	0 / 100	2 ms	376 KiB

port_facility

#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;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 12
• Subtask 3: 0 / 56
• Subtask 4: 0 / 22