Submission #656052

#	Time	Username	Problem	Language	Result	Execution time	Memory
656052		aebov	Port Facility (JOI17_port_facility)	C++17	0 / 100	1426 ms	1048576 KiB

port_facility

    #pragma GCC optimize("Ofast")
    #pragma GCC optimize("unroll-loops")
     
    #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
    #include<iostream>
    #include<algorithm>
    #include<vector>
    #include<cstring>
    #include<utility>
    #include<unordered_set>
    #include<set>
    #define ll long long
    #define ln (e-s+1)
    #define md ((s+e)/2)
    #define dm ((e+s)/2+1)
    #define lc (id*2)
    #define rc (id*2+1)
    #define pb push_back
    #define pii pair<int, int>
    #define pll pair<ll ,  ll>
    #define F first
    #define S second
    using namespace std;
     
    const int N = 1e6 + 5;
    const ll mod = (ll)1e9 + 7;
    int n, a[N], b[N], cnt;
    ll int ans = 1LL;
    bool vis[N];
    vector<pii> vc[2];
    set<int> st;
    pii seg[2][N << 2];
     
    void upd(int ind, int p, pii x, int id = 1,int s = 0, int e = (n<<1)){
    	if(e - s == 1){
    		seg[ind][id] = x;
    		return;
    	}
    	if(p < md)upd(ind, p, x, lc , s, md);
    	else upd(ind, p, x, rc, md, e);
    	seg[ind][id] = min(seg[ind][lc], seg[ind][rc]);
    }
    /*void updmax(int p, pii x, int id = 1,int s = 1, int e = (n<<1) + 1){
    	if(p < s || p > e)return;
    	if(ln == 1){
    		segmax[id] = x;
    		return;
    	}
    	updmax(p, x, lc, s, md), updmax(p, x, rc, dm , e);
    	segmax[id] = max(segmax[lc], segmax[rc]);
    }*/
    pii get(int ind, int l,int r,int id = 1,int s = 0, int e = (n<<1)){
    	if(l >= e|| r <= s)return {mod, mod};
    	if(l <=s&& e<= r)return seg[ind][id];
    	return min(get(ind ,l, r, lc, s, md), get(ind, l, r, rc, md, e));
    }
    /*pii getmax(int l,int r,int id = 1,int s = 1, int e = (n<<1) + 1){
    	if(l > e|| r < s)return {-mod, -mod};
    	if(l <=s&& e<= r)return segmax[id];
    	return max(getmax(l, r, lc, s, md), getmax(l, r, rc, dm, e));
    }*/
    void dfs(int v,int c){
    //	cout << "dfs " << v << " " << c << endl;
    	vis[v] = true;
    	upd(0, b[v],{mod, v});
    	upd(1, a[v],{mod, v});
    	vc[c].pb({a[v], b[v]});
     	while(true){
    		auto p = get(0, a[v], b[v]);
    		if(p.F > a[v])break;
    		dfs(p.S, c ^ 1);
    	}	
    	while(true){
    		auto p = get(1 ,a[v], b[v]);
    		if(-p.F < b[v])break;
    		dfs(p.S, c ^ 1);
    	}
     
    }
    bool valid(vector<pii> vc){
    	st.clear();
    	sort(vc.begin(), vc.end());
    	for(pii i : vc){
    		auto it = st.lower_bound(i.F);
    		if(it != st.end() && (*it) <= i.S){
    			printf("%d\n", 0);
    			exit(0);
    		}
    		st.insert(i.S);
    	}
    	return 0;
    }
    int main(){
    	scanf("%d",&n);
    	fill(seg[0] , seg[0] + (n+2) * 4 , pii(mod, mod));
    	fill(seg[1] , seg[1] + (n+2) * 4 , pii(mod , mod));
    	for(int i = 0; i < n; i ++){
    		scanf("%d%d", &a[i], &b[i]); a[i]--, b[i]--;
    		upd(0, b[i], {a[i], i}), upd(1, a[i], {-b[i],i});
    	}
    	for(int i = 0; i < n; i ++) if(!vis[i])dfs(i, 0), cnt ++;
    	if(valid(vc[0]) || valid(vc[1]))return 0;
    	while(cnt --) ans <<= 1, ans %= mod;
    	printf("%lld\n", ans);
    }

Compilation message (stderr)

port_facility.cpp: In function 'int main()':
port_facility.cpp:94:11: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |      scanf("%d",&n);
      |      ~~~~~^~~~~~~~~
port_facility.cpp:98:12: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   98 |       scanf("%d%d", &a[i], &b[i]); a[i]--, b[i]--;
      |       ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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