#include<bits/stdc++.h>
#define fr first
#define sc second
using namespace std;
const int N = 200010;
struct Segtree{
pair <int, int> tree[4*N]; int lazy[4*N];
pair <int, int> join(pair <int, int> a, pair <int, int> b){
if(a.fr < b.fr) return a;
else if(b.fr < a.fr) return b;
if(a.sc < b.sc) return a;
return b;
}
void unlazy(int node, int l, int r){
if(lazy[node] == 0) return;
tree[node].first = lazy[node];
tree[node].second = l;
if(l != r){
lazy[2*node] = lazy[node];
lazy[2*node+1] = lazy[node];
}
lazy[node] = 0;
}
void build(int node, int l,int r){
lazy[node] = 0;
if(l == r){
tree[node] = {0, l};
return;
}
int mid = (l+r)/2;
build(2*node, l, mid);
build(2*node+1, mid+1, r);
tree[node] = join(tree[2*node], tree[2*node+1]);
return;
}
void update(int node, int l, int r, int tl, int tr, int val){
unlazy(node, tl, tr);
if(l > tr or tl > r) return;
if(l <= tl and tr <= r){
lazy[node] = val;
unlazy(node, tl, tr);
return;
}
int mid = (tl+tr)/2;
update(2*node, l, r, tl, mid, val);
update(2*node+1, l, r, mid+1,tr, val);
tree[node] = join(tree[2*node], tree[2*node+1]);
return;
}
pair <int, int> query(int node, int l, int r, int tl, int tr){
unlazy(node, tl, tr);
if(l > tr or tl > r) return {2, 0};
if(l <= tl and tr <= r) return tree[node];
int mid = (tl+tr)/2;
return join(query(2*node, l, r, tl, mid), query(2*node+1, l, r, mid+1, tr));
}
} seg[2];
struct Segtree2{
pair <int, int> tree[4*N]; int lazy[4*N];
pair <int, int> join(pair <int, int> a, pair <int, int> b){
if(a.fr < b.fr) return a;
if(a.fr > b.fr) return b;
return a;
}
void unlazy(int node, int l, int r){
tree[node].first += lazy[node];
if(l != r){
lazy[2*node] += lazy[node];
lazy[2*node+1] += lazy[node];
}
lazy[node] = 0;
}
void build(int node, int l,int r){
lazy[node] = 0;
if(l == r){
tree[node] = {0, l};
return;
}
int mid = (l+r)/2;
build(2*node, l, mid);
build(2*node+1, mid+1, r);
tree[node] = join(tree[2*node], tree[2*node+1]);
return;
}
void update(int node, int l, int r, int tl, int tr, int val){
unlazy(node, tl, tr);
if(l > tr or tl > r) return;
if(l <= tl and tr <= r){
lazy[node] += val;
unlazy(node, tl, tr);
return;
}
int mid = (tl+tr)/2;
update(2*node, l, r, tl, mid, val);
update(2*node+1, l, r, mid+1,tr, val);
tree[node] = join(tree[2*node], tree[2*node+1]);
return;
}
pair <int, int> query(int node, int l, int r, int tl, int tr){
unlazy(node, tl, tr);
if(l > tr or tl > r) return {1e9, 0};
if(l <= tl and tr <= r) return tree[node];
int mid = (tl+tr)/2;
return join(query(2*node, l, r, tl, mid), query(2*node+1, l, r, mid+1, tr));
}
} segint;
vector <array <int, 3>> intervalos;
int res[N];
int main(){
int n, m;
cin >> n >> m;
for(int i = 1;i <= m;i++){
int a, b;
cin >> a >> b;
intervalos.push_back({a, -b, i-1});
}
sort(intervalos.begin(), intervalos.end());
for(int i = 0;i < m;i++){
intervalos[i][1] *= -1;
}
segint.build(1, 1, n);
for(auto [a, b, i] : intervalos){
if(b > a){
segint.update(1, a, b-1, 1, n, 1);
}
else if(b < a){
segint.update(1, a, n, 1, n, 1);
if(b == 1) continue;
segint.update(1, 1, b-1, 1, n, 1);
}
}
pair <int, int> t = segint.query(1, 1, n, 1, n);
if(t.fr <= 1){
seg[0].build(1, 1, n);
seg[1].build(1, 1, n);
int st = t.sc+1;
//cout << st << '\n';
if(st > n) st = 1;
map <int, int> aux;
for(int i = 1;i <= n;i++){
aux[i] = i + (i<st ? n : 0) - (st-1);
}
array <int, 3> amigao = {-1, -1, -1};
vector <array <int, 3>> aaa;
for(int i = 0;i < m;i++){
intervalos[i][0] = aux[intervalos[i][0]];
intervalos[i][1] = aux[intervalos[i][1]];
if(intervalos[i][1] < intervalos[i][0]){
amigao = intervalos[i];
}
else{
aaa.push_back({intervalos[i][1], intervalos[i][0], intervalos[i][2]});
}
}
intervalos = aaa;
sort(intervalos.begin(), intervalos.end());
for(int i = 0;i < intervalos.size();i++){
swap(intervalos[i][0], intervalos[i][1]);
}
if(amigao[0] != -1){
res[amigao[2]] = 0;
seg[0].update(1, amigao[0], n, 1, n, 1);
seg[0].update(1, 1, amigao[1], 1, n, 1);
//cout << amigao[0] << ' ' << amigao[1] << '\n';
}
for(int i = 0;i < intervalos.size();i++){
auto [l, r, _] = intervalos[i];
//cout << l << ' ' << r << ' ';
pair <int, int> a = seg[0].query(1, l, r, 1, n);
pair <int, int> b = seg[1].query(1, l, r, 1, n);
//cout << a.fr << ' ' << a.sc << ' ' << b.fr << ' '<< b.sc << '\n';
if(a.fr == 1 and b.fr == 1){
res[_] = 0;
continue;
}
else if(a.fr == 1 and b.fr == 0){
res[_] = 1;
seg[1].update(1, l, r, 1, n, 1);
}
else if(a.fr == 0 and b.fr == 1){
res[_] = 0;
seg[0].update(1, l, r, 1, n, 1);
}
else{
if(a.sc <= b.sc){
res[_] = 0;
seg[0].update(1, l, r, 1, n, 1);
}
else{
res[_] = 1;
seg[1].update(1, l, r, 1, n, 1);
}
}
}
if(seg[0].query(1, 1, n, 1, n).fr != 1 or seg[1].query(1, 1, n, 1, n).fr != 1){
seg[0].build(1, 1, n);
seg[1].build(1, 1, n);
vector <array <int, 3>> aaa;
for(int i = 0;i < m;i++){
intervalos[i][0] = aux[intervalos[i][0]];
intervalos[i][1] = aux[intervalos[i][1]];
if(intervalos[i][1] < intervalos[i][0]){
}
else{
aaa.push_back({intervalos[i][0], -intervalos[i][1], intervalos[i][2]});
}
}
intervalos = aaa;
sort(intervalos.begin(), intervalos.end());
for(int i = 0;i < intervalos.size();i++){
intervalos[i][1] *= -1;
}
if(amigao[0] != -1){
res[amigao[2]] = 0;
seg[0].update(1, amigao[0], n, 1, n, 1);
seg[0].update(1, 1, amigao[1], 1, n, 1);
// cout << amigao[0] << ' ' << amigao[1] << '\n';
}
for(int i = 0;i < intervalos.size();i++){
auto [l, r, _] = intervalos[i];
//cout << l << ' ' << r << ' ';
pair <int, int> a = seg[0].query(1, l, r, 1, n);
pair <int, int> b = seg[1].query(1, l, r, 1, n);
//cout << a.fr << ' ' << a.sc << ' ' << b.fr << ' '<< b.sc << '\n';
if(a.fr == 1 and b.fr == 1){
res[_] = 0;
continue;
}
else if(a.fr == 1 and b.fr == 0){
res[_] = 1;
seg[1].update(1, l, r, 1, n, 1);
}
else if(a.fr == 0 and b.fr == 1){
res[_] = 0;
seg[0].update(1, l, r, 1, n, 1);
}
else{
if(a.sc <= b.sc){
res[_] = 0;
seg[0].update(1, l, r, 1, n, 1);
}
else{
res[_] = 1;
seg[1].update(1, l, r, 1, n, 1);
}
}
}
if(seg[0].query(1, 1, n, 1, n).fr != 1 or seg[1].query(1, 1, n, 1, n).fr != 1){
cout << "impossible\n";
return 0;
}
}
for(int i = 0;i < m;i++){
cout << res[i];
}
cout << '\n';
return 0;
}
else{
for(int i = 0;i < m;i++){
if(intervalos[i][1] < intervalos[i][0]) intervalos[i][1] += n;
intervalos[i][1] *= -1;
}
sort(intervalos.begin(), intervalos.end());
for(int i = 0;i < m;i++){
intervalos[i][1] *= -1;
if(intervalos[i][1] > n) intervalos[i][1] -= n;
}
seg[0].build(1, 1, n);
seg[1].build(1, 1, n);
for(int i = 0;i < intervalos.size();i++){
auto [l, r, _] = intervalos[i];
if(l < r){
pair <int, int> a = seg[0].query(1, l, r, 1, n);
pair <int, int> b = seg[1].query(1, l, r, 1, n);
if(a.fr == 1 and b.fr == 1){
res[_] = 0;
continue;
}
else if(a.fr == 1 and b.fr == 0){
res[_] = 1;
seg[1].update(1, l, r, 1, n, 1);
}
else if(a.fr == 0 and b.fr == 1){
res[_] = 0;
seg[0].update(1, l, r, 1, n, 1);
}
else{
if(a.sc < b.sc){
res[_] = 0;
seg[0].update(1, l, r, 1, n, 1);
}
else{
res[_] = 1;
seg[1].update(1, l, r, 1, n, 1);
}
}
}
else{
pair <int, int> a = seg[0].query(1, l, n, 1, n);
pair <int, int> b = seg[1].query(1, l, n, 1, n);
if(a.fr == 1 and b.fr == 1){
a = seg[0].query(1, 1, r, 1, n);
b = seg[1].query(1, 1, r, 1, n);
if(a.fr == 1 and b.fr == 1){
res[_] = 0;
continue;
}
else if(a.fr == 1 and b.fr == 0){
res[_] = 1;
seg[1].update(1, l, n, 1, n, 1);
seg[1].update(1, 1, r, 1, n, 1);
}
else if(a.fr == 0 and b.fr == 1){
res[_] = 0;
seg[0].update(1, l, n, 1, n, 1);
seg[0].update(1, 1, r, 1, n, 1);
}
else{
if(a.sc < b.sc){
res[_] = 0;
seg[0].update(1, l, n, 1, n, 1);
seg[0].update(1, 1, r, 1, n, 1);
}
else{
res[_] = 1;
seg[1].update(1, l, n, 1, n, 1);
seg[1].update(1, 1, r, 1, n, 1);
}
}
continue;
}
else if(a.fr == 1 and b.fr == 0){
res[_] = 1;
seg[1].update(1, l, n, 1, n, 1);
seg[1].update(1, 1, r, 1, n, 1);
}
else if(a.fr == 0 and b.fr == 1){
res[_] = 0;
seg[0].update(1, l, n, 1, n, 1);
seg[0].update(1, 1, r, 1, n, 1);
}
else{
if(a.sc < b.sc){
res[_] = 0;
seg[0].update(1, l, n, 1, n, 1);
seg[0].update(1, 1, r, 1, n, 1);
}
else{
res[_] = 1;
seg[1].update(1, l, n, 1, n, 1);
seg[1].update(1, 1, r, 1, n, 1);
}
}
}
}
for(int i = 0;i < m;i++){
cout << res[i];
}
cout << '\n';
}
}
Compilation message
alternating.cpp: In function 'int main()':
alternating.cpp:163:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
163 | for(int i = 0;i < intervalos.size();i++){
| ~~^~~~~~~~~~~~~~~~~~~
alternating.cpp:172:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
172 | for(int i = 0;i < intervalos.size();i++){
| ~~^~~~~~~~~~~~~~~~~~~
alternating.cpp:217:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
217 | for(int i = 0;i < intervalos.size();i++){
| ~~^~~~~~~~~~~~~~~~~~~
alternating.cpp:226:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
226 | for(int i = 0;i < intervalos.size();i++){
| ~~^~~~~~~~~~~~~~~~~~~
alternating.cpp:278:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
278 | for(int i = 0;i < intervalos.size();i++){
| ~~^~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
22096 KB |
Output is correct |
| 2 |
Correct |
9 ms |
22096 KB |
Output is correct |
| 3 |
Correct |
9 ms |
22096 KB |
Output is correct |
| 4 |
Correct |
8 ms |
22096 KB |
Output is correct |
| 5 |
Correct |
14 ms |
21072 KB |
Output is correct |
| 6 |
Incorrect |
14 ms |
21072 KB |
'impossible' claimed, but there is a solution |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
22096 KB |
Output is correct |
| 2 |
Correct |
9 ms |
22096 KB |
Output is correct |
| 3 |
Correct |
9 ms |
22096 KB |
Output is correct |
| 4 |
Correct |
8 ms |
22096 KB |
Output is correct |
| 5 |
Correct |
14 ms |
21072 KB |
Output is correct |
| 6 |
Incorrect |
14 ms |
21072 KB |
'impossible' claimed, but there is a solution |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
22096 KB |
Output is correct |
| 2 |
Correct |
9 ms |
22096 KB |
Output is correct |
| 3 |
Correct |
9 ms |
22096 KB |
Output is correct |
| 4 |
Correct |
8 ms |
22096 KB |
Output is correct |
| 5 |
Correct |
14 ms |
21072 KB |
Output is correct |
| 6 |
Incorrect |
14 ms |
21072 KB |
'impossible' claimed, but there is a solution |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
101 ms |
32444 KB |
Output is correct |
| 2 |
Correct |
23 ms |
30300 KB |
Output is correct |
| 3 |
Correct |
141 ms |
32576 KB |
Output is correct |
| 4 |
Correct |
112 ms |
31936 KB |
Output is correct |
| 5 |
Correct |
205 ms |
34624 KB |
Output is correct |
| 6 |
Correct |
218 ms |
34620 KB |
Output is correct |
| 7 |
Incorrect |
183 ms |
35476 KB |
'impossible' claimed, but there is a solution |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
22096 KB |
Output is correct |
| 2 |
Correct |
9 ms |
22096 KB |
Output is correct |
| 3 |
Correct |
9 ms |
22096 KB |
Output is correct |
| 4 |
Correct |
8 ms |
22096 KB |
Output is correct |
| 5 |
Correct |
14 ms |
21072 KB |
Output is correct |
| 6 |
Incorrect |
14 ms |
21072 KB |
'impossible' claimed, but there is a solution |
| 7 |
Halted |
0 ms |
0 KB |
- |
