Submission #656061

#	Time	Username	Problem	Language	Result	Execution time	Memory
656061		aebov	Port Facility (JOI17_port_facility)	C++17	78 / 100	275 ms	145100 KiB

port_facility

#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
#include<utility>
#include<set>
#define ll long long
#define ln (e-s+1)
#define md ((s+e) >> 1)
#define dm (((e+s) >> 1) + 1)
#define lc (id<<1)
#define rc (lc | 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] + ((2*n + 2) * 4) , pii(mod, mod));
	fill(seg[1] , seg[1] + ((2*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:89:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |  scanf("%d",&n);
      |  ~~~~~^~~~~~~~~
port_facility.cpp:93:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |   scanf("%d%d", &a[i], &b[i]); a[i]--, b[i]--;
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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