#include<bits/stdc++.h>
using namespace std;
#ifdef DEBUG
auto&operator <<(auto& o, pair<auto, auto> p) {return o<<"("<<p.first<<", "<<p.second<<")";}
auto operator <<(auto& o, auto x)->decltype(x.end(), o) {o<<"{"; for(auto v : x) o<<v<<", "; return o<<"}";}
#define debug(X) cout<<"["#X"]"<<X<<endl;
#else
#define debug(X) {}
#endif
#define int long long
const int base = 1<<19;
struct segtree
{
vector<pair<int, int> > tree;
segtree(){tree.resize(base*2+10, {0, -1});}
void add(int w, pair<int, int> val)
{
w += base;
if(tree[w] < val) tree[w] = val;
w /= 2;
while(w != 0)
{
tree[w] = max(tree[w*2], tree[w*2+1]);
w /= 2;
}
}
pair<int, int> query(int w, int p, int k, int x, int y)
{
if(p > y || k < x) return {0, -1};
if(x <= p && k <= y) return tree[w];
return max(query(w*2, p, (p+k)/2, x, y),
query(w*2+1, (p+k)/2+1, k, x, y));
}
};
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, m;
cin>>n>>m;
map<int, int> scl;
vector<pair<int, int> > vals(n);
for(auto& v : vals) cin>>v.first>>v.second;
for(auto& v : vals) scl[v.first] = 1, scl[v.second] = 1;
int cnt = 0;
for(auto& v : scl) v.second = cnt++;
for(auto& v : vals) v.first = scl[v.first], v.second = scl[v.second];
debug(vals);
segtree A;
for(auto& v : vals)
if(v.second < v.first)
{A.add(v.first, make_pair(v.second + cnt, (int)(&v - &vals[0])));}
else
{A.add(v.first, make_pair(v.second, (int)(&v - &vals[0])));}
vector par(n, vector(20, -1));
for(auto& v : vals)
{
debug((int)(&v - &vals[0]));
if(v.second < v.first)
{
auto a1 = A.query(1, 0, base-1, v.first, base-1);
auto a2 = A.query(1, 0, base-1, 0, v.second);
if(a2.second != -1){par[(int)(&v - &vals[0])][0] = a2.second;}
else par[(int)(&v - &vals[0])][0] = a1.second;
}
else
par[(int)(&v - &vals[0])][0] =
A.query(1, 0, base-1, v.first, v.second).second;
}
int result = 1e9+7;
auto check = [&](int p, int k, int x)
{
if(k < p)
return x >= p || x <= k;
else
return p <= x && x <= k;
};
for(int i=0;i<n;i++)
if(check(vals[i].first, vals[i].second, vals[par[i][0]].second))
{cout<<2; return 0;}
for(int i=1;i<20;i++)
for(int j=0;j<n;j++)
{
par[j][i] = par[par[j][i-1]][i-1];
if(check(vals[j].first, vals[j].second, vals[par[j][i]].second))
{result = min(result, (1LL<<(i+1))); return 0;}
}
cout<<result;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
6 ms |
16732 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
6 ms |
16732 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
6 ms |
16732 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
6 ms |
16728 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
6 ms |
16728 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
6 ms |
16732 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
