Submission #1001289

#	Time	Username	Problem	Language	Result	Execution time	Memory
1001289		Tob	Cultivation (JOI17_cultivation)	C++14	100 / 100	836 ms	2788 KiB

cultivation

#include <bits/stdc++.h>
 
#pragma GCC optimize("Ofast")
 
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
 
using namespace std;
 
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
 
const int N = 307, inf = 2e9;
 
int n, m, k, siz;
int a[N], b[N];
int mem[2*N][N];
pii gr[2*N][N];
array <ll,3> vv[2*N];
ll q[6*N], dq[6*N];
 
struct MQ {
	int type, l1, r1, l2, r2;
	inline void push(ll x) {q[++r1] = x; while (l2 <= r2 && dq[r2] < x) r2--; dq[++r2] = x;}
	inline void pop() {if (dq[l2] == q[l1]) l2++; l1++;}
	inline ll get() {return dq[l2];}
	inline void reset() {l1 = l2 = type*2*N; r1 = r2 = l1-1;}
} m1, m2, m3;
 
int main () {
	FIO;
	m1.type = 0;
	m2.type = 1;
	m3.type = 2;
	cin >> n >> m >> k;
	
	vector <pii> so;
	for (int i = 0; i < k; i++) {
		cin >> a[i] >> b[i];
		a[i]--; b[i]--;
		so.pb({a[i], b[i]});
	}
	sort(all(so));
	for (int i = 0; i < k; i++) a[i] = so[i].F, b[i] = so[i].S;
	
	int d = a[0]; for (int i = 0; i < k; i++) a[i] -= d;
	d = n-a[k-1]-1; for (int i = 1; i < k; i++) d = max(d, a[i]-a[i-1]-1);
	a[k] = n-1;
	vector <ll> v; v.pb(d);
	for (int i = 0; i <= k; i++) {
		for (int j = i; j <= k; j++) {
			if (a[j]-a[i]-1 >= d) v.pb(a[j]-a[i]-1);
			if (a[j]+n-a[i]-1 >= d) v.pb(a[j]+n-a[i]-1);
			if (a[i]+n-a[j]-1 >= d) v.pb(a[i]+n-a[j]-1);
		}
		if (n-a[i]-1 >= d) v.pb(n-a[i]-1);
	}
	sort(all(v)); v.erase(unique(all(v)), v.end());
	
	//PRECOMPUTE -> O(N^2 log N)
	for (int i = 0; i < k; i++) {
		set <int> s;
		multiset <int> rj;
		rj.insert(0);
		for (int j = i; j >= 0; j--) {
			mem[i][j] = mem[i][j+1];
			gr[i][j].F = gr[i][j+1].F;
			gr[i][j].S = gr[i][j+1].S;
			if (s.find(b[j]) != s.end()) continue;
			auto p1 = s.lower_bound(b[j]);
			if (p1 == s.end()) {
				if (!s.empty()) rj.insert(b[j]-*(--p1)-1);
				s.insert(b[j]);
				gr[i][j] = {*s.begin(), m-*s.rbegin()-1};
			}
			else if (p1 == s.begin()) {
				rj.insert(*p1-b[j]-1);
				s.insert(b[j]);
				gr[i][j] = {*s.begin(), m-*s.rbegin()-1};
			}
			else {
				int x = *p1; --p1; int y = *p1;
				rj.erase(rj.find(x-y-1));
				rj.insert(x-b[j]-1);
				rj.insert(b[j]-y-1);
				s.insert(b[j]);
			}
			mem[i][j] = *rj.rbegin();
		}
	}
	
	//SOLVE O(N^3)
	ll mn = inf;
	for (auto x : v) {
		m1.reset(); m2.reset(); m3.reset(); siz = 0;
		int l = 0, r = -1, z = 0;
		for (int i = 0; i < k; i++) {
			while (a[z]+x < a[i]) {
				int gt = (x+a[z]+1 < 2LL*n) ? x+a[z]+1 : 2*n;
				if (vv[siz-1][2] != gt) {vv[siz++] = {l+1, r, gt}; l++;}
				else vv[siz-1][0]++, l++;
				z++;
			}
			if (!siz || vv[siz-1][2] != a[i]) {vv[siz++] = {l, r+1, a[i]}; r++;}
			else vv[siz-1][1]++, r++;
		}
		while (z < k) {
			int gt = (x+a[z]+1 < 2LL*n) ? x+a[z]+1 : 2*n;
			if (vv[siz-1][2] != gt) {vv[siz++] = {l+1, r, gt}; l++;}
			else vv[siz-1][0]++, l++;
			z++;
		}
		z = 0;
		#define C (x+max(m1.get(), m2.get()+m3.get()))
		
		for (int i = 0; i+1 < siz && vv[i][2] < 2*n; i++) {
			l = vv[i][0];
			r = vv[i][1];
			m1.push(mem[r][l]); m2.push(gr[r][l].F); m3.push(gr[r][l].S);
			while (vv[z][2]+n-1 < vv[i+1][2]) {
				mn = min(mn, C);
				m1.pop(); m2.pop(); m3.pop();
				z++;
			}
		}
	}
	
	cout << mn << "\n";
 
	return 0;
}

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