Submission #550770

#	Time	Username	Problem	Language	Result	Execution time	Memory
550770		AlperenT	Port Facility (JOI17_port_facility)	C++17	0 / 100	1 ms	212 KiB

port_facility

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 5, MOD = 1e9 + 7, INF = 1e9 + 5;

struct mint{
    int val = 0;
 
    mint(long long a = 0) : val(a % MOD) {if(val < 0) val += MOD; }
    mint(long long a, long long b) {*this += a; *this /= b; }
 
    mint &operator += (const mint &b) {val += b.val; if(val >= MOD) val -= MOD; return *this; }
    mint &operator -= (const mint &b) {val -= b.val; if(val < 0) val += MOD; return *this; }
    mint &operator *= (const mint &b) {val = (1ll * val * b.val) % MOD; return *this; }
 
    mint mexp(mint a, long long b){
        mint c(1);
        for(; b > 0; b /= 2, a *= a) if(b & 1) c *= a;
        return c;
    }
 
    mint minv(const mint &a) {return mexp(a, MOD - 2); };
 
    mint &operator /= (const mint &b) {*this *= minv(b); return *this; }
 
    friend mint operator + (mint a, const mint &b) {return a += b; }
    friend mint operator - (mint a, const mint &b) {return a -= b; }
    friend mint operator - (const mint &a) {return 0 - a; }
    friend mint operator * (mint a, const mint &b) {return a *= b; }
    friend mint operator / (mint a, const mint &b) {return a /= b; }
 
    friend bool operator == (const mint &a, const mint &b) {return a.val == b.val; }
    friend bool operator != (const mint &a, const mint &b) {return a.val != b.val; }
 
    friend istream &operator >> (istream &is, mint &a) {long long b; is >> b; a = b; return is; }
    friend ostream &operator << (ostream &os, const mint &a) {return os << a.val; }
};

int n;

pair<int, int> arr[N];

stack<pair<int, int>> stk1, stk2;

mint ans = 1;

bool isgood(pair<int, int> a, pair<int, int> b){
	return a.first > b.first && a.second < b.second;
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);
	
	cin >> n;

	for(int i = 1; i <= n; i++) cin >> arr[i].first >> arr[i].second;

	sort(arr + 1, arr + n + 1);

	stk1.push({0, INF});
	stk2.push({0, INF});

	for(int i = 1; i <= n; i++){
		while(stk1.top().second < arr[i].first) stk1.pop();
		while(stk2.top().second < arr[i].first) stk2.pop();

		if(isgood(arr[i], stk1.top()) && isgood(arr[i], stk2.top())){
			ans *= 2;
			stk1.push(arr[i]);
		}
		else if(isgood(arr[i], stk1.top())) stk1.push(arr[i]);
		else if(isgood(arr[i], stk2.top())) stk2.push(arr[i]);
		else ans *= 0;
	}

	cout << ans;
}

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