제출 #328950

#제출 시각아이디문제언어결과실행 시간메모리
328950pit4hPort Facility (JOI17_port_facility)C++14
0 / 100
18 ms31724 KiB
#include<bits/stdc++.h> #define st first #define nd second #define mp make_pair #ifndef LOCAL #define cerr if(0)cerr #endif using namespace std; using ll = long long; using ld = long double; using vi = vector<int>; using pii = pair<int, int>; const int N = 1e6+1; const ll mod = 1e9+7; int l[N], r[N], nr[2*N], col[N]; bool is[N]; ll ans=1; priority_queue<pii> r_min[N]; bool collide(int i, int it) { while(r_min[it].size() && !is[r_min[it].top().nd]) { r_min[it].pop(); } if(r_min[it].size() && -r_min[it].top().st < r[i]) return true; return false; } void add(int id, int it) { r_min[it].push(mp(-r[id], id)); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin>>n; for(int i=0; i<n; ++i) { cin>>l[i]>>r[i]; nr[l[i]]=i; nr[r[i]]=i; } for(int i=1; i<=2*n; ++i) { if(!is[nr[i]]) { is[nr[i]] = 1; if(!collide(nr[i], 1)) { col[i] += 1; } if(!collide(nr[i], 2)) { col[i] += 2; } if(col[i]==0) { ans = 0; break; } if(col[i]==3) { cerr<<nr[i]<<": any\n"; ans *= 2LL; ans %= mod; add(nr[i], 1); } else { cerr<<nr[i]<<": "<<col[i]<<'\n'; add(nr[i], col[i]); } } else { is[nr[i]] = 0; } } cout<<ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...