Submission #881468

#	Time	Username	Problem	Language	Result	Execution time	Memory
881468		eitanelb	Cultivation (JOI17_cultivation)	C++14	80 / 100	1712 ms	262144 KiB

cultivation

#include<vector>
#include<iostream>
#include<set>
#include<fstream>
#include<algorithm>
using namespace std;
#define pi pair<int,int>
#define x first
#define y second
/*
for down - just real distances from down (optional also for left) -> O(n)
for up - just real distances, or such that together it's distance between two -> O(n)+O(n^2)
after I have up and down - O(n^2) //optional - O(nlogu), with segmentree sparse/coordination, then O(n^4 logU)
 
then O(n^5), or if r<=40 -> O(40*40*40*n)
which is 60 points
 
for 100 points, let's see that whenever you get the up bigger, it affects only one place
that can being it to O(n^3), which is 100 points
*/
 
 
int deb = 0;
pair<int, pi>* merge(pair<int, pi>* v1, pair<int, pi>* v2, int n1, int n2) {
	pair<int, pi>* v3 = new pair<int,pi>[n1+n2];
	int p1 = 0, p2 = 0, p3=0;
	while (p1 < n1 || p2 < n2) {
		if (p1 != n1 && (p2 == n2 || v1[p1].x <= v2[p2].x)) v3[p3++] = v1[p1++];
		else v3[p3++] = v2[p2++];
	}
	return v3;
}
int Time_To_Fool_The_Lab(int r, int c, int n, vector<int> X, vector<int> Y) {
	int* vdown = new int[n];
	pair<int, pi>* vup = new pair<int, pi>[n];
	//int sz = n * (n - 1) / 2;
	int sz = 0;
	for (int i = 0; i < n; i++)for (int j = 0; j < n; j++)if (X[i] > X[j])sz++;
	pair<int, pi>* vsum = new pair<int, pi>[sz];
	int t = 0;
	for (int i = 0; i < n; i++) {
		vdown[i] = X[i] - 1;
	}
	for (int i = 0; i < n; i++) {
		vup[i] = {r - X[i], {i, -1}};
		for (int j = 0; j < n; j++) if (X[i] > X[j]) vsum[t++]={X[i] - X[j] - 1, {i, j}};
	}
	sort(vdown, vdown + n);
	int h = unique(vdown, vdown + n)-vdown;
	sort(vup, vup+n);
	sort(vsum, vsum + sz);
	
	int res = 2e9;
	for (int d = 0; d < h; d++) {
		int down = vdown[d];
		pair<int, pi>* vnup = new pair<int, pi>[sz];
		for (int i = 0; i < sz;i++) vnup[i] = {vsum[i].x - down,vsum[i].y};
		vnup = merge(vnup, vup,sz,n);
 
		bool* on = new bool[n];
		int *dr=new int[n], * dl = new int[n], * maxi = new int[n], * disl = new int[n], * disr = new int[n];
		for (int i = 0; i < n; i++) {
			on[i] = 0;
			if (X[i] == r) {
				dr[i] = dl[i] = 0;
				on[i] = 1;
				disl[i] = disr[i] = 0;
				continue;
			}
			dr[i] = c - Y[i];
			dl[i] = Y[i] - 1;
			disl[i] = disr[i] = c;
			for (int j = 0; j < n; j++) {
				if (j == i) continue;
				if (X[j] > X[i] && X[j] - down <= X[i] + 1) {
					if (Y[j] > Y[i]) dr[i] = min(dr[i], Y[j] - Y[i] - 1);
					else if (Y[j] < Y[i]) dl[i] = min(dl[i], Y[i] - Y[j] - 1);
					else on[i] = 1;
 
					disr[i] = min(disr[i], c - Y[j]);
					disl[i] = min(disl[i], Y[j]-1);
				}
			}
		}
		if (deb) {cout << "disl: "; for (int i = 0; i < n; i++) cout << disl[i] << ' '; cout << endl;}
		if (deb) { cout << "disr: "; for (int i = 0; i < n; i++) cout << disr[i] << ' '; cout << endl; }
		multiset<int> maxs, sdl, sdr;
		for (int i = 0; i < n; i++) {
			if (on[i]) maxi[i] = max(dr[i], dl[i]);
			else maxi[i] = dr[i] + dl[i] + 1;
			maxs.insert(maxi[i]);
			sdl.insert(disl[i]);
			sdr.insert(disr[i]);
		}
		if (deb) {for (int i = 0; i < n; i++) {cout << dl[i] << ' ' << dr[i] << ' ' << maxi[i] << ' ' << on[i] << endl;}}
 
		// row 1 ************
		int mx1 = 0;
		set<int> st;
		for (int i = 0; i < n; i++)
			if (X[i] - down <= 1)
				st.insert(Y[i]);
		sdl.insert(*st.begin() - 1);
		sdr.insert(c - *prev(st.end()));
		int fr = 0;
		for (int i : st) {
			mx1 = max(mx1, i - fr - 1);
			fr = i;
		}
		maxs.insert(mx1);
 
		int up = 0;
 
		for (int q = 0; q < (n + sz);q++) {
			if (deb) { cout << "disl: "; for (int i = 0; i < n; i++) cout << disl[i] << ' '; cout << endl; }
			if (deb) { cout << "disr: "; for (int i = 0; i < n; i++) cout << disr[i] << ' '; cout << endl; }
			pair<int, pi> pr = vnup[q];
			if (deb) { cout << pr.x << ' ' << pr.y.x << ' ' << pr.y.y << endl; }
			up = pr.x;
			if (up < 0) continue;
			if (pr.y.y == -1) {
				int u = pr.y.x;
				maxs.erase(maxs.find(maxi[u]));
				sdl.erase(sdl.find(disl[u]));
				sdr.erase(sdr.find(disr[u]));
				maxi[u] = dr[u] = dl[u] = disr[u] = disl[u] = 0;
				maxs.insert(0); sdl.insert(0); sdr.insert(0);
			}
			else {
				int i = pr.y.x, j = pr.y.y;
				if (Y[i]== Y[j]) on[j] = 1;
				else if (Y[i] > Y[j]) {
					if (dr[j] > Y[i] - Y[j] - 1) {
						dr[j] = Y[i] - Y[j] - 1;
					}
				}
				else {
					if (dl[j] > Y[j] - Y[i] - 1) {
						dl[j] = Y[j] - Y[i] - 1;
					}
				}
 
				sdl.erase(sdl.find(disl[j]));
				sdr.erase(sdr.find(disr[j]));
				disr[j] = min(disr[j], c - Y[i]);
				disl[j] = min(disl[j], Y[i] - 1);
				sdl.insert(disl[j]);
				sdr.insert(disr[j]);
 
				maxs.erase(maxs.find(maxi[j]));
				if (on[j]) maxi[j] = max(dr[j], dl[j]);
				else maxi[j] = dr[j] + dl[j] + 1;
				maxs.insert(maxi[j]);
			}
			int mxla=*prev(sdl.end()), mxfa = *prev(sdr.end());
			int mx = *prev(maxs.end());
			if (mxla >= c || mxfa >= c) continue;
			mx = max(mx, mxla + mxfa);
			if (mx > 2e9 - up - down) continue;
			if (deb) {
				cout << mx << ' ' << mxla << ' ' << mxfa << ' ' << up << ' ' << down << endl;
			}
			res = min(res, mx + down + up);
		}
	}
	return res;
}
 
 
 
 
int run = 1;
int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	if (run == 1) {
		int R, C, N;
		cin >> R >> C >> N;
		vector<int> X(N), Y(N);
		for (int i = 0; i < N; i++) {
			cin >> X[i] >> Y[i];
		}
 
		int res = Time_To_Fool_The_Lab(R, C, N, X, Y);
 
		cout << res << endl;
	}
	if (run == 2) {
		vector<int> sizes = {0, 16, 16, 12, 20, 16, 3 };
		string name = "01-01";
		for(int j=2;j<3;j++){
			cout << "****" << j << "****\n";
			name[1] = '0' + j;
			for (int i = 11; i <= sizes[j]; i++) {
				cout << "**" << j << ' ' << i << "**\n";
				name[3] = '0' + i / 10; name[4] = '0' + i % 10;
				ifstream fin(name + ".in"), fout(name + ".out");
				int R, C, N;
				fin >> R >> C >> N;
				vector<int> X(N), Y(N);
				for (int i = 0; i < N; i++) {
					fin >> X[i] >> Y[i];
				}
 
				int nres, res = Time_To_Fool_The_Lab(R, C, N, X, Y);
 
				fout >> nres;
				if (nres != res) {
					cout << "subtask " << j << "test" << i << endl;
					cout << R << ' ' << C << endl << N << endl;
					for (int i = 0; i < N; i++) {
						cout << X[i] << ' ' << Y[i] << endl;
					}
					cout << res << ' ' << nres << endl;
					break;
				}
			}
		}
	}
}

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