Submission #110313

#	Time	Username	Problem	Language	Result	Execution time	Memory
110313		tincamatei	Cultivation (JOI17_cultivation)	C++14	0 / 100	3 ms	384 KiB

cultivation

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 300;

struct Cell {
	int l, c;
} v[MAX_N];

bool cmp(Cell a, Cell b) {
	return a.c < b.c;
}

struct Event {
	bool toerase;
	int l, c;

	inline bool operator< (const Event &x) const {
		return c < x.c || (c == x.c && toerase < x.toerase);
	}
};

multiset<int> vert;

static inline int getAbove(int x, int r) {
	multiset<int>::iterator it = vert.upper_bound(x);
	if(it == vert.end())
		return r + 1;
	else
		return *it;
}

static inline int getBelow(int x) {
	multiset<int>::iterator it = vert.lower_bound(x);
	if(it == vert.begin())
		return 0;
	else {
		it--;
		return *it;
	}
}

long long getsol(int n, int r, int c) {
	long long rez = 1LL << 35;
	
	int necleft, necright;
	necleft = necright = 1<<30;

	for(int i = 0; i < n; ++i) {
		necleft = min(necleft, v[i].c - 1);
		necright = min(necright, c - v[i].c);
	}

	for(int i = 0; i < n; ++i)
		for(int j = i + 1; j < n; ++j) {
			int expleft, expright;
			long long auxrez;

			expleft = necleft;
			expright = max(necright, necleft + (v[j].c - v[i].c - 1 - necleft - necright));
			auxrez = expleft + expright;
			vector<Event> toadd, toerase;
			vector<Event> events(2 * n);
			
			for(int k = 0; k < n; ++k) {
				toadd.push_back({0, v[k].l, max(1, v[k].c - expleft)});
				toerase.push_back({1, v[k].l, min(c, v[k].c + expright)});
			}
			merge(toadd.begin(), toadd.end(), toerase.begin(), toerase.end(), events.begin());
			
			int p1, p2;
			int expup, expdown, middle;

			expup = expdown = middle = 0;
			p1 = 0;
			
			for(int k = 0; k < n - 1; ++k)
				if(v[k + 1].c - v[k].c - 1 > expleft + expright)
					expup = expdown = middle = 1 << 30;
			vert.clear();

			while(p1 < events.size()) {
				p2 = p1;
				while(p2 < events.size() && events[p1].c == events[p2].c && !events[p2].toerase) {
					vert.insert(events[p2].l);
					++p2;
				}

				p2 = p1;
				while(p2 < events.size() && events[p1].c == events[p2].c) {
					int down, up;
					up = getBelow(events[p2].l);
					down = getAbove(events[p2].l, r);

					if(up == 0)
						expdown = max(expdown, events[p2].l - 1);
					else
						middle = max(middle, events[p2].l - up - 1);
					if(down == r + 1)
						expup = max(expup, r - events[p2].l);
					else
						middle = max(middle, up - events[p2].l - 1);
					++p2;
				}

				p2 = p1;
				while(p2 < events.size() && events[p1].c == events[p2].c) {
					if(events[p2].toerase)
						vert.erase(vert.find(events[p2].l));
					++p2;
				}
			
				p1 = p2;
			}
			
			rez = min(auxrez + max(middle, expup + expdown), rez);
		}
	
	return rez;
}

int main() {
#ifdef HOME
	FILE *fin = fopen("input.in", "r");
	FILE *fout = fopen("output.out", "w");
#else
	FILE *fin = stdin;
	FILE *fout = stdout;
#endif

	int n, r, c;
	fscanf(fin, "%d%d", &r, &c);
	fscanf(fin, "%d", &n);

	for(int i = 0; i < n; ++i)
		fscanf(fin, "%d%d", &v[i].l, &v[i].c);

	sort(v, v + n, cmp);

	fprintf(fout, "%lld", getsol(n, r, c));

	fclose(fin);
	fclose(fout);
	return 0;
}

Compilation message (stderr)

cultivation.cpp: In function 'long long int getsol(int, int, int)':
cultivation.cpp:83:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while(p1 < events.size()) {
          ~~~^~~~~~~~~~~~~~~
cultivation.cpp:85:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(p2 < events.size() && events[p1].c == events[p2].c && !events[p2].toerase) {
           ~~~^~~~~~~~~~~~~~~
cultivation.cpp:91:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(p2 < events.size() && events[p1].c == events[p2].c) {
           ~~~^~~~~~~~~~~~~~~
cultivation.cpp:108:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(p2 < events.size() && events[p1].c == events[p2].c) {
           ~~~^~~~~~~~~~~~~~~
cultivation.cpp: In function 'int main()':
cultivation.cpp:133:8: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  fscanf(fin, "%d%d", &r, &c);
  ~~~~~~^~~~~~~~~~~~~~~~~~~~~
cultivation.cpp:134:8: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  fscanf(fin, "%d", &n);
  ~~~~~~^~~~~~~~~~~~~~~
cultivation.cpp:137:9: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   fscanf(fin, "%d%d", &v[i].l, &v[i].c);
   ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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