#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define MASK(i) (1ULL << (i))
#define GETBIT(mask, i) (((mask) >> (i)) & 1)
#define ALL(v) (v).begin(), (v).end()
ll max(ll a, ll b){return (a > b) ? a : b;}
ll min(ll a, ll b){return (a < b) ? a : b;}
ll gcd(ll a, ll b){return __gcd(abs(a), abs(b));}
ll lcm(ll a, ll b){return abs(a) / gcd(a, b) * abs(b);}
ll LASTBIT(ll mask){return (mask) & (-mask);}
int pop_cnt(ull mask){return __builtin_popcountll(mask);}
int ctz(ull mask){return __builtin_ctzll(mask);}
int logOf(ull mask){return 63 - __builtin_clzll(mask);}
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
ll rngesus(ll l, ll r){return l + (ull) rng() % (r - l + 1);}
template <class T1, class T2>
bool maximize(T1 &a, T2 b){
if (a < b) {a = b; return true;}
return false;
}
template <class T1, class T2>
bool minimize(T1 &a, T2 b){
if (a > b) {a = b; return true;}
return false;
}
template <class T>
void printArr(T container, string separator = " ", string finish = "\n", ostream &out = cout){
for(auto item: container) out << item << separator;
out << finish;
}
template <class T>
void remove_dup(vector<T> &a){
sort(ALL(a));
a.resize(unique(ALL(a)) - a.begin());
}
const int N = 6e5 + 69;
vector<pair<int,int>> queries[N];
int odd_range = 0;
set<pair<int,int>> S[2];
int del_range(int idx, pair<int,int> v){
int proc = 0;
while(true){
auto it = S[idx].lower_bound(make_pair(v.first, -1));
if (it == S[idx].begin()) break;
it--;
pair<int, int> cur = *it;
if (cur.second <= v.first) break;
proc++;
S[idx].erase(cur);
if ((cur.second - cur.first) % 2 == 1) odd_range--;
if (cur.second > v.second){
pair<int, int> left = make_pair(cur.first, v.first);
pair<int, int> right = make_pair(v.second, cur.second);
S[idx].insert(left); S[idx].insert(right);
if ((left.second - left.first) % 2 == 1) odd_range++;
if ((right.second - right.first) % 2 == 1) odd_range++;
}
else{
minimize(cur.second, v.first);
S[idx].insert(cur);
if ((cur.second - cur.first) % 2 == 1) odd_range++;
}
}
while(true){
auto it = S[idx].lower_bound(make_pair(v.first, -1));
if (it == S[idx].end()) break;
pair<int, int> cur = *it;
if (cur.first >= v.second) break;
proc++;
S[idx].erase(cur);
if ((cur.second - cur.first) % 2 == 1) odd_range--;
if (cur.second > v.second){
maximize(cur.first, v.second);
S[idx].insert(cur);
if ((cur.second - cur.first) % 2 == 1) odd_range++;
}
}
return proc > 0;
}
void add_range(int idx, pair<int, int> v){
auto it = S[idx].lower_bound(v);
if (it != S[idx].end() && (*it).first == v.second) {
pair<int, int> cur = *it;
S[idx].erase(cur);
if ((cur.second - cur.first) % 2 == 1) odd_range--;
v.second = cur.second;
}
it = S[idx].lower_bound(v);
if (it != S[idx].begin()){
it--;
if ((*it).second == v.first){
pair<int,int> cur = *it;
S[idx].erase(cur);
if ((cur.second - cur.first) % 2 == 1) odd_range--;
v.first = cur.first;
}
}
S[idx].insert(v);
if ((v.second - v.first) % 2 == 1) odd_range++;
}
int solve(){
int n, m; cin >> n >> m;
vector<pair<int,int>> a(n);
for(int i = 0; i < n; ++i) cin >> a[i].first >> a[i].second;
vector<int> X;
X.push_back(0);
X.push_back(m);
for(pair<int,int> i: a){
if (i.first > 0) X.push_back(i.first - 1);
X.push_back(i.first);
if (i.first < m) X.push_back(i.first + 1);
}
remove_dup(X);
for(int i = 0; i < n; ++i){
int j = (i + 1) % n;
if (a[i].first == a[j].first){
int idx = lower_bound(ALL(X), a[i].first) - X.begin();
int l = a[i].second, r = a[j].second;
if (l > r) swap(l, r);
queries[idx].push_back(make_pair(l, r));
}
}
int ans = 0;
for(int i = 0; i < (int) X.size(); ++i){
int cur_parity = X[i] % 2;
if (S[1 - cur_parity].empty()) maximize(ans, X[i]);
for(pair<int, int> j: queries[i]){
int cnt0 = del_range(0, j), cnt1 = del_range(1, j);
if (cnt0 && cnt1) return ans;
if (cnt0 + cnt1 == 0){
add_range(cur_parity, j);
}
}
if (odd_range > 0) return ans;
}
return ans;
}
int main(void){
ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
clock_t start = clock();
cout << solve() << "\n";
cerr << "Time elapsed: " << clock() - start << "ms!\n";
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |