Submission #44407

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

port_facility

#include<bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;

const int mod = 1e9 + 7;
const int MN = 1000010;

int N;
pii P[MN];
vector<int> A, B;
stack<set<int> > stk;

int main() {
    scanf("%d", &N);

    for(int i = 0; i < N; i++) {
        scanf("%d %d", &P[i].first, &P[i].second);
    }

    sort(P, P + N);

    for(int i = 0; i < N; i++) {
        while(A.size() && A.back() < P[i].first) A.pop_back();
        while(B.size() && B.back() < P[i].first) B.pop_back();
        if(!A.size() || A.back() > P[i].second) {
            A.push_back(P[i].second);
        }
        else if(!B.size() || B.back() > P[i].second) {
            B.push_back(P[i].second);
        }
        else {
            printf("0");
            return 0;
        }
    }

    int cnt = 0;
    for(int i = 0; i < N; i++) {
        while(!stk.empty() && *stk.top().rbegin() < P[i].first) {
            stk.pop();
            cnt++;
        }
        if(stk.empty()) {
            stk.push(set<int>());
            stk.top().insert(P[i].second);
        }
        else {
            set<int>::iterator it = stk.top().lower_bound(P[i].first);
            if(*it < P[i].second) {
                stk.top().insert(P[i].second);
            }
            else {
                stk.push(set<int>());
                stk.top().insert(P[i].second);
            }
        }
    }
    while(!stk.empty()) {
        stk.pop();
        cnt++;
    }

    int ans = 1;
    for(int i = 0; i < cnt; i++) ans = ans * 2 % mod;
    printf("%d", ans);
}

Compilation message (stderr)

port_facility.cpp: In function 'int main()':
port_facility.cpp:15:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &N);
     ~~~~~^~~~~~~~~~
port_facility.cpp:18:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &P[i].first, &P[i].second);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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