Submission #244199

#	Time	Username	Problem	Language	Result	Execution time	Memory
244199		Osama_Alkhodairy	Port Facility (JOI17_port_facility)	C++17	0 / 100	5 ms	384 KiB

port_facility

#include <bits/stdc++.h>
using namespace std;
#define finish(x) return cout << x << endl, 0
#define ll long long

int n, mod = 1e9 + 7;
vector <int> a;


int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    a.resize(2 * n);
    vector <int> l(n + 1), r(n + 1);
    for(int i = 1 ; i <= n ; i++){
        cin >> l[i] >> r[i];
        l[i]--; r[i]--;
        a[l[i]] = i;
        a[r[i]] = -i;
    }
    int ans = 0;
    vector <int> vis(n + 1);
    vector <int> g, h;
    for(auto &i : a){
        if(i < 0){
            i *= -1;
            if(h.size() && h.back() == i){
                h.pop_back();
                for(int j = (int)g.size() - 1 ; j >= 0 ; j--){
                    if(l[g[j]] > l[i]) ans--;
                    else break;
                }
                continue;
            }
            vector <int> c;
            while(g.size() && g.back() != i){
                c.push_back(g.back());
                g.pop_back();
            }
            if(g.size() == 0) finish(0);
            g.pop_back();
            reverse(c.begin(), c.end());
            for(auto &i : c){
                ans--;
                h.push_back(i);
            }
        }
        else{
            g.push_back(i);
            ans++;
        }
    }
    int res = 1;
    while(ans--){
        res *= 2;
        if(res >= mod) res -= mod;
    }
    cout << res << endl;
}

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