제출 #447243

#제출 시각아이디문제언어결과실행 시간메모리
447243alan8585Port Facility (JOI17_port_facility)C++14
0 / 100
1 ms204 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, id; bool operator<(const datas &a) { return x < a.x; } }; vector<datas> ori, v, tv; vector<int> C; int find(int a) { if(C[a] != a) return C[a] = find(C[a]); return a; } void merge(int a, int b) { // cout << a << ' ' << b << '\n'; a = find(a); b = find(b); if(a == b) return; C[a] = b; } 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 && v[tl].y < v[tr].y)) { if(now == -1 || ori[now].y < v[tl].y) now = v[tl].id; tv[i] = v[tl]; tl++; } else { if(now != -1 && v[tr].x < ori[now].y) merge(v[tr].id, now); tv[i] = v[tr]; tr++; } } for(int i = l; i <= r; i++) v[i] = tv[i]; } bool is_vali() { sort(ALL(v)); stack<int> st1, st2; for(datas &i : v) { while(!st1.empty() && st1.top() < i.x) st1.pop(); while(!st2.empty() && st2.top() < i.x) st2.pop(); if(st1.empty() || st1.top() > i.y) st1.push(i.y); else if(st2.empty() || st2.top() > i.y) st2.push(i.y); else return 0; } return 1; } int main() {Tie int n; cin >> n; v.resize(n), tv.resize(n), C.resize(n); for(int i = 0; i < n; i++) { C[i] = i; cin >> v[i].x >> v[i].y; v[i].id = i; } ori = v; if(!is_vali()) { cout << "0\n"; return 0; } v = ori; sort(ALL(v)); merge_sort(0, n - 1); for(int i = 0; i < n; i++) { v[i].x = n * 2 + 1 - v[i].x; v[i].y = n * 2 + 1 - v[i].y; ori[i].x = n * 2 + 1 - ori[i].x; ori[i].y = n * 2 + 1 - ori[i].y; } sort(ALL(v)); // reverse(ALL(v)); merge_sort(0, n - 1); int ans = 1; // for(int i = 0; i < n; i++) cout << C[i] << " \n"[i == n - 1]; for(int i = 0; i < n; i++) if(C[i] == i) ans = (ans << 1) % 100000007; cout << ans << '\n'; }

컴파일 시 표준 에러 (stderr) 메시지

port_facility.cpp: In function 'void merge_sort(int, int)':
port_facility.cpp:44:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   44 |     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...