oj.uz

Submission #1000764

# Submission time Handle Problem Language Result Execution time Memory
1000764 2024-06-18T08:30:20 Z Tob Cultivation (JOI17_cultivation) C++14
5 / 100
 1 ms 600 KB 
#include <bits/stdc++.h>
 
#pragma optimize("O3, unroll-loops")
 
#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;
int a[N], b[N];
ll mem[2*N][N];
pll gr[2*N][N];
vector <int> add[2*N], rem[2*N];
 
int main () {
//	FIO;
	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] >= d) v.pb(a[j]-a[i]);
			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) {
		vector <pair <pii, ll> > vv;
		int l = 0, r = -1, z = 0, la = 0;
		for (int i = 0; i < k; i++) {
			while (a[z]+x < a[i]) {
				if (vv.back().S != (ll)a[z]+x+1) {vv.pb({{l+1, r}, (ll)a[z]+x+1}); l++;}
				else vv[vv.size()-1].F.F++, l++;
				z++;
			}
			if (vv.empty() || vv.back().S != a[i]) {vv.pb({{l, r+1}, a[i]}); r++;}
			else vv[vv.size()-1].F.S++, r++;
		}
		la = vv.size();
		while (z < k) {
			if (vv.back().S != (ll)a[z]+x+1) {vv.pb({{l+1, r}, (ll)a[z]+x+1}); l++;}
			else vv[vv.size()-1].F.F++, l++;
			if ((ll)a[z]+x+1 < n) la = vv.size();
			z++;
		}
		vector <ll> v1(la+2, 0), v2(la+2, 0), v3(la+2, 0);
		for (int i = la-1; i >= 0; i--) {
			v1[i] = max(v1[i+1], mem[vv[i].F.S][vv[i].F.F]);
			v2[i] = max(v2[i+1], gr[vv[i].F.S][vv[i].F.F].F);
			v3[i] = max(v3[i+1], gr[vv[i].F.S][vv[i].F.F].S);
		}
		ll mx1 = 0, mx2 = 0, mx3 = 0; z = 0;
		mn = min(mn, x+max(v1[0], v2[0]+v3[0]));
		for (int i = la; i+1 < vv.size() && vv[i].S < 2*n; i++) {
			l = vv[i].F.F;
			r = vv[i].F.S;
			mx1 = max(mx1, mem[r][l]); mx2 = max(mx2, gr[r][l].F); mx3 = max(mx3, gr[r][l].S);
			while (vv[z].S+n-1 < min(2LL*n, vv[i+1].S)) z++;
			mn = min(mn, x+max(max(mx1, v1[z]), max(mx2, v2[z]) + max(mx3, v3[z])));
		}
	}
	
	cout << mn << "\n";
 
	return 0;
}

Compilation message

cultivation.cpp:3: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    3 | #pragma optimize("O3, unroll-loops")
      | 
cultivation.cpp: In function 'int main()':
cultivation.cpp:114:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |   for (int i = la; i+1 < vv.size() && vv[i].S < 2*n; i++) {
      |                    ~~~~^~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Incorrect 1 ms 600 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Incorrect 1 ms 600 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

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

Subtask #5
0 / 20.0

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

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Incorrect 1 ms 600 KB Output isn't correct
18 Halted 0 ms 0 KB -