#include <bits/stdc++.h>
#define ff first
#define ss second
#define int ll
#define INF INT_MAX
#define MAX 1000001
#define MOD 1000000007
using namespace std;
typedef long long ll;
int n,m,k,a[MAX],b[MAX];
struct segtree{
int sz;
vector<int> mn,lazy;
void init(int n){
sz=1;
while(sz<n){
sz*=2;
}
mn.resize(2*sz,0);
lazy.resize(2*sz,0);
}
void propogate(int x,int lx,int rx){
if(rx-lx==1 || lazy[x]==0){
return;
}
mn[2*x+1]+=lazy[x];
mn[2*x+2]+=lazy[x];
lazy[2*x+1]+=lazy[x];
lazy[2*x+2]+=lazy[x];
lazy[x]=0;
}
void upd(int x,int lx,int rx,int l,int r,int v){
propogate(x,lx,rx);
if(lx>=r || rx<=l){
return;
}
if(lx>=l && rx<=r){
mn[x]+=v;
lazy[x]+=v;
return;
}
int mid=(lx+rx)/2;
upd(2*x+1,lx,mid,l,r,v);
upd(2*x+2,mid,rx,l,r,v);
mn[x]=min(mn[2*x+1],mn[2*x+2]);
}
void upd(int l,int r,int v){
upd(0,0,sz,l,r,v);
}
int get_min(int x,int lx,int rx,int l,int r){
propogate(x,lx,rx);
if(lx>=r || rx<=l){
return INF;
}
if(lx>=l && rx<=r){
return mn[x];
}
int mid=(lx+rx)/2;
int m1,m2;
m1=get_min(2*x+1,lx,mid,l,r);
m2=get_min(2*x+2,mid,rx,l,r);
return min(m1,m2);
}
int get_min(int l,int r){
return get_min(0,0,sz,l,r);
}
};
segtree st,st1;
void f(int l,int r,int v){
st1.upd(0,r+1,v);
st1.upd(l,n,v);
}
void solve(){
cin >> n >> m;
vector<array<int,3>> c,d;
st.init(n);
st1.init(n);
for(int i=0;i<m;i++){
int x,y;
cin >> x >> y;
x--;
y--;
if(x>y){
f(x,y,1);
d.push_back({x,y,i});
continue;
}
c.push_back({x,y,i});
st.upd(x,y+1,1);
}
sort(c.begin(),c.end());
if(st.get_min(0,n)==2){
int j=0;
for(int i=0;i<n;i++){
while(j<(int)c.size() && c[j][0]!=i){
j++;
}
while(j<(int)c.size() && st.get_min(i,n)==2){
st.upd(c[j][0],c[j][1],-1);
a[c[j][2]]=1;
j++;
}
}
for(int i=0;i<m;i++){
cout << a[i];
}
return;
}
cout << "impossible" << "\n";
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
int t=1;
//cin >> t;
while(t--){
solve();
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
'impossible' claimed, but there is a solution |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
'impossible' claimed, but there is a solution |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
'impossible' claimed, but there is a solution |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
34 ms |
12488 KB |
'impossible' claimed, but there is a solution |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
'impossible' claimed, but there is a solution |
| 2 |
Halted |
0 ms |
0 KB |
- |
