Submission #414376

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
414376	2021-05-30T11:41:09 Z	amoo_safar	Cultivation (JOI17_cultivation)	C++17	15 / 100	2000 ms	33768 KB

cultivation

// vaziat meshki-ghermeze !
#include <bits/stdc++.h>

#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'

using namespace std;

typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<int, int> pii;

const ll Mod = 1000000007LL;
const int N = 3e2 + 10;
const int Inf = 2'000'000'001;
const ll Log = 30;

int n, R, C;
pii A[N];

// 0, x, y -> C + R < x -> y
// 1, x, y -> C < x -> y
// 2, x, y -> R < x -> y
typedef pii con;
typedef pair<con, int> Query;
vector<Query> Q, TQ, V0, V1;
typedef pair<con, con> iff;
vector< pair<iff, int> > cons;

bool Better(con A, con B){
	if(A.F != B.F)
		return false;
	return A.S >= B.S;
}
bool Better(iff A, iff B){
	return Better(A.F, B.F) && Better(A.S, B.S);
}
bool Sat(con A, int i, int j){
	if(A.F == 0)
		return i + j < A.S;
	if(A.F == 1)
		return i < A.S;
	return j < A.S;
}
void Check(int l, int r){
	int ln = r - l - 1;
	vector<int> V;
	for(int k = 1; k <= n; k++){
		if(l < A[k].F && A[k].F < r)
			V.pb(A[k].S);
	}
	sort(all(V));

	int sz = Q.size();
	vector< pair<con, int> > tmp;
	if(!V.empty() && V[0] > 1)
		tmp.pb({{1, V[0] - 1}, ln});
	if(!V.empty() && V.back() < C)
		tmp.pb({{2, C - V.back()}, ln});
	for(int i = 0; i + 1 < (int) V.size(); i++){
		if(0 < V[i + 1] - V[i] - 1)
			tmp.pb({{0, V[i + 1] - V[i] - 1}, ln});
	}
	if(V.empty())
		tmp.pb({{1, C}, ln});
	sort(all(tmp));
	int cnt = 0;
	for(int i = 0; i < (int) tmp.size(); i++)
		if((i + 1 == (int) tmp.size()) || (!Better(tmp[i + 1].F, tmp[i].F)) )
			Q.pb(tmp[i]), cnt ++;
	// cerr << "!! " << ' ' << cnt << '\n';
	for(int i = sz; i < (int) Q.size(); i++)
		TQ.pb(Q[i]);
	// Q.resize(sz);
}

int ans[N][N]; // C R

pii Inter(pii A, pii B){ return pii(max(A.F, B.F), min(A.S, B.S)); }
pii Inter(con c, int v){
	if(c.F == 0){
		if(v < c.S)
			return pii(0, v + 1);
		return pii(v + 1, 0);
	} else if(c.F == 1){
		return pii(0, c.S);
	}
	return pii((v - c.S) + 1, v + 1);
}
pii Inter(iff c, int v){ return Inter(Inter(c.F, v), Inter(c.S, v)); }

vector<iff> act;
bool Valid(int v){
	// return false;
	// vector<int> mk(v + 1, 0);
	// v = min(C - 1 + C - 1, v);
	// for(int i = 0, j = v; i < C; i++, j--)
	// 	if(0 <= j && j < C && ans[i][j] == 0)
	// 		return true;
	// return false;
	// vector<iff> tmp = act;
	// act.clear();
	// for(int i = 0; i < (int) tmp.size(); i++)
	// 	if((i + 1 == (int) tmp.size()) || (!Better(tmp[i + 1], tmp[i])) )
	// 		act.pb(tmp[i]);
	
	pii seg = pii(0, C);
	if(v < C)
		seg = pii(0, v + 1);
	else
		seg = pii(v - (C - 1), C);
	// cerr << "!! " << v << ' ' << seg.F << ' ' << seg.S << '\n';

	vector<pii> Al;
	for(auto fi : act){
		pii X = Inter(fi, v);
		X = Inter(X, seg);
		// X.S = min(X.S, v + 1);
		// X.F = max(X.F, 0);
		if(X.F >= X.S) continue;
		Al.pb(X);
		// for(int i = X.F; i < X.S; i++) mk[i] = 1;
	}
	sort(all(Al));
	int nw = seg.F;
	for(auto [l, r] : Al){
		if(nw < l)
			return true;
		nw = max(nw, r);
	}
	if(nw != seg.S)
		return true;
	return false;
	// for(int i = 0; i <= v; i++){
	// 	if(i < C && v - i < C && mk[i] == 0)
	// 		return true;
	// }
	// return false;
}

int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> R >> C >> n;
	for(int i = 1; i <= n; i++){
		cin >> A[i].F >> A[i].S;
	}
	sort(A + 1, A + n + 1);
	// vector<int> V;
	// sort(all(V));
	// for(int i = 1; i <= n; i++) V.pb(A[i].S);
	// int mn_S = 0;
	// for(int i = 0; i < n; i++)
	// 	mn_S = max(mn_S, V[i + 1] - V[i] - 1);
	// Check(0, R + 1);
	// int mx = (A[1].F - 1) + (R - A[n].F);
	Check(0, R + 1);
	for(auto &[cn, sm] : Q)
		sm = Inf;

	// debug(Q.size());

	TQ.clear();
	int sz = Q.size();
	for(int i = 1; i <= n; i++)
		Check(0, A[i].F);
	Q.resize(sz);
	V0 = TQ; TQ.clear();
	for(int i = 1; i <= n; i++)
		Check(A[i].F, R + 1);
	Q.resize(sz);
	V1 = TQ; TQ.clear();
	for(auto [c1, v1] : V0)
		for(auto [c2, v2] : V1)
			cons.pb({{min(c1, c2), max(c1, c2)}, v1 + v2});
	// debug(Q.size());
	Q.resize(sz);
	// debug(Q.size());

	for(int i = 1; i <= n; i++)
		for(int j = i + 1; j <= n; j++)
			if(A[j].F - 1 > A[i].F)
				Check(A[i].F, A[j].F);
	// debug(Q.size());
	for(auto [c1, v1] : Q)
		cons.pb({{c1, c1}, v1});
	
	sort(all(cons), [&](auto e1, auto e2){
		return e1.S > e2.S;
	});
	// debug("X");
	// debug(cons.size());
	int ANS = R + C;
	cons.pb({{{0, 0}, {0, 0}}, 0});
	int la = -1;
	for(auto [fi, v] : cons){
		// debug(v);
		// int CC = C + C;
		// for(int i = 0; i < C; i++){
		// 	for(int j = 0; j < C; j++)
		// 		if(!ans[i][j])
		// 			// CC = min(CC, i + j);
		// 			ANS = min(ANS, i + j + v);
		// }
		if(la == v){
			act.pb(fi);
			continue;
		}
		int L = -1, Rb = C + C - 1;
		int mid;
		while(L + 1 < Rb){
			mid = (L + Rb) >> 1;
			if(Valid(mid)) Rb = mid;
			else L = mid;
		}
		if(Rb != C + C - 1)
			ANS = min(ANS, Rb + v);
		la = v;
		act.pb(fi);
	}
	
	cout << ANS << '\n';
	return 0;
}

Subtask #1

5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	332 KB	Output is correct
6	Correct	1 ms	204 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	1 ms	204 KB	Output is correct
10	Correct	1 ms	204 KB	Output is correct
11	Correct	1 ms	204 KB	Output is correct
12	Correct	1 ms	204 KB	Output is correct
13	Correct	1 ms	204 KB	Output is correct
14	Correct	1 ms	204 KB	Output is correct
15	Correct	1 ms	204 KB	Output is correct
16	Correct	1 ms	204 KB	Output is correct

Subtask #2

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	332 KB	Output is correct
6	Correct	1 ms	204 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	1 ms	204 KB	Output is correct
10	Correct	1 ms	204 KB	Output is correct
11	Correct	1 ms	204 KB	Output is correct
12	Correct	1 ms	204 KB	Output is correct
13	Correct	1 ms	204 KB	Output is correct
14	Correct	1 ms	204 KB	Output is correct
15	Correct	1 ms	204 KB	Output is correct
16	Correct	1 ms	204 KB	Output is correct
17	Correct	2 ms	332 KB	Output is correct
18	Correct	27 ms	1148 KB	Output is correct
19	Correct	8 ms	460 KB	Output is correct
20	Correct	7 ms	460 KB	Output is correct
21	Correct	32 ms	1048 KB	Output is correct
22	Correct	109 ms	2996 KB	Output is correct
23	Correct	9 ms	680 KB	Output is correct
24	Correct	130 ms	4176 KB	Output is correct
25	Correct	132 ms	3692 KB	Output is correct
26	Correct	757 ms	21292 KB	Output is correct
27	Correct	249 ms	7380 KB	Output is correct
28	Correct	163 ms	5788 KB	Output is correct
29	Correct	187 ms	5704 KB	Output is correct
30	Correct	196 ms	6552 KB	Output is correct
31	Correct	269 ms	7776 KB	Output is correct
32	Correct	177 ms	5692 KB	Output is correct

Subtask #3

0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	332 KB	Output is correct
6	Correct	1 ms	204 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	1 ms	204 KB	Output is correct
10	Correct	1 ms	204 KB	Output is correct
11	Correct	1 ms	204 KB	Output is correct
12	Correct	1 ms	204 KB	Output is correct
13	Correct	1 ms	204 KB	Output is correct
14	Correct	1 ms	204 KB	Output is correct
15	Correct	1 ms	204 KB	Output is correct
16	Correct	1 ms	204 KB	Output is correct
17	Correct	2 ms	332 KB	Output is correct
18	Correct	27 ms	1148 KB	Output is correct
19	Correct	8 ms	460 KB	Output is correct
20	Correct	7 ms	460 KB	Output is correct
21	Correct	32 ms	1048 KB	Output is correct
22	Correct	109 ms	2996 KB	Output is correct
23	Correct	9 ms	680 KB	Output is correct
24	Correct	130 ms	4176 KB	Output is correct
25	Correct	132 ms	3692 KB	Output is correct
26	Correct	757 ms	21292 KB	Output is correct
27	Correct	249 ms	7380 KB	Output is correct
28	Correct	163 ms	5788 KB	Output is correct
29	Correct	187 ms	5704 KB	Output is correct
30	Correct	196 ms	6552 KB	Output is correct
31	Correct	269 ms	7776 KB	Output is correct
32	Correct	177 ms	5692 KB	Output is correct
33	Correct	440 ms	21160 KB	Output is correct
34	Execution timed out	2037 ms	33768 KB	Time limit exceeded
35	Halted	0 ms	0 KB	-

Subtask #4

0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	321 ms	460 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #5

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	321 ms	460 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #6

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	332 KB	Output is correct
6	Correct	1 ms	204 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	1 ms	204 KB	Output is correct
10	Correct	1 ms	204 KB	Output is correct
11	Correct	1 ms	204 KB	Output is correct
12	Correct	1 ms	204 KB	Output is correct
13	Correct	1 ms	204 KB	Output is correct
14	Correct	1 ms	204 KB	Output is correct
15	Correct	1 ms	204 KB	Output is correct
16	Correct	1 ms	204 KB	Output is correct
17	Correct	2 ms	332 KB	Output is correct
18	Correct	27 ms	1148 KB	Output is correct
19	Correct	8 ms	460 KB	Output is correct
20	Correct	7 ms	460 KB	Output is correct
21	Correct	32 ms	1048 KB	Output is correct
22	Correct	109 ms	2996 KB	Output is correct
23	Correct	9 ms	680 KB	Output is correct
24	Correct	130 ms	4176 KB	Output is correct
25	Correct	132 ms	3692 KB	Output is correct
26	Correct	757 ms	21292 KB	Output is correct
27	Correct	249 ms	7380 KB	Output is correct
28	Correct	163 ms	5788 KB	Output is correct
29	Correct	187 ms	5704 KB	Output is correct
30	Correct	196 ms	6552 KB	Output is correct
31	Correct	269 ms	7776 KB	Output is correct
32	Correct	177 ms	5692 KB	Output is correct
33	Correct	440 ms	21160 KB	Output is correct
34	Execution timed out	2037 ms	33768 KB	Time limit exceeded
35	Halted	0 ms	0 KB	-