This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#include <chrono>
#include <random>
using namespace std;
#define F first
#define S second
#define pb push_back
#define vll vector<ll>
#define pll pair<ll, ll>
typedef long long ll;
ll n, m;
set<ll> lef;
set<ll> rig;
vector<pll> pts;
vector<pair<ll, pll>> seg;
vll con;
ll dumb;
bool inside(ll y){
if(lef.upper_bound(y)==lef.begin()) return 0;
auto it=prev(lef.upper_bound(y));
auto it2=rig.lower_bound(y);
if(it==lef.end() || it2==rig.end()){
return 0;
}
ll f=*it;
ll s=*it2;
if(f<s){
return 1;
}
return 0;
}
void solve(){
cin>>n>>m;
pts.resize(n);
for(ll i=0;i<n;i++){
cin>>pts[i].F>>pts[i].S;
con.pb(pts[i].F);
}
for(ll i=0;i<n-1;i++){
if(pts[i].F==pts[i+1].F){
seg.pb({pts[i].F, {min(pts[i].S, pts[i+1].S), max(pts[i].S, pts[i+1].S)}});
}
}
if(pts[n-1].F==pts[0].F){
seg.pb({pts[0].F, {min(pts[0].S, pts[n-1].S), max(pts[0].S, pts[n-1].S)}});
}
sort(seg.begin(), seg.end());
sort(con.begin(), con.end());
con.erase(unique(con.begin(), con.end()), con.end());
ll p=0;
dumb=0;
for(auto &x:con){
bool done=0;
while(p<n && seg[p].F<=x){
//cout<<"______\n";
//cout<<seg[p].F<<' '<<seg[p].S.F<<' '<<seg[p].S.S<<'\n';
if(x==0){
lef.insert(seg[p].S.F);
rig.insert(seg[p].S.S);
if((seg[p].S.S-seg[p].S.F)%2==1){
dumb--;
}
}
else{
if(inside(seg[p].S.F) && inside(seg[p].S.S)){
//cout<<"bruh\n";
ll orgl=*prev(lef.upper_bound(seg[p].S.F));
ll orgr=*rig.lower_bound(seg[p].S.S);
if((seg[p].S.F-orgl)%2==1){
dumb--;
rig.insert(seg[p].S.F);
}
else if(seg[p].S.F-orgl==0){
lef.erase(orgl);
}
else{
rig.insert(seg[p].S.F);
}
if((orgr-seg[p].S.S)%2==1){
dumb--;
lef.insert(seg[p].S.S);
}
else if(seg[p].S.S-orgr==0){
rig.erase(orgr);
}
else{
lef.insert(seg[p].S.S);
}
}
else{
if(inside(seg[p].S.F)){
//cout<<"damn\n";
rig.erase(seg[p].S.F);
rig.insert(seg[p].S.S);
ll orgl=*prev(lef.lower_bound(seg[p].S.F));
if((seg[p].S.S-orgl)%2==0 && (seg[p].S.F-orgl)%2==1){
dumb++;
}
else if((seg[p].S.S-orgl)%2==1 && (seg[p].S.F-orgl)%2==0){
dumb--;
}
}
else{
//cout<<"hi\n";
lef.erase(seg[p].S.S);
lef.insert(seg[p].S.F);
ll orgr=*rig.lower_bound(seg[p].S.S);
if((orgr-seg[p].S.F)%2==0 && (orgr-seg[p].S.S)%2==1){
dumb++;
}
else if((orgr-seg[p].S.F)%2==1 && (orgr-seg[p].S.S)%2==0){
dumb--;
}
}
}
}
done=1;
p++;
/*cout<<x<<'\n';
for(auto &it:lef){
cout<<it<<' ';
}
cout<<'\n';
for(auto &it:rig){
cout<<it<<' ';
}
cout<<'\n';*/
}
if(x%2==1 && done){
cout<<x-1<<'\n';
return;
}
auto it=lef.begin();
for(auto &r:rig){
if((r-*it)%2==1){
cout<<x<<'\n';
return;
}
it=next(it);
}
}
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
solve();
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... |