#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) {o<<"{"; for(auto v : x) o<<v<<", "; return o<<"}";}
#define debug(X) cerr<<"["#X"]: "<<X<<endl;
#else
#define debug(X) {}
#endif
#define int long long
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
set<pair<int, int> > segs[2]; //.first = koniec, .second = poczatek
vector<int> np(2);
int result = 0;
auto add = [&](int x, int y1, int y2)
{
x = x%2;
auto it = segs[x].insert({y2, y1}).first;
if(abs(y2 - y1)%2 == 1) np[x]++;
if(it != segs[x].begin())
{
it--;
if(it->first == y1)
{
if(abs(it->first - it->second)%2 == 1) np[x]--;
if(abs(y2 - y1)%2 == 1) np[x]--;
segs[x].erase(make_pair(it->first, it->second));
segs[x].erase(make_pair(y2, y1));
y1 = it->second;
it = segs[x].insert(make_pair(y2, y1)).first;
if(abs(y2 - y1)%2 == 1) np[x]++;
}
else
it++;
}
it++;
if(it != segs[x].end())
{
if(it->second == y2)
{
if(abs(it->first - it->second)%2 == 1) np[x]--;
if(abs(y1 - y2)%2 == 1) np[x]--;
segs[x].erase(make_pair(it->first, it->second));
segs[x].erase(make_pair(y2, y1));
y2 = it->first;
segs[x].insert(make_pair(y2, y1));
if(abs(y2 - y1)%2 == 1) np[x]++;
}
}
};
auto sub = [&](int x, int y1, int y2)
{
x = x%2; x^=1;
auto it1 = segs[x].upper_bound(make_pair(y1, -1));
if(it1 != segs[x].end() && it1->second <= y1) {cout<<result; exit(0);}
auto it2 = segs[x].upper_bound(make_pair(y2, -1));
if(it2 != segs[x].end() && it2->second <= y2) {cout<<result; exit(0);}
if(it1 != it2) {cout<<result; exit(0);}
x^=1;
vector<pair<int, int> > toAdd;
for(auto it = segs[x].upper_bound(make_pair(y1, -1)); it != segs[x].end()
&& it->second <= y2; ++it)
{
if(abs(it->first - it->second)%2 == 1) np[x]--;
if(it->second < y1)
{
if(abs(it->second - y1)%2 == 1) np[x]++;
toAdd.push_back(make_pair(y1, it->second));
}
if(it->first > y2)
{
if(abs(it->first - y2)%2 == 1) np[x]++;
toAdd.push_back(make_pair(it->first, y2));
}
}
for(auto v : toAdd) segs[x].insert(v);
};
int n, m;
cin>>n>>m;
vector<pair<int, int> > pts(n);
for(auto& v : pts) {cin>>v.first>>v.second;}
auto cmp = [&](pair<int, int> a, pair<int, int> b) {
if((int)a.second*b.first < (int)a.first*b.second) return true;
if((int)a.second*b.first > (int)a.first*b.second) return false;
return a < b;
};
if(!cmp(pts[0], pts[1])) reverse(pts.begin(), pts.end());
vector<pair<pair<int, bool>, pair<int, int> > > events;
for(int i=0;i<n;i++)
{
if(pts[i].first != pts[(i+1)%n].first) continue;
pair<pair<int, bool>, pair<int, int> > toAdd;
toAdd.second = make_pair(pts[i].second, pts[(i+1)%n].second);
if(pts[i].second < pts[(i+1)%n].second) toAdd.first.second = 1;
if(pts[i].second > pts[(i+1)%n].second) toAdd.first.second = 0;
toAdd.first.first = pts[i].first;
events.push_back(toAdd);
}
sort(events.begin(), events.end());
result = events[0].first.first;
int prev = -1;
for(auto& v : events)
{
if(prev != v.first.first)
{
if(np[0] == 0 && np[1] == 0 && segs[(v.first.first%2)^1].size() == 0)
{result = v.first.first;}
else if(np[0] == 0 && np[1] == 0 && segs[(v.first.first%2)].size() == 0)
result = v.first.first-1;
}
if(v.first.second == 1) add(v.first.first, v.second.first, v.second.second);
if(v.first.second == 0) sub(v.first.first, v.second.second, v.second.first);
// if(&v == &events[events.size()-1]) continue;
// if((*(&v + 1)).first.first != v.first.first)
// if(np[0] == 0 && np[1] == 0 && segs[(v.first.first+1)%2].size() == 0)
prev = v.first.first;
}
// if(np[0] == 0 && np[1] == 0 && segs[0].size() == 0 && segs[1].size() == 0) result = m+1;
cout<<result;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
8 ms |
2192 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
348 KB |
Output is correct |
| 5 |
Incorrect |
30 ms |
8652 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
37 ms |
7716 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
