Submission #47320

#	Time	Username	Problem	Language	Result	Execution time	Memory
47320		Kmcode	Cultivation (JOI17_cultivation)	C++14	65 / 100	2053 ms	5152 KiB

cultivation

#include "bits/stdc++.h"
using namespace std;


#define MAX 2002

int n;
int r;
int c;

vector<pair<long long int, long long int> > v;


vector<long long int> vv;

struct st {
	map<long long int, int> mp;
	priority_queue<pair<long long int, long long int> > q;
	long long int las_up;
	long long int las_dw;
	long long int las_md;
	bool changu;
	bool changd;
	bool changm;
	st() {
		changu = changd=changm=true;
		
	}
	void ins(long long int val) {
		mp[val]++;
		changu = changd = changm = true;
		auto it = mp.lower_bound(val);
		if (next(it) != mp.end()) {
			q.push(make_pair((*next(it)).first - (*it).first, (*it).first));
		}
		if (it != mp.begin()) {
			q.push(make_pair(-(*prev(it)).first + (*it).first, (*prev(it)).first));
		}
	}
	void er(long long int val) {
		mp[val]--;
		changu = changd = changm = true;
		if (mp[val] == 0) {
			mp.erase(val);
			auto it = mp.lower_bound(val);
			if (it != mp.begin() && it != mp.end()) {
				q.push(make_pair(-(*prev(it)).first + (*it).first, (*prev(it)).first));
			}
		}
	}
	long long int up() {
		if (changu == false) {
			return las_up;
		}
		changu = false;
		if (mp.size() == 0) {
			las_up = LLONG_MAX / 100LL;
			return LLONG_MAX / 100LL;
		}
		las_up = (*mp.begin()).first;
		return las_up;
	}
	long long int dw() {
		if (changd == false) {
			return las_dw;
		}
		changd = false;
		if (mp.size() == 0) {
			las_dw = LLONG_MAX / 100LL;
			return LLONG_MAX / 100LL;
		}
		las_dw= r - (*mp.rbegin()).first - 1LL;
		return las_dw;
	}
	long long int mid() {
		if (changm == false) {
			return las_md;
		}
		changm = false;
		while (!q.empty()) {
			long long int n1 = q.top().second;
			long long int n2 = q.top().first + n1;
			if (mp.count(n1) == 0 || mp.count(n2) == 0) {
				q.pop();
				continue;
			}
			auto it = mp.upper_bound(n1);
			if ((*it).first != n2) {
				q.pop();
				continue;
			}
			las_md=n2 - n1 - 1LL;
			return las_md;
		}
		las_md = 0;
		return las_md;
	}
};

st z[2002];
vector<long long int> sear;

struct monotonic_queue {
	pair<long long int, int> v[2002];
	int fr;
	int bc;
	monotonic_queue() {
		fr = 0;
		bc = -1;
	}
	void monotonic_queue1() {
		fr = 0;
		bc = -1;
	}
	void add(pair<long long int, int> p) {
		while (bc>=fr&&v[bc].first <= p.first) {
			bc--;
		}
		v[bc + 1] = p;
		bc++;
	}
	long long int gt(long long int ic) {
		while (sear[v[fr].second] >= ic + c) {
			fr++;
		}
		return v[fr].first;
	}
};
vector<long long int> mg(vector<long long int> &a, vector<long long int> &b) {
	vector<long long int> r;
	int aa = 0;
	int bb = 0;
	while (aa < a.size() || bb < b.size()) {
		if (bb<b.size() && r.size() && r.back() == b[bb]) {
			bb++;
			continue;
		}
		if (aa<a.size() && r.size() && r.back() == a[aa]) {
			aa++;
			continue;
		}
		if (bb<b.size() && (aa == a.size() || a[aa]>b[bb])) {
			r.push_back(b[bb]);
			bb++;
			continue;
		}
		r.push_back(a[aa]);
		aa++;
		continue;
	}
	return r;
}
bool cmp(pair<long long int, long long int> a, pair<long long int, long long int> b) {
	return a.second < b.second;
}


vector<int> las;

long long int u1[MAX];
long long int d1[MAX];
long long int md1[MAX];

monotonic_queue u2;
monotonic_queue d2;
monotonic_queue md2;
int main() {
	scanf("%d%d", &r, &c);
	cin >> n;
	long long int mint = LLONG_MAX;
	long long int maxt = 0;
	for (int i = 0; i < n; i++) {
		int a, b;
		scanf("%d%d", &a, &b);
		a--;
		b--;
		v.push_back(make_pair(a, b));
		mint = min(mint, (long long int)b);
		maxt = max(maxt, (long long int)b);
	}
	for (int i = 0; i < v.size(); i++) {
		sear.push_back(v[i].second + c);
		sear.push_back(v[i].second);
		sear.push_back(v[i].second - c);
	}
	sort(sear.begin(), sear.end());
	sear.erase(unique(sear.begin(), sear.end()), sear.end());
	maxt = c - maxt - 1LL;
	long long int lef_least = mint;
	long long int rig_least = maxt;
	maxt += mint;
	vv.push_back(0);
	v.push_back(make_pair(0, c - 1));
	v.push_back(make_pair(0, 0));
	for (int i = 0; i < v.size(); i++) {
		for (int j = 0; j < v.size(); j++) {
			vv.push_back(v[i].second + c - v[j].second - 1);
			vv.push_back(max(0LL, abs(v[j].second - v[i].second) - 1));
		}
	}
	v.pop_back();
	v.pop_back();
	vv.push_back(maxt);
	sort(vv.begin(), vv.end());
	vv.erase(unique(vv.begin(), vv.end()), vv.end());
	long long int ans = LLONG_MAX;
	sort(v.begin(), v.end(), cmp);
	for (int j = 0; j < v.size(); j++) {
		int id1 = lower_bound(sear.begin(), sear.end(), v[j].second) - sear.begin();
		id1--;
		las.push_back(id1);
	}
	for (int i = 0; i < vv.size(); i++) {
		if (vv[i] < maxt)continue;
		for (int j = 0; j < v.size(); j++) {
			for (int k = las[j] + 1;k+1<sear.size()&&sear[k+1]<=v[j].second+vv[i]+1LL; k++) {
				las[j] = k;
				z[k].ins(v[j].first);
			}
		}
		for (int j = 0; j < sear.size(); j++) {
			u1[j] = z[j].up();
			d1[j]= z[j].dw();
			md1[j] = z[j].mid();
		}
		u2.monotonic_queue1();
		d2.monotonic_queue1();
		md2.monotonic_queue1();
		int idx = sear.size() - 1;
		for (int j = sear.size() - 1; j >= 0; j--) {
			u2.add(make_pair(u1[j], j));
			d2.add(make_pair(d1[j], j));
			md2.add(make_pair(md1[j], j));
			while (sear[idx] > sear[j] + c) {
				idx--;
			}
			if (sear[idx]==sear[j]+c) {
				long long int need = u2.gt(sear[j]) + d2.gt(sear[j]) + max(0LL, md2.gt(sear[j]) - u2.gt(sear[j]) - d2.gt(sear[j]));
				ans = min(ans, need + vv[i]);
			}
		}
	}
	printf("%lld\n", ans);
	return 0;
}

Compilation message (stderr)

cultivation.cpp: In function 'std::vector<long long int> mg(std::vector<long long int>&, std::vector<long long int>&)':
cultivation.cpp:133:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while (aa < a.size() || bb < b.size()) {
         ~~~^~~~~~~~~~
cultivation.cpp:133:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while (aa < a.size() || bb < b.size()) {
                          ~~~^~~~~~~~~~
cultivation.cpp:134:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (bb<b.size() && r.size() && r.back() == b[bb]) {
       ~~^~~~~~~~~
cultivation.cpp:138:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (aa<a.size() && r.size() && r.back() == a[aa]) {
       ~~^~~~~~~~~
cultivation.cpp:142:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (bb<b.size() && (aa == a.size() || a[aa]>b[bb])) {
       ~~^~~~~~~~~
cultivation.cpp:142:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (bb<b.size() && (aa == a.size() || a[aa]>b[bb])) {
                       ~~~^~~~~~~~~~~
cultivation.cpp: In function 'int main()':
cultivation.cpp:181:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < v.size(); i++) {
                  ~~^~~~~~~~~~
cultivation.cpp:195:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < v.size(); i++) {
                  ~~^~~~~~~~~~
cultivation.cpp:196:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < v.size(); j++) {
                   ~~^~~~~~~~~~
cultivation.cpp:208:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int j = 0; j < v.size(); j++) {
                  ~~^~~~~~~~~~
cultivation.cpp:213:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < vv.size(); i++) {
                  ~~^~~~~~~~~~~
cultivation.cpp:215:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < v.size(); j++) {
                   ~~^~~~~~~~~~
cultivation.cpp:216:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int k = las[j] + 1;k+1<sear.size()&&sear[k+1]<=v[j].second+vv[i]+1LL; k++) {
                            ~~~^~~~~~~~~~~~
cultivation.cpp:221:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < sear.size(); j++) {
                   ~~^~~~~~~~~~~~~
cultivation.cpp:189:16: warning: unused variable 'lef_least' [-Wunused-variable]
  long long int lef_least = mint;
                ^~~~~~~~~
cultivation.cpp:190:16: warning: unused variable 'rig_least' [-Wunused-variable]
  long long int rig_least = maxt;
                ^~~~~~~~~
cultivation.cpp:168:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &r, &c);
  ~~~~~^~~~~~~~~~~~~~~~
cultivation.cpp:174:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &a, &b);
   ~~~~~^~~~~~~~~~~~~~~~

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