#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MOD 998244353
const int N = 1e6 + 5;
int n, m;
int a[N];
int b[N];
int c[1010][1010];
void solve(){
cin >> n >> m;
int mx = 0;
for(int i = 1; i <= n; i++){
cin >> a[i] >> b[i];
mx = max(mx, b[i]);
}
if(n <= 5){
int w = 0, h = 0;
vector<int> xs, ys;
for (int i = 1; i <= n; ++i) {
xs.push_back(a[i]);
ys.push_back(b[i]);
}
sort(xs.begin(), xs.end());
sort(ys.begin(), ys.end());
w = ys.back() - ys[0];
h = xs.back() - xs[0];
if (w % 2) {
cout << 0 << '\n';
}
else {
cout << (h % 2 ? xs.back() - 1 : xs.back()) << '\n';
}
exit(0);
}
if(n == 6){
set<int> xs;
map<int, vector<int>> mx;
for (int i = 1; i <= n; ++i) {
xs.insert(a[i]);
mx[a[i]].push_back(b[i]);
sort(mx[a[i]].begin(), mx[a[i]].end());
}
int w1 = 0, w2 = 0, h1 = 0, h2 = 0, wmid = 0;
int x1 = *xs.begin();
xs.erase(xs.begin());
int x2 = *xs.begin();
xs.erase(xs.begin());
int x3 = *xs.begin();
w1 = mx[x1][1] - mx[x1][0];
w2 = mx[x3][1] - mx[x3][0];
h1 = x2 - x1, h2 = x3 - x2;
if (w1 > w2) {
// case 1
if (w1 % 2) {
cout << 0;
}
else if (h1 % 2) {
cout << x2 - 1;
}
else if (w2 % 2 == 1 || (w1 - w2) % 2 == 1) {
cout << x2;
}
else if (h2 % 2) {
cout << x3 - 1;
}
else {
cout << x3;
}
}
else {
if (w1 % 2) {
cout << 0;
}
else if (h1 % 2) {
cout << x2 - 1;
}
else if (w2 % 2 == 1 || (w2 - w1) % 2 == 1) {
cout << x2;
}
else if (h2 % 2) {
cout << x3 - 1;
}
else {
cout << x3;
}
}
exit(0);
}
if(m > 1000 or mx > 1000){
vector<int> v;
for(int i = 2; i <= n; i++){
while(v.size() > 1){
int k = v[v.size() - 2], j = v.back();
if(a[k] == a[j] and a[j] == a[i]){
v.pop_back();
}
else if(b[k] == b[j] and b[j] == b[i]){
v.pop_back();
}
else{
break;
}
}
v.push_back(i);
}
int ans = 0;
for(int i: v){
if(b[i] % 2 or b[i] == 0){
break;
}
ans = a[i] - (a[i] % 2);
if(a[i] % 2){
break;
}
}
cout << ans << '\n';
}
else{
for(int i = 1; i <= n; i++){
int j = i - 1;
if(j == 0){
j = n;
}
if(a[i] == a[j]){
for(int y = min(b[i], b[j]); y + min(b[i], b[j]) < b[i] + b[j]; y++){
c[a[i]][y] ^= 1;
}
}
}
for(int i = 1; i < m; i++){
for(int j = 0; j <= 1000; j++){
c[i][j] ^= c[i-1][j];
}
}
int ans = 0;
for(int i = 0; i < m; i++){
int ok = 0;
for(int j = 0; j <= 1000; j++){
if(c[i][j]){
ok = 1;
if(c[i+1][j] and c[i][j+1] and c[i+1][j+1]){
c[i][j] = 0;
c[i+1][j] = 0;
c[i][j+1] = 0;
c[i+1][j+1] = 0;
}
else{
ok = 2;
break;
}
}
}
if(ok == 2){
break;
}
if(ok == 1){
continue;
}
ans = i + 1;
}
cout << ans;
}
}
int main() {
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int tests = 1;
// cin >> tests;
for(int i = 1; i <= tests; i++){
solve();
}
}
# | 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... |