Submission #1217601

#TimeUsernameProblemLanguageResultExecution timeMemory
1217601The_SamuraiPort Facility (JOI17_port_facility)C++20
10 / 100
2 ms584 KiB
// I stand with PALESTINE //#pragma GCC optimize("Ofast") //#pragma GCC optimize ("unroll-loops") //#pragma GCC target("avx,avx2") #include <bits/stdc++.h> //#include <ext/pb_ds/assoc_container.hpp> using namespace std; //using namespace __gnu_pbds; #define int long long #define ff first #define ss second #define sz(a) (int) (a).size() //template<class T, class C = null_type> using ordered_tree = tree<T, C, less<T>, rb_tree_tag, tree_order_statistics_node_update>; typedef long double ld; namespace io { template<typename F, typename S> ostream &operator<<(ostream &os, const pair<F, S> &p) { return os << p.ff << " " << p.ss; } template<typename F, typename S> ostream &operator<<(ostream &os, const map<F, S> &mp) { for (auto it: mp) { os << it << endl; } return os; } template<typename F> ostream &operator<<(ostream &os, const vector<F> &v) { bool space = false; for (F x: v) { if (space) os << " "; space = true; os << x; } return os; } template<typename F> ostream &operator<<(ostream &os, const deque<F> &d) { bool space = false; for (F x: d) { if (space) os << " "; space = true; os << x; } return os; } template<typename F> ostream &operator<<(ostream &os, const set<F> &st) { bool space = false; for (F x: st) { if (space) os << " "; space = true; os << x; } return os; } template<typename F> ostream &operator<<(ostream &os, const multiset<F> &st) { bool space = false; for (F x: st) { if (space) os << " "; space = true; os << x << x; } return os; } template<typename F, typename S> istream &operator>>(istream &is, pair<F, S> &p) { return is >> p.ff >> p.ss; } template<typename F> istream &operator>>(istream &is, vector<F> &v) { for (F &x: v) { is >> x; } return is; } long long fastread() { char c; long long d = 1, x = 0; do c = getchar(); while (c == ' ' || c == '\n'); if (c == '-') c = getchar(), d = -1; while (isdigit(c)) { x = x * 10 + c - '0'; c = getchar(); } return d * x; } static bool sep = false; using std::to_string; string to_string(bool x) { return (x ? "true" : "false"); } string to_string(const string &s) { return "\"" + s + "\""; } string to_string(const char *s) { return "\"" + string(s) + "\""; } string to_string(const char &c) { string s; s += c; return "\'" + s + "\'"; } template<typename Type> string to_string(vector<Type>); template<typename F, typename S> string to_string(pair<F, S>); template<typename Collection> string to_string(Collection); template<typename F, typename S> string to_string(pair<F, S> p) { return "{" + to_string(p.ff) + ", " + to_string(p.ss) + "}"; } template<typename Type> string to_string(vector<Type> v) { bool sep = false; string s = "["; for (Type x: v) { if (sep) s += ", "; sep = true; s += to_string(x); } s += "]"; return s; } template<typename Collection> string to_string(Collection collection) { bool sep = false; string s = "{"; for (auto x: collection) { if (sep) s += ", "; sep = true; s += to_string(x); } s += "}"; return s; } void print() { cout << endl; sep = false; } template<typename F, typename... Other> void print(F ff, Other... other) { if (sep) cout << " | "; sep = true; cout << to_string(ff); print(other...); } } using namespace io; namespace utils { template<typename F, typename S> inline void maxs(F &a, S b) { a = a > b ? a : b; } template<typename F, typename S> inline void mins(F &a, S b) { a = a < b ? a : b; } template<typename F, typename S> long long max(F a, S b) { return a > b ? a : b; } template<typename F, typename S> long long min(F a, S b) { return a < b ? a : b; } constexpr long long operator "" _E(unsigned long long n) { long long p = 1, a = 10; for (int i = 0; i < n; i++) p *= a; return p; } random_device rd; mt19937 mt(rd()); template<typename T> T rand(T l, T r) { uniform_int_distribution<T> dist(l, r); return dist(mt); }; } using namespace utils; #ifdef sunnatov #define print(...) cout << "[" << #__VA_ARGS__ << "]: "; io::print( __VA_ARGS__ ); #else #define print( ... ) 42 #endif const int mod = 9_E + 7; const double EPS = 1e-7; long long doxuya = 18_E + 10; int INF = 9_E + 10; const char nl = '\n'; int month[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; /* */ template<typename T> struct SegTree { vector<T> tree; int size; T neutral_element = -1e9; // sum - 0, mx - (-INF), mn - INF inline T merge(T a, T b) { return max(a, b); } void init(int n) { size = 1; while (size <= n) size *= 2; tree.assign(2 * size, neutral_element); } void build(vector<T> &a) { size = 1; while (size < a.size()) size *= 2; tree.assign(2 * size, neutral_element); for (int i = size; i < size + a.size(); i++) tree[i] = a[i - size]; for (int i = size - 1; i > 0; i--) tree[i] = merge(tree[i << 1], tree[i << 1 | 1]); } void upd(int p, T value) { // upd value at position p p += size; tree[p] = value; for (; p > 1; p >>= 1) tree[p >> 1] = merge(tree[p], tree[p ^ 1]); } T get(int l, int r) { // sum on interval [l, r] if (l > r) return neutral_element; T res = neutral_element; for (l += size, r += size + 1; l < r; l >>= 1, r >>= 1) { if (l & 1) res = merge(res, tree[l++]); if (r & 1) res = merge(res, tree[--r]); } return res; } }; int solve(int n, vector<pair<int, int>> a) { sort(a.begin(), a.end()); vector<vector<int>> g(n + 1); for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { // print(i, j, a[i], a[j]); if (a[j].ff < a[i].ss and a[i].ss < a[j].ss) { g[i].emplace_back(j); g[j].emplace_back(i); } } } vector vis(n, false); vector<int> color(n + 1, -1); auto dfs = [&](auto &dfs, int u) -> bool { if (color[u] == -1) color[u] = 0; vis[u] = true; for (int v: g[u]) { if (color[v] == -1) color[v] = 1 - color[u]; // print(u, v, color[u], color[v]); if (color[v] == color[u]) return false; if (!vis[v]) { if (!dfs(dfs, v)) return false; } } return true; }; print(g); int ans = 1; for (int i = 0; i < n; i++) { if (vis[i]) continue; if (!dfs(dfs, i)) ans = 0; else ans = ans * 2 % mod; } return ans; } void solution(istream &cin, ostream &cout, const int &test_case) { int n; cin >> n; vector<pair<int, int>> a(n); cin >> a; sort(a.begin(), a.end()); SegTree<int> sg; sg.init(2 * n + 1); vector<int> pos(2 * n + 1); for (int i = 0; i < n; i++) pos[a[i].ff] = pos[a[i].ss] = i; set<int, greater<>> st; for (int x = 1; x <= 2 * n; x++) { int i = pos[x]; if (a[i].ff == x) { if (sg.get(a[i].ff, a[i].ss) > a[i].ff) { // assert(solve(n, a) == 0); cout << 0; return; } auto it = st.lower_bound(a[i].ss); if (it != st.end()) sg.upd(a[i].ss, *it); st.insert(a[i].ss); } else { sg.upd(a[i].ss, -INF); } } sg.init(2 * n + 1); map<int, int> last; int sum = 0, ans = 1; last[0] = 0; for (int x = 1; x <= 2 * n; x++) { int i = pos[x]; // if (a[i].ff == x) cout << "("; // else cout << ")"; if (a[i].ff == x) { sum++; last[sum] = x; sg.upd(a[i].ff, a[i].ss); } else { sum--; // cout << x << ' ' << sum << ' ' << sg.get(last[sum] + 1, x) << endl; if (sg.get(last[sum] + 1, x) <= x) ans = ans * 2 % mod; last[sum] = x; } } // cout << nl; cout << ans; } int32_t main() { clock_t startTime = clock(); cin.tie(0)->sync_with_stdio(false); srand(time(0)); std::istream &in(std::cin); std::ostream &out(std::cout); int32_t queries = 1; #ifdef test_cases freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); cin >> queries; #else // cin >> queries; #endif for (int32_t test_case = 1; test_case <= queries; test_case++) { print(test_case); solution(cin, cout, test_case); cout << nl; } #ifdef sunnatov cout << "Time: " << (int) ((double) (clock() - startTime) / CLOCKS_PER_SEC * 1000) << " ms" << endl; #endif return EXIT_SUCCESS; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...