Submission #447270

#TimeUsernameProblemLanguageResultExecution timeMemory
447270alan8585Port Facility (JOI17_port_facility)C++14
78 / 100
6096 ms377272 KiB
#pragma GCC optimize ("Ofast","unroll-loops") #include <bits/stdc++.h> #define pb push_back #define eb emplace_back #define MP make_pair #define F first #define S second #define setpre(a) cout.precision(a),cout<<fixed; #define ALL(a) a.begin(),a.end() #define MEM(a,b) memset(a,b,sizeof a) #define Tie ios::sync_with_stdio(0),cin.tie(0); using namespace std; typedef long long ll; typedef long double ld; typedef pair<int,int> pii; typedef pair<ll,ll> pll; typedef pair<ld,ld> pdd; struct datas { int x, y; bool operator<(const datas &a) { return x < a.x; } }; vector<datas> ori; vector<int> e[1000100]; vector<int> C; int n, v[1000100], tv[1000100]; int find(int a) { if(C[a] != a) return C[a] = find(C[a]); return a; } void merge(int a, int b) { a = find(a); b = find(b); if(a == b) return; if(a > b) swap(a, b); C[b] = a; } void merge_sort(int l, int r) { if(l == r) return; int m = l + r >> 1, tl = l, tr = m + 1, now = -1; merge_sort(l, m); merge_sort(m + 1, r); for(int i = l; i <= r; i++) { if(tr > r || (tl <= m && ori[v[tl]].y < ori[v[tr]].y)) { if(now == -1 || (ori[now].y < ori[v[tl]].y)) now = v[tl]; tv[i] = v[tl++]; } else { if(now != -1 && ori[v[tr]].x < ori[now].y) { e[v[tr]].pb(now); e[now].pb(v[tr]); merge(v[tr], now + n); merge(now, v[tr] + n); } tv[i] = v[tr++]; } } for(int i = l; i <= r; i++) v[i] = tv[i]; // memcpy(v + l, tv + l, sizeof(int) * (r - l + 1)); } bitset<1000100> vis; vector<datas> lv, rv; void dfs(int a, int c) { vis[a] = 1; if(c == 1) lv.pb(ori[a]); else rv.pb(ori[a]); for(int i : e[a]) if(!vis[i]) dfs(i, 3 - c); } bool f(int a, int b) { return ori[a].x < ori[b].x; } int main() {Tie cin >> n; C.resize(n * 2), ori.resize(n); for(int i = 0; i < n; i++) cin >> ori[i].x >> ori[i].y; for(int i = 0; i < n * 2; i++) C[i] = i; for(int i = 0; i < n; i++) v[i] = i; sort(v, v + n, f); merge_sort(0, n - 1); for(int i = 0; i < n; i++) { ori[i].x = n * 2 + 1 - ori[i].x; ori[i].y = n * 2 + 1 - ori[i].y; swap(ori[i].x, ori[i].y); } for(int i = 0; i < n; i++) v[i] = i; sort(v, v + n, f); merge_sort(0, n - 1); int ans = 1; for(int i = 0; i < n; i++) { if(vis[i]) continue; lv.clear(); rv.clear(); dfs(i, 1); sort(ALL(lv)); int mx = -1; for(datas i : lv) { if(i.y > mx && mx > i.x) ans = 0; mx = max(mx, i.y); } sort(ALL(rv)); mx = -1; for(datas i : rv) { if(i.y > mx && mx > i.x) ans = 0; mx = max(mx, i.y); } } for(int i = 0; i < n; i++) if(find(i) == find(i + n)) ans = 0; int tmp = 0; for(int i = 0; i < 2 * n; i++) if(find(i) == i) tmp++; tmp >>= 1; for(int i = 0; i < tmp; i++) ans = (ans << 1) % 1000000007; cout << ans << '\n'; }

Compilation message (stderr)

port_facility.cpp: In function 'void merge_sort(int, int)':
port_facility.cpp:46:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |     int m = l + r >> 1, tl = l, tr = m + 1, now = -1;
      |             ~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...