Submission #94687

#TimeUsernameProblemLanguageResultExecution timeMemory
94687MB81Port Facility (JOI17_port_facility)C++11
0 / 100
2 ms504 KiB
    // :)
    // "Khodaya, be man "Tagwaye setiz" biamooz ta
    //  dar anbuh masuliat nalaghzam ..." -Shariati
    #include <bits/stdc++.h>
    #include <ext/pb_ds/assoc_container.hpp>
    #include <ext/pb_ds/tree_policy.hpp>
    #define F first
    #define S second
    #define MP make_pair
    using namespace std;
    using namespace __gnu_pbds;
    template <typename T> using ordered_set =  tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
    template <typename T> using ordered_multiset =  tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
    typedef long long int64;
    typedef pair<int,int> pii;
    typedef pair<int64,int64> pii64;
    const int maxn = 2e6+9;
    const int64 M = 1e9+7;
    const int64 I = 1e9;
     
    vector <pii> v1;
    int fen[2][maxn];
     
    int n, ans = 1;
     
    void upd (int x, int val, int id) {
    	for (; x < maxn; x += x&-x)
    		fen[id][x] += val;
    	return;
    }
     
    int get (int x, int id) {
    	int res = 0;
    	for (; x; x -= x&-x)
    		res += fen[id][x];
    	return res;
    }
     
    int main () {
    	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    	cin >> n;
    	for (int i = 0; i < n; i++) {
    		int st, en;
    		cin >> st >> en;
    		v1.push_back( MP( en, st ) );
    	}
    	sort(v1.begin(), v1.end());
    	for (int i = 0; i < n; i++) {
    		int x = v1[i].S, y = v1[i].F;
    		int cur1 = get(x, 0);
    		int cur2 = get(x, 1);
    		if (cur1 + cur2 == 0) {
    			ans = 2LL * ans % M;
    			upd(x, 1, 0);
    			upd(y, -1, 0);
    			continue;
    		}
    		if (cur1 > 0 && cur2 > 0)
    			ans = 0;
    		if (cur1 > 0) {
    			upd(x, 1, 1);
    			upd(y, -1, 1);
    		} else {
    			upd(x, 1, 0);
    			upd(y, -1, 0);
    		}
    	}
    	cout << ans << "\n";
    }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...