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("trapv")
#define st first
#define nd second
#define pb(x) push_back(x)
#define pp(x) pop_back(x)
#define mp(a, b) make_pair(a, b)
#define all(x) (x).begin(), (x).end()
#define rev(x) reverse(all(x))
#define sor(x) sort(all(x))
#define sz(x) (int)(x).size()
#define rsz(x) resize(x)
using namespace std;
///~~~~~~~~~~~~~~~~~~~~~~~~~~
void debug(){cerr<<"\n";}
template <typename H, typename... T>
void debug(H h, T... t) {cerr<<h; if (sizeof...(t)) cerr << ", "; debug(t...);}
#define deb(x...) cerr<<#x<<" = ";debug(x);
///~~~~~~~~~~~~~~~~~~~~~~~~~
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<pii > vii;
typedef vector<ll> vl;
typedef vector<pll> vll;
typedef string str;
#define BOOST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
typedef unsigned int uint;
//mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
const int N=305, INF=1e9+5, mod=1e9+7;
pair<int, int> r[N][N];
uint len[N][N];
int tim[N][N];
uint X[N];
int Y[N];
uint M[N];
pair<int, int> find(pair<int, int> x){
if(r[x.st][x.nd]==x)return x;
return r[x.st][x.nd]=find(r[x.st][x.nd]);
}
void Union(int a, int b){
pii u=find(mp(a, b));
if(a==0){
len[u.st][u.nd]=2*INF;
return;
}
pii v=find(mp(a-1, b));
assert(u!=v);
r[v.st][v.nd]=u;
len[u.st][u.nd]+=len[v.st][v.nd];
}
int main(){
//BOOST;
int n, w, h;
cin>>h>>w>>n;
//assert(n<=250);
vii pts(n);
for(pii &i:pts)cin>>i.st>>i.nd, i.st--, i.nd--;
map<int, int> cx, cy;
for(int i=0; i<pts.size(); i++){
cx[pts[i].st]=1;
cy[pts[i].nd]=1;
}
int wsk=0;
for(auto &i:cx){
X[wsk]=i.st;
i.nd=wsk++;
}
wsk=0;
for(auto &i:cy){
Y[wsk]=i.st;
i.nd=wsk++;
}
uint ans=2*INF;
X[cx.size()]=h;
for(int y=0; y<cy.size(); y++){
for(int i=0; i<cx.size(); i++){
for(int j=0; j<cy.size(); j++){
tim[i][j]=2*INF;
}
//r[i][wsk]=mp(i, wsk);
}
Y[cy.size()]=Y[y]+w;
deb(y);
for(int i=0; i<n; i++){
int xx=cx[pts[i].st];
for(int j=cy[pts[i].nd]; j<cy.size(); j++){
tim[xx][j]=min(tim[xx][j], Y[j+1]-pts[i].nd);
}
}
vector<pair<int, pair<int, int> > > V;
for(int i=0; i<cx.size(); i++){
for(int j=0; j<cy.size(); j++){
V.pb(mp(tim[i][j], mp(i, j)));
}
}
sor(V);
//for(int x=0; x<cx.size(); x++){
//deb(y);
//X[cx.size()]=X[x]+h;
for(int x=0; x<cx.size(); x++){
M[x]=0;
}
for(int i=0; i<cx.size(); i++){
for(int j=0; j<cy.size(); j++){
len[i][j]=X[i+1]-X[i];
if(j>=y){
if(i+1!=cx.size()){
M[i]=max(M[i], len[i][j]);
//for(int x=0; x<=i; x++)M[x]=max(M[x], len[i][j]);
}
else{
//for(int x=0; x<=i; x++)M[x]=max(M[x], len[i][j]+X[x]);
}
}
r[i][j]=mp(i, j);
}
//r[i][wsk]=mp(i, wsk);
}
for(int x=cx.size()-1; x>=0; x--){
M[x]=max(M[x], M[x+1]);
}
for(int j=y; j<cy.size(); j++){
for(int x=0; x<cx.size(); x++){
M[x]=max(M[x], len[cx.size()-1][j]+X[x]);
}
}
vector<int> vx;
for(int i=0; i<cx.size(); i++){
vx.pb(i);
}
for(int i=V.size()-1; i>=0; i--){
if(i+1==V.size() || V[i].st!=V[i+1].st){
uint a=max(Y[y], V[i].st-1);
for(int x:vx){
if(ans>a+max(M[x]-1, X[x]))ans=a+max(M[x]-1, X[x]);
}
}
Union(V[i].nd.st, V[i].nd.nd);
int xx=r[V[i].nd.st][V[i].nd.nd].st;
if(V[i].nd.nd>=y){
uint a=len[r[V[i].nd.st][V[i].nd.nd].st][r[V[i].nd.st][V[i].nd.nd].nd];
if(xx<cx.size()-1){
for(int x:vx){
if(x>xx)break;
if(a>M[x])M[x]=a;
}
}
else{
for(int x:vx){
if(x>xx)break;
M[x]=max(M[x], min(X[x]+a, (uint)2*INF));
}
}
//if(M[0]>=2*INF)break;
if(i%30==0){
for(int x=0; x<vx.size(); x++){
while(x<vx.size() && M[vx[x]]>=2*INF){
swap(vx[x], vx.back());
vx.pp();
}
}
sor(vx);
}
}
//deb(x, y, ans);
//if(M<INF)ans=min(ans, max(X[x], M)+Y[y]);
}
}
cout<<ans;
}
Compilation message (stderr)
cultivation.cpp: In function 'int main()':
cultivation.cpp:69:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
69 | for(int i=0; i<pts.size(); i++){
| ~^~~~~~~~~~~
cultivation.cpp:85:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::map<int, int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
85 | for(int y=0; y<cy.size(); y++){
| ~^~~~~~~~~~
cultivation.cpp:86:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::map<int, int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
86 | for(int i=0; i<cx.size(); i++){
| ~^~~~~~~~~~
cultivation.cpp:87:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::map<int, int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
87 | for(int j=0; j<cy.size(); j++){
| ~^~~~~~~~~~
cultivation.cpp:96:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::map<int, int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
96 | for(int j=cy[pts[i].nd]; j<cy.size(); j++){
| ~^~~~~~~~~~
cultivation.cpp:101:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::map<int, int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
101 | for(int i=0; i<cx.size(); i++){
| ~^~~~~~~~~~
cultivation.cpp:102:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::map<int, int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
102 | for(int j=0; j<cy.size(); j++){
| ~^~~~~~~~~~
cultivation.cpp:110:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::map<int, int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
110 | for(int x=0; x<cx.size(); x++){
| ~^~~~~~~~~~
cultivation.cpp:113:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::map<int, int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
113 | for(int i=0; i<cx.size(); i++){
| ~^~~~~~~~~~
cultivation.cpp:114:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::map<int, int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
114 | for(int j=0; j<cy.size(); j++){
| ~^~~~~~~~~~
cultivation.cpp:117:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::map<int, int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
117 | if(i+1!=cx.size()){
| ~~~^~~~~~~~~~~
cultivation.cpp:132:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::map<int, int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
132 | for(int j=y; j<cy.size(); j++){
| ~^~~~~~~~~~
cultivation.cpp:133:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::map<int, int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
133 | for(int x=0; x<cx.size(); x++){
| ~^~~~~~~~~~
cultivation.cpp:138:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::map<int, int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
138 | for(int i=0; i<cx.size(); i++){
| ~^~~~~~~~~~
cultivation.cpp:142:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
142 | if(i+1==V.size() || V[i].st!=V[i+1].st){
| ~~~^~~~~~~~~~
cultivation.cpp:152:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::map<int, int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
152 | if(xx<cx.size()-1){
| ~~^~~~~~~~~~~~
cultivation.cpp:166:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
166 | for(int x=0; x<vx.size(); x++){
| ~^~~~~~~~~~
cultivation.cpp:167:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
167 | while(x<vx.size() && M[vx[x]]>=2*INF){
| ~^~~~~~~~~~
# | 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... |