Submission #55300

#	Time	Username	Problem	Language	Result	Execution time	Memory
55300		ksun48	Cultivation (JOI17_cultivation)	C++14	60 / 100	2043 ms	1188 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;

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

void insert(maxqueue* m, int f){
	cout << "insert " << m << " " << f << endl;
	while(m->elements.size() > 0 && 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){
	cout << "get " << m << " " << m->elements[m->s] << endl;
	return m->elements[m->s];
}
void pop(maxqueue *m){
	cout << "pop " << m << " " << m->elements[m->s] << endl;
	if(m->indices[m->s] == m->curidx){
		m->s++;
	}
	m->curidx++;
}

void tryxfast(int x){
	if(x < 0 || tried.find(x) != tried.end()){
		return;
	}
	tried.insert(x);
	set<int> times;
	for(pair<int,int> z : seeds){
		times.insert(z.first - x);
		times.insert(z.first + 1);
	}
	vector<int> pos;
	map<int,int> idx;
	for(int t : times){
		idx[t] = pos.size();
		pos.push_back(t);
	}
	vector<int> ins[pos.size()];
	vector<int> del[pos.size()];
	for(pair<int,int> z : seeds){
		ins[idx[z.first - x]].push_back(z.second); // ins
		del[idx[z.first + 1]].push_back(z.second); // del
	}

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

	multiset<int> grass;
	grass.insert(-1);
	grass.insert(c);
	multiset<int> diffs;
	diffs.insert(-(c+1));
	for(int i = 0; i < pos.size(); i++){
		for(int a : ins[i]){
			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);
		}
		for(int a : del[i]){
			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));
		}
		totals.push_back( -*diffs.begin() );
		ups.push_back( *(++grass.begin()) - 0 );
		downs.push_back( c-1 - *(--(--grass.end())) );
	}
	/*// 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);
		pop(downset);
		pop(totalset);
	}
	delete upset;
	delete downset;
	delete totalset;*/
	// two pointers: 
	int j = 0;
	multiset<int> upset;
	multiset<int> downset;
	multiset<int> totalset;
	for(int i = 0; i < pos.size(); i++){
		while(j < pos.size() && pos[j] <= pos[i] + r - 1){
			upset.insert(-ups[j]);
			downset.insert(-downs[j]);
			totalset.insert(-totals[j]);
			j++;
		}
		int total = -*totalset.begin();
		if(total < c+1){
			LL need = max((LL)-*upset.begin() + (LL)-*downset.begin(), (LL)total - 1);
			best = (int)min((LL)best, need + x);
		}
		upset.erase(upset.find(-ups[i]));
		downset.erase(downset.find(-downs[i]));
		totalset.erase(totalset.find(-totals[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({s,e});
	}
	sort(seeds.begin(), seeds.end());
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			tryxfast(seeds[i].first + r-1 - seeds[j].first);
			tryxfast(seeds[i].first -   1 - seeds[j].first);
		}
	}
	cout << best << '\n';
}

Compilation message (stderr)

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:124:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < pos.size(); i++){
                 ~~^~~~~~~~~~~~
cultivation.cpp:125:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(j < pos.size() && pos[j] <= pos[i] + r - 1){
         ~~^~~~~~~~~~~~

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