Submission #1164452

#TimeUsernameProblemLanguageResultExecution timeMemory
1164452HasanV11010238Port Facility (JOI17_port_facility)C++20
0 / 100
0 ms320 KiB
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007
int main(){
    int n, l, r;
    cin>>n;
    vector<int> ev(2 * n + 1, 0);
    for (int i = 1; i <= n; i++){
        cin>>l>>r;
        ev[l] = i;
        ev[r] = -i;
    }
    bool can = 1;
    int nxt = 0;
    vector<int> isd(n + 1, 0), la(n + 1, 0), de;
    for (int i = 1; i <= 2 * n; i++){
        while (!de.empty() && isd[de.back()] == 1) de.pop_back();
        if (ev[i] > 0){
            de.push_back(ev[i]);
            continue;
        }
        int no = -ev[i], in = de.size() - 1;
        if (la[no] == 0) nxt++;
        while (de[in] != no){
            if (la[de[in]] != 0 && isd[de[in]] == 0){
                can = 0;
                break;
            }
            la[de[in]] = 1;
            in--;
        }
        if (!can) break;
        isd[no] = 1;
    }
    if (!can){
        cout<<0<<"\n";
        return 0;
    }
    int ans = 1;
    for (int i = 1; i <= nxt; i++) ans = (ans * 2) % mod;
    cout<<ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...