Submission #876051

#TimeUsernameProblemLanguageResultExecution timeMemory
876051awuAlternating Current (BOI18_alternating)C++14
100 / 100
566 ms178980 KiB
#include <bits/extc++.h> using namespace std; #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2") #define int long long #define f first #define s second #define all(x) x.begin(), x.end() #define debug(x) do{auto y = x; cout << #x << " = " << y << endl;}while(0) // #define endl "\n" #define unordered_map __gnu_pbds::gp_hash_table using pii = pair<int, int>; const int inf = 1ll << 60; const int MOD = 1e9 + 7; struct segtree { vector<int> t, lz; segtree(int s) { int n = 1; while(n < s) n *= 2; t.resize(n * 2); lz.resize(n * 2); } void push(int n, int tl, int tr) { t[n] += lz[n]; if(tl + 1 != tr) { lz[n * 2] += lz[n]; lz[n * 2 + 1] += lz[n]; } lz[n] = 0; } void inc(int ul, int ur, int n = 1, int tl = 0, int tr = -1) { if(ul >= ur) { inc(ul, inf); inc(0, ur); return; } if(tr == -1) tr = t.size() / 2; if(ul >= tr || ur <= tl) return; if(ul <= tl && ur >= tr) { lz[n]++; return; } push(n, tl, tr); int tm = (tl + tr) / 2; inc(ul, ur, n * 2, tl, tm); inc(ul, ur, n * 2 + 1, tm, tr); push(n * 2, tl, tm); push(n * 2 + 1, tm, tr); t[n] = min(t[n * 2], t[n * 2 + 1]); } int query(int ql, int qr, int n = 1, int tl = 0, int tr = -1) { if(tr == -1) tr = t.size() / 2; if(ql >= tr || qr <= tl) return inf; push(n, tl, tr); if(ql <= tl && qr >= tr) return t[n]; int tm = (tl + tr) / 2; return min(query(ql, qr, n * 2, tl, tm), query(ql, qr, n * 2 + 1, tm, tr)); } }; struct interval_tree { vector<unordered_map<int, int>> t; interval_tree(int s) { int n = 1; while(n < s) n *= 2; t.resize(n * 2); } void update(int ul, int ur, int v, int n = 1, int tl = 0, int tr = -1) { if(ul >= ur) { update(ul, inf, v); update(0, ur, v); return; } if(tr == -1) tr = t.size() / 2; if(ul >= tr || ur <= tl) return; if(ul <= tl && ur >= tr) { t[n][v] = 0; return; } int tm = (tl + tr) / 2; update(ul, ur, v, n * 2, tl, tm); update(ul, ur, v, n * 2 + 1, tm, tr); } void erase(int ul, int ur, int v, int n = 1, int tl = 0, int tr = -1) { if(ul >= ur) { erase(ul, inf, v); erase(0, ur, v); return; } if(tr == -1) tr = t.size() / 2; if(ul >= tr || ur <= tl) return; if(ul <= tl && ur >= tr) { t[n].erase(v); return; } int tm = (tl + tr) / 2; erase(ul, ur, v, n * 2, tl, tm); erase(ul, ur, v, n * 2 + 1, tm, tr); } int cnt(int i, int n = 1, int tl = 0, int tr = -1) { if(tr == -1) tr = t.size() / 2; if(tl + 1 == tr) return t[n].size(); int tm = (tl + tr) / 2; if(i < tm) return t[n].size() + cnt(i, n * 2, tl, tm); return t[n].size() + cnt(i, n * 2 + 1, tm, tr); } pii get(int i, int n = 1, int tl = 0, int tr = -1) { if(tr == -1) tr = t.size() / 2; pii ret = {-1, -1}; if(tl + 1 != tr) { int tm = (tl + tr) / 2; if(i < tm) ret = get(i, n * 2, tl, tm); else ret = get(i, n * 2 + 1, tm, tr); } for(auto i : t[n]) { if(ret.s != -1 && ret.f != -1) return ret; if(ret.f == -1) ret.f = i.f; else ret.s = i.f; } return ret; } }; void die() { cout << "impossible" << endl; exit(0); } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); int n, m; cin >> n >> m; vector<pii> rs(m); interval_tree intr(n); for(int i = 0; i < m; i++) { int a, b; cin >> a >> b; a--; rs[i] = {a, b}; intr.update(a, b, i); } segtree st1(n), st2(n); deque<int> ids; for(int i = 0; i < n; i++) { int c = intr.cnt(i); if(c < 2) die(); if(c == 2) ids.push_back(i); } vector<int> which(m); while(ids.size()) { int i; pii x = intr.get(ids.front()); if(which[x.f] || which[x.s]) { i = ids[0]; ids.pop_front(); } else { i = ids.back(); ids.pop_back(); x = intr.get(i); } if(!which[x.f]) { if(which[x.s] != 1) { st1.inc(rs[x.f].f, rs[x.f].s); which[x.f] = 1; } else { st2.inc(rs[x.f].f, rs[x.f].s); which[x.f] = 2; } } if(!which[x.s]) { if(which[x.f] != 2) { st2.inc(rs[x.s].f, rs[x.s].s); which[x.s] = 2; } else { st1.inc(rs[x.s].f, rs[x.s].s); which[x.s] = 1; } } } for(int i = 0; i < m; i++) { if(!which[i]) continue; intr.erase(rs[i].f, rs[i].s, i); } for(int i = 0; i < n; i++) { pii x = intr.get(i); if(st1.query(i, i + 1) == 0) { if(x.f == -1) die(); st1.inc(rs[x.f].f, rs[x.f].s); which[x.f] = 1; intr.erase(rs[x.f].f, rs[x.f].s, x.f); swap(x.f, x.s); } if(st2.query(i, i + 1) == 0) { if(x.f == -1) die(); st2.inc(rs[x.f].f, rs[x.f].s); which[x.f] = 2; intr.erase(rs[x.f].f, rs[x.f].s, x.f); } } for(auto i = 0; i < m; i++) { cout << which[i] % 2; } cout << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...