This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |