#include <set>
#include <cstdio>
#include <vector>
#include <utility>
#include <iterator>
#include <algorithm>
using namespace std;
int tree[262144], lazy[262144];
void propagate(int i, int b, int e) {
if (!lazy[i]) return;
if (b != e) {
lazy[i * 2 + 1] += lazy[i * 2 + 1], lazy[i];
lazy[i * 2 + 2] += lazy[i * 2 + 2], lazy[i];
}
tree[i] += lazy[i];
lazy[i] = 0;
}
int query(int i, int b, int e, int l, int r) {
propagate(i, b, e);
if (r < b || e < l) return 0;
if (l <= b && e <= r) return tree[i];
int m = (b + e) / 2;
return min(query(i * 2 + 1, b, m, l, r), query(i * 2 + 2, m + 1, e, l, r));
}
int update(int i, int b, int e, int l, int r, int v) {
propagate(i, b, e);
if (r < b || e < l) return tree[i];
if (l <= b && e <= r) {
lazy[i] += v;
propagate(i, b, e);
return tree[i];
}
int m = (b + e) / 2;
return tree[i] = min(update(i * 2 + 1, b, m, l, r, v), update(i * 2 + 2, m + 1, e, l, r, v));
}
int n, m, x[100006], y[100006];
vector<int> adj[100006];
set<int> s;
vector<pair<int, int>> v;
int cl[100006];
bool dfs(int x) {
for (auto &i: adj[x]) {
if (!cl[i]) {
cl[i] = -cl[x];
if (dfs(i)) return true;
} else if (cl[i] == cl[x]) return true;
}
return false;
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 0; i < m; i++) {
scanf("%d%d", x + i, y + i);
x[i]--, y[i]--;
if (x[i] > y[i]) s.insert(i);
v.push_back({ x[i], -i - 1 });
v.push_back({ y[i], i });
}
sort(v.begin(), v.end());
int k = 0;
for (int i = 0; i < n; i++) {
while (k < (int)v.size() && v[k] < make_pair(i, 0)) {
if (v[k].second < 0) s.insert(-v[k].second - 1);
else s.erase(v[k].second);
k++;
}
if ((int)s.size() < 2) return puts("impossible"), 0;
if ((int)s.size() == 2) {
int first = *s.begin();
int second = *next(s.begin());
adj[first].push_back(second);
adj[second].push_back(first);
}
}
for (int i = 0; i < m; i++) if (!cl[i] && !adj[i].empty()) {
cl[i] = -1;
if (dfs(i)) return puts("impossible"), 0;
}
for (int i = 0; i < m; i++) if (cl[i] >= 0) {
if (x[i] <= y[i]) update(0, 0, 131071, x[i], y[i], 1);
else update(0, 0, 131071, 0, y[i], cl[i]), update(0, 0, 131071, x[i], n - 1, 1);
}
for (int i = 0; i < m; i++) if (!cl[i]) {
int t = 0;
if (x[i] <= y[i]) t = query(0, 0, 131071, x[i], y[i]);
else t = min(query(0, 0, 131071, 0, y[i]), query(0, 0, 131071, x[i], n - 1));
if (t > 1) cl[i] = -1;
else {
cl[i] = 1;
if (x[i] <= y[i]) update(0, 0, 131071, x[i], y[i], -1);
else update(0, 0, 131071, 0, y[i], cl[i]), update(0, 0, 131071, x[i], n - 1, -1);
}
}
for (int i = 0; i < m; i++) {
if (cl[i] == -1) printf("0");
else printf("1");
}
}
Compilation message
alternating.cpp: In function 'void propagate(int, int, int)':
alternating.cpp:14:51: warning: right operand of comma operator has no effect [-Wunused-value]
14 | lazy[i * 2 + 1] += lazy[i * 2 + 1], lazy[i];
| ~~~~~~^
alternating.cpp:15:51: warning: right operand of comma operator has no effect [-Wunused-value]
15 | lazy[i * 2 + 2] += lazy[i * 2 + 2], lazy[i];
| ~~~~~~^
alternating.cpp: In function 'int main()':
alternating.cpp:58:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
58 | scanf("%d%d", &n, &m);
| ~~~~~^~~~~~~~~~~~~~~~
alternating.cpp:60:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
60 | scanf("%d%d", x + i, y + i);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2636 KB |
no wires in direction 0 between segments 1 and 15 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2636 KB |
no wires in direction 0 between segments 1 and 15 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2636 KB |
no wires in direction 0 between segments 1 and 15 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
90 ms |
10120 KB |
no wires in direction 0 between segments 1 and 100000 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2636 KB |
no wires in direction 0 between segments 1 and 15 |
| 2 |
Halted |
0 ms |
0 KB |
- |
