Submission #519109

#	Time	Username	Problem	Language	Result	Execution time	Memory
519109		Antekb	Cultivation (JOI17_cultivation)	C++14	80 / 100	2063 ms	3192 KiB

cultivation

#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){
      |             ~^~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 15 / 15
• Subtask 4: 30 / 30
• Subtask 5: 20 / 20
• Subtask 6: 0 / 20