Submission #55510

#	Time	Username	Problem	Language	Result	Execution time	Memory
55510		ksun48	Cultivation (JOI17_cultivation)	C++14	80 / 100	2072 ms	38772 KiB

cultivation

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

int r, c, n;
vector<pair<int,int> > seeds;
const int INF = 2100100100;
int best = INF;
set<int> tried;

vector<int> xlist;

int up[400][400];
int down[400][400];
int total[400][400];

struct maxqueue {
	vector<int> elements;
	vector<int> indices;
	int s;
	int len;
	maxqueue() : s(0), len(0), elements(0), indices(0) {}
};

void insert(maxqueue* m, int f){
	while(m->elements.size() > 0 && m->elements.size() > m->s && m->elements[m->elements.size()-1] <= f){
		m->elements.pop_back();
		m->indices.pop_back();
	}
	m->elements.push_back(f);
	m->indices.push_back(m->len);
	m->len++;
}
int get(maxqueue* m){
	return m->elements[m->s];
}
void pop(maxqueue *m, int idx){
	if(m->indices[m->s] == idx){
		m->s++;
	}
}

int idx(LL a){
	int s = 0;
	int e = xlist.size();
	while(s + 1 < e){
		int m = (s+e) / 2;
		if(a >= xlist[m]){
			s = m;
		} else {
			e = m;
		}
	}
	return s;
}

void tryxfast(int x){
	if(x < 0){
		return;
	}
	vector<int> pos1;
	vector<int> pos2;
	for(int a : xlist){
		pos1.push_back(a - x);
		pos2.push_back(a + 1);
	}
	vector<int> pos(pos1.size() + pos2.size());
	merge(pos1.begin(), pos1.end(), pos2.begin(), pos2.end(), pos.begin());

	vector<int> ups;
	vector<int> downs;
	vector<int> totals;

	for(int i = 0; i < pos.size(); i++){
		int a = idx((LL)pos[i]+x);
		int b = idx((LL)pos[i]-1);
		// a >= b
		ups.push_back(up[a][b]);
		downs.push_back(down[a][b]);
		totals.push_back(total[a][b]);
	}


	// two pointers: 
	int j = 0;
	maxqueue* upset    = new maxqueue();
	maxqueue* downset  = new maxqueue();
	maxqueue* totalset = new maxqueue();
	for(int i = 0; i < pos.size(); i++){
		while(j < pos.size() && pos[j] <= pos[i] + r - 1){
			insert(upset, ups[j]);
			insert(downset, downs[j]);
			insert(totalset, totals[j]);
			j++;
		}
		int total = get(totalset);
		if(total < c+1){
			LL need = max((LL)get(upset) + (LL)get(downset), (LL)total - 1);
			best = (int)min((LL)best, need + x);
		}
		pop(upset, i);
		pop(downset, i);
		pop(totalset, i);
	}
}

int main(){
	cin.sync_with_stdio(0); cin.tie(0);
	cin >> r >> c >> n;
	for(int i = 0; i < n; i++){
		int s, e;
		cin >> s >> e;
		s--; e--;
		seeds.push_back({e,s});
	}
	sort(seeds.begin(), seeds.end());
	set<int> xset;
	for(int i = 0; i < n; i++){
		swap(seeds[i].first, seeds[i].second);
		xset.insert(seeds[i].first);
	}
	xlist.push_back(-1);
	for(int x : xset){
		xlist.push_back(x);
	}

	// replace this part with O(n^2 log n) 

	/*for(int i = 0; i < xlist.size(); i++){
		for(int j = 0; j <= i; j++){
			vector<int> stuff;
			int tot = 0;
			for(int k = 0; k < seeds.size(); k++){
				int p = seeds[k].first;
				if(p <= xlist[i] && p > xlist[j]){
					stuff.push_back(seeds[k].second);
				}
			}
			for(int i = 0; i + 1 < stuff.size(); i++){
				tot = max(tot, stuff[i+1] - stuff[i]);
			}
			if(stuff.size() == 0){
				total[i][j] = up[i][j] = down[i][j] = c+1;
			} else {
				up[i][j] = stuff[0] - 0;
				down[i][j] = c-1 - stuff[stuff.size()-1];
				total[i][j] = tot;
			}
		}
	}*/
	for(int i = 0; i < xlist.size(); i++){
		vector<int> ins[xlist.size() + 1];
		vector<int> del[xlist.size() + 1];

		for(int k = 0; k < seeds.size(); k++){
			int p = seeds[k].first;
			if(p <= xlist[i]){
				ins[0].push_back(seeds[k].second);
				int jdel = lower_bound(xlist.begin(), xlist.end(), p) - xlist.begin();
				del[jdel].push_back(seeds[k].second);
			}
		}

		multiset<int> grass;
		grass.insert(-1);
		grass.insert(c);
		multiset<int> diffs;
		diffs.insert(-(c+1));
		for(int j = 0; j <= i; j++){
			for(int a : del[j]){
				int a1 = *(--grass.find(a));
				int a2 = *(++grass.find(a));
				diffs.erase(diffs.find(a1-a));
				diffs.erase(diffs.find(a-a2));
				diffs.insert(a1-a2);
				grass.erase(grass.find(a));
			}
			for(int a : ins[j]){
				grass.insert(a);
				int a1 = *(--grass.find(a));
				int a2 = *(++grass.find(a));
				diffs.erase(diffs.find(a1-a2));
				diffs.insert(a1-a);
				diffs.insert(a-a2);
			}
			total[i][j] = -*diffs.begin();
			up[i][j] = *(++grass.begin()) - 0;
			down[i][j] = c-1 - *(--(--grass.end()));
		}
	}

	set<int> trying;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			trying.insert(seeds[i].first + r-1 - seeds[j].first);
			trying.insert(seeds[i].first -   1 - seeds[j].first);
		}
	}
	for(int r : trying){
		tryxfast(r);
	}
	cout << best << '\n';
}

Compilation message (stderr)

cultivation.cpp: In constructor 'maxqueue::maxqueue()':
cultivation.cpp:21:6: warning: 'maxqueue::len' will be initialized after [-Wreorder]
  int len;
      ^~~
cultivation.cpp:18:14: warning:   'std::vector<int> maxqueue::elements' [-Wreorder]
  vector<int> elements;
              ^~~~~~~~
cultivation.cpp:22:2: warning:   when initialized here [-Wreorder]
  maxqueue() : s(0), len(0), elements(0), indices(0) {}
  ^~~~~~~~
cultivation.cpp: In function 'void insert(maxqueue*, int)':
cultivation.cpp:26:53: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(m->elements.size() > 0 && m->elements.size() > m->s && m->elements[m->elements.size()-1] <= f){
                                  ~~~~~~~~~~~~~~~~~~~^~~~~~
cultivation.cpp: In function 'void tryxfast(int)':
cultivation.cpp:74:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < pos.size(); i++){
                 ~~^~~~~~~~~~~~
cultivation.cpp:89:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < pos.size(); i++){
                 ~~^~~~~~~~~~~~
cultivation.cpp:90:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(j < pos.size() && pos[j] <= pos[i] + r - 1){
         ~~^~~~~~~~~~~~
cultivation.cpp: In function 'int main()':
cultivation.cpp:151:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < xlist.size(); i++){
                 ~~^~~~~~~~~~~~~~
cultivation.cpp:155:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int k = 0; k < seeds.size(); k++){
                  ~~^~~~~~~~~~~~~~

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