#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pll;
#define fastio ios::sync_with_stdio(false), cin.tie(0)
#define pb push_back
#define eb emplace_back
#define f first
#define s second
#define int long long
#define lowbit(x) x&-x
const int maxn = 1e5 + 5;
const int INF = 1e18;
int n, m;
struct seg{
int l, r, id;
seg(){}
seg(int _l, int _r, int _id) : l(_l), r(_r), id(_id){
if(r < l) r += n;
}
bool operator < (const seg& other) const{
if(l != other.l) return l < other.l;
return r < other.r;
}
};
class comp{
public:
bool operator ()(seg a, seg b){
if(a.r != b.r) return a.r < b.r;
else return a.l < b.l;
}
};
int st[maxn * 4], tag[maxn * 4];
void cast(int val, int v){
st[v] += val, tag[v] += val;
}
void push(int v){
if(tag[v]){
cast(tag[v], v * 2);
cast(tag[v], v * 2 + 1);
tag[v] = 0;
}
}
void upd(int l, int r, int val, int v = 1, int L = 0, int R = n - 1){
if(l > R || r < L) return;
if(l <= L && r >= R){
st[v] += val, tag[v] += val;
return;
}
push(v);
int m = (L + R) / 2;
upd(l, r, val, v * 2, L, m);
upd(l, r, val, v * 2 + 1, m + 1, R);
st[v] = min(st[v * 2], st[v * 2 + 1]);
}
int qry(int l, int r, int v = 1, int L = 0, int R = n - 1){
if(l > R || r < L) return INF;
if(l <= L && r >= R) return st[v];
push(v);
int m = (L + R) / 2;
return min(qry(l, r, v * 2, L, m), qry(l, r, v * 2 + 1, m + 1, R));
}
void insert(int l, int r, int val){
l %= n, r %= n;
if(l <= r) upd(l, r, val);
else upd(l, n - 1, val), upd(0, r, val);
}
bool ck(seg a){
a.l %= n, a.r %= n;
if(a.l <= a.r) return qry(a.l, a.r) >= 2;
else return min(qry(a.l, n - 1), qry(0, a.r)) >= 2;
}
int getlen(int a, int b){
return (b - a + n) % n + 1;
}
signed main(void){
fastio;
cin>>n>>m;
vector<seg> e;
int mx = -INF;
int st = 0;
for(int i = 0; i < m; i++){
int a, b;
cin>>a>>b;
a--, b--;
if(getlen(a, b) > mx) mx = getlen(a, b), st = a;
insert(a, b, 1);
e.pb(seg(a, b, i));
}
if(qry(0, n - 1) < 2){
cout<<"impossible\n";
return 0;
}
for(int i = 0; i < m; i++){
if(e[i].l >= st) continue;
e[i].l += n, e[i].r += n;
// if(e[i].l < st) e[i].l += n;
// if(e[i].r < e[i].l) e[i].r += n;
// cout<<e[i].l<<" "<<e[i].r<<"\n";
}
sort(e.begin(), e.end());
assert(e[0].l == st);
int r = e[0].l - 1;
vector<int> ans(m);
int id = 0;
priority_queue<seg, vector<seg>, comp> q;
int dist = 0;
while(true){
// cout<<"r : "<<r<<"\n";
while(id < m && e[id].l <= r + 1){
// cout<<"push : "<<e[id].l<<" "<<e[id].r<<" "<<e[id].id<<"\n";
q.push(e[id]);
id++;
}
while(true){
if(q.empty()){
cout<<"impossible\n";
return 0;
}
seg cur = q.top(); q.pop();
if(!ck(cur)) continue;
if(cur.r <= r) continue;
// cout<<"use : "<<cur.l<<" "<<cur.r<<" "<<cur.id<<"\n";
insert(cur.l, cur.r, -1);
ans[cur.id] = 1;
dist += cur.r - r;
r = cur.r;
break;
}
// cout<<dist<<"\n";
if(dist >= n) break;
}
cout<<"ok\n";
// for(auto x : ans) cout<<x;
// cout<<"\n";
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
2396 KB |
ok is not a string of length exactly 15 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
2396 KB |
ok is not a string of length exactly 15 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
2396 KB |
ok is not a string of length exactly 15 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
19 ms |
11980 KB |
ok is not a string of length exactly 100000 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
2396 KB |
ok is not a string of length exactly 15 |
| 2 |
Halted |
0 ms |
0 KB |
- |
