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>
// #pragma GCC optimize("Ofast")
#define ll long long
#define lb lower_bound
#define ub upper_bound
#define pii pair<int,int>
#define pll pair<ll,ll>
#define F first
#define S second
#define ld long double
#define pb push_back
#define all(v) v.begin(),v.end()
#define in insert
#define sz(s) (int)s.size()
#define int ll
#define ppb pop_back
#define mem(a,i) memset(a,i,sizeof(a))
using namespace std;
const int MAX=2e5+15;
const ll inf=1e18;
const int mod=1e9+7;
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
int binpow(int a,int n){
if(!n)return 1;
if(n%2==1)return a*binpow(a,n-1)%mod;
int k=binpow(a,n/2);
return k*k%mod;
}
int n,m;
int x[MAX],y[MAX];
vector<pii> vec[MAX];
void solve(){
cin>>n>>m;
set<int> st;
map<int,int> mp;
int cur=0;
for(int i=1;i<=n;i++){
cin>>x[i]>>y[i];
assert(y[i]<=1000);
// y[i]/=2;
// st.in(y[i]);
}
// for(int x:st){
// // while(cur%2!=x%2)cur++;
// mp[x]=cur++;
// }
// for(int i=1;i<=n;i++){
// y[i]=mp[y[i]];
// }
for(int i=1;i<=n;i++){
int nx=x[i%n+1],ny=y[i%n+1];
if(nx==x[i]){
vec[x[i]].pb({min(ny,y[i]),max(ny,y[i])-1});
}
}
int ans=0;
// T.init();
vector<int> use(MAX,0),push(MAX,0);
for(int i=0;i<=m+2;i++){
for(auto [l,r]:vec[i]){
int sum=0;
for(int j=l;j<=r;j++){
sum+=use[j];
use[j]^=1;
}
assert(sum==0||sum==r-l+1);
}
int sum=0;
for(int j=0;j<=1000;j++){
if(push[j]){
if(!use[j]){
cout<<ans<<"\n";
return;
}
else{
push[j]=0;
}
}
else{
if(use[j]){
push[j]=1;
}
}
sum+=push[j];
}
for(int j=0;j<=1000;){
if(push[j]){
if(push[j+1])j+=2;
else{
cout<<ans<<"\n";
return;
}
}
else j++;
}
if(!sum)ans=max(ans,i+1);
}
cout<<ans<<"\n";
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t=1;
// cin>>t;
while(t--)solve();
}
Compilation message (stderr)
Main.cpp: In function 'void solve()':
Main.cpp:45:9: warning: unused variable 'cur' [-Wunused-variable]
45 | int cur=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... |