제출 #914455

#제출 시각아이디문제언어결과실행 시간메모리
914455daoquanglinh2007Port Facility (JOI17_port_facility)C++17
0 / 100
32 ms55124 KiB
#include <bits/stdc++.h> using namespace std; const int NM = 2e6, inf = 1e9+7, MOD = 1e9+7; int N, r[NM+5], cnt = 0, ans = 1; int suml[NM+5], sumr[NM+5], mn[NM+5], mn2[NM+5]; void update_sum(int sum[NM+5], int x){ while (x <= NM){ sum[x]++; x += x & (-x); } } void update_mn(int mn[NM+5], int x, int val){ while (x <= NM){ mn[x] = min(mn[x], val); x += x & (-x); } } int get_sum(int sum[NM+5], int x){ int res = 0; while (x > 0){ res += sum[x]; x -= x & (-x); } return res; } int get_mn(int mn[NM+5], int x){ int res = +inf; while (x > 0){ res = min(res, mn[x]); x -= x & (-x); } return res; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> N; for (int i = 1; i <= N; i++){ int x, y; cin >> x >> y; r[x] = y; } for (int i = 1; i <= NM; i++) mn[i] = mn2[i] = +inf; for (int i = 2*N; i >= 1; i--){ if (r[i] == 0) continue; cnt += get_sum(suml, r[i])-get_sum(sumr, r[i]); update_sum(suml, i); update_sum(sumr, r[i]); if (get_mn(mn2, 2*N-(r[i]+1)+1) <= r[i]){ cout << 0; return 0; } int tmp = get_mn(mn, 2*N-(r[i]+1)+1); if (tmp <= r[i]){ update_mn(mn2, 2*N-r[i]+1, tmp); } update_mn(mn, 2*N-r[i]+1, i); } assert(cnt < N); for (int i = 1; i <= N-cnt; i++) ans = ans*2%MOD; cout << ans; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...