Submission #1184082

#TimeUsernameProblemLanguageResultExecution timeMemory
1184082mfmme23Port Facility (JOI17_port_facility)C++20
0 / 100
0 ms320 KiB
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
const int MOD = 1'000'000'007;
struct Event {
    int time;
    int index;
    bool isStart;
};

int main() {
    int N;
    cin >> N;

    vector<int> A(N), B(N);
    vector<Event> events;

    for (int i = 0; i < N; ++i) {
        cin >> A[i] >> B[i];
        events.push_back({A[i], i, true});   
        events.push_back({B[i], i, false});  
    }

    
    sort(events.begin(), events.end(), [](const Event &a, const Event &b) {
        return a.time < b.time;
    });


    vector<vector<int>> dp(1, vector<int>(1, 1));  

    for (const auto &e : events) {
        int n = dp.size();
        int m = dp[0].size();

        vector<vector<int>> new_dp(n + 1, vector<int>(m + 1, 0));

        if (e.isStart) {
           
            for (int i = 0; i < n; ++i)
                for (int j = 0; j < m; ++j) {
                    new_dp[i + 1][j] = (new_dp[i + 1][j] + dp[i][j]) % MOD;  
                    new_dp[i][j + 1] = (new_dp[i][j + 1] + dp[i][j]) % MOD;  
                }
        } else {
            
            for (int i = 0; i < n; ++i)
                for (int j = 0; j < m; ++j) {
                    if (i > 0)
                        new_dp[i - 1][j] = (new_dp[i - 1][j] + dp[i][j]) % MOD;  
                    if (j > 0)
                        new_dp[i][j - 1] = (new_dp[i][j - 1] + dp[i][j]) % MOD;  
                }
        }

        dp = move(new_dp);
    }
    cout << dp[0][0] << 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...