Submission #902623

#TimeUsernameProblemLanguageResultExecution timeMemory
902623Maite_MoraleThe Kingdom of JOIOI (JOI17_joioi)C++14
60 / 100
2542 ms262144 KiB
#include<bits/stdc++.h> #define F first #define S second #define MAX 3000 #define oo 1e18 #define mod 1000000007 #define fast_in ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);cout.setf(ios::fixed);cout.precision(0); using namespace std; typedef long long ll; #define pll pair<ll , ll> #define vll vector<ll> #define vvll vector<vll> #define vpll vector<pll> ll tmn[3][MAX][MAX],tmx[3][MAX][MAX],a[MAX][MAX],m,n; vll v;map<ll,ll> mp; ll OK(ll x,ll z){ ll cl=-1,mx=0,mn=oo; for(int i=0;i<n;i++){ while(cl+1<m && tmn[0][i][cl+1]<x)cl++; if(cl!=-1)mx=max(mx,tmx[1][i][cl]); } mn=min(mn,mx);cl=m;mx=0; for(int i=0;i<n;i++){ while(cl-1>=0 && tmn[1][i][cl-1]<x)cl--; mx=max(mx,tmx[0][i][cl]); } mn=min(mn,mx);cl=-1;mx=0; for(int i=n-1;i>=0;i--){ while(cl+1<m && tmn[0][i][cl+1]<x)cl++; if(cl!=-1)mx=max(mx,tmx[1][i][cl]); } mn=min(mn,mx);cl=m;mx=0; for(int i=n-1;i>=0;i--){ while(cl-1>=0 && tmn[1][i][cl-1]<x)cl--; mx=max(mx,tmx[0][i][cl]); } mn=min(mn,mx); if(z==1)return max(abs(v[0]-mn),abs(v.back()-x)); if(abs(v[0]-mn)<=abs(v.back()-x))return 1; return 0; } int main(){ fast_in cin>>n>>m; for(int i=0;i<n;i++){ tmn[0][i][m]=tmn[1][i][0]=oo; tmx[0][i][m]=tmx[1][i][0]=0; for(int j=0;j<m;j++){ cin>>a[i][j]; if(mp[a[i][j]]==0){ mp[a[i][j]]=1; v.push_back(a[i][j]); } tmx[1][i][j]=max(tmx[1][i][j],a[i][j]); tmx[1][i][j+1]=tmx[1][i][j]; tmn[1][i][j]=min(tmn[1][i][j],a[i][j]); tmn[1][i][j+1]=tmn[1][i][j]; } for(int j=m-1;j>=0;j--){ tmx[0][i][j]=max(tmx[0][i][j+1],a[i][j]); tmn[0][i][j]=min(tmn[0][i][j+1],a[i][j]); } } sort(v.begin(),v.end()); if(v.size()==1){cout<<0;return 0;} ll p=1,f=v.size(); while(abs(f-p)!=1){ ll md=(p+f)/2; if(md<0 || md>=v.size())while(true){md=md;} if(OK(v[md],0)==1)p=md; else f=md; } if(f==v.size()){cout<<OK(v[p],1);return 0;} cout<<min(OK(v[p],1),OK(v[f],1)); return 0; }

Compilation message (stderr)

joioi.cpp: In function 'int main()':
joioi.cpp:71:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |         if(md<0 || md>=v.size())while(true){md=md;}
      |                    ~~^~~~~~~~~~
joioi.cpp:75:9: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |     if(f==v.size()){cout<<OK(v[p],1);return 0;}
      |        ~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...