Submission #1248359

#TimeUsernameProblemLanguageResultExecution timeMemory
1248359chikien2009Port Facility (JOI17_port_facility)C++20
0 / 100
6092 ms320 KiB
#include <bits/stdc++.h> using namespace std; void setup() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); } struct SEGMENT_TREE { int tree[8000000]; inline void Update(int ind, int l, int r, int x, int v) { if (r < x || x < l) { return; } if (l == r) { tree[ind] = v; return; } int m = (l + r) >> 1; Update(ind << 1, l, m, x, v); Update(ind << 1 | 1, m + 1, r, x, v); tree[ind] = max(tree[ind << 1], tree[ind << 1 | 1]); } inline int Get(int ind, int l, int r, int x, int y) { if (r < x || y < l) { return 0; } if (x <= l && r <= y) { return tree[ind]; } int m = (l + r) >> 1; return max(Get(ind << 1, l, m, x, y), Get(ind << 1 | 1, m + 1, r, x, y)); } } st; int n, a[2000000], b; set<int> s; long long res = 1; const long long mod = 1e9 + 7; set<int>::iterator l, r; int main() { setup(); cin >> n; while (n > 5) { res++; } for (int i = 0, j; i < n; ++i) { cin >> j >> a[j]; } for (int i = 1; i <= 2 * n; ++i) { if (a[i] != 0) { s.insert(a[i]); l = s.lower_bound(i); r = s.lower_bound(a[i]); b = st.Get(1, 1, 2 * n, i, a[i]); if (i < b && b < a[i]) { cout << 0; return 0; } if (l == r) { (res *= 2) %= mod; continue; } r = prev(r); st.Update(1, 1, 2 * n, a[i], (*r)); } } cout << res; 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...