oj.uz

Submission #671993

# Submission time Handle Problem Language Result Execution time Memory
671993 2022-12-14T14:43:05 Z amunduzbaev Cultivation (JOI17_cultivation) C++17
5 / 100
 221 ms 320 KB 
#include "bits/stdc++.h"
using namespace std;

#define ar array
typedef long long ll;
//~ #define int ll

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n, m; cin >> n >> m;
	int sz; cin >> sz;
	vector<int> x(sz), y(sz), t;
	for(int i=0;i<sz;i++){
		cin >> x[i] >> y[i];
	} 
	//~ assert(sz <= 1);
	
	t = x;
	sort(t.begin(), t.end());
	t.erase(unique(t.begin(), t.end()), t.end());
	vector<int> used(t.size());
	
	vector<int> id(sz);
	for(int i=0;i<sz;i++){
		id[i] = lower_bound(t.begin(), t.end(), x[i]) - t.begin() + 1;
	}
	
	ll res = 2 * (n + m);
	auto check = [&](int d){
		vector<ar<int, 2>> tot;
		for(int i=0;i<sz;i++){
			//~ cout<<max(1LL, y[i] - w)<<" "<<min(y[i] + e, m)<<"\n";
			tot.push_back({y[i], id[i]});
			tot.push_back({y[i] + d + 1, -id[i]});
		}
		sort(tot.begin(), tot.end());
		vector<int> v, is;
		vector<ar<int, 3>> Mn;
		multiset<int> mn, used;
		mn.insert(0);
		
		auto add = [&](int x){
			if(used.empty()){
				used.insert(x);
				return;
			}
			auto it = used.upper_bound(x);
			if(it == used.begin()){
				mn.insert(*it - x - 1);
				used.insert(x);
				return;
			}
			if(it == used.end()){
				it--;
				mn.insert(x - *it - 1);
				used.insert(x);
				return;
			}
			
			auto l = it; l--;
			mn.erase(mn.find(*it - *l - 1));
			mn.insert(*it - x - 1);
			mn.insert(x - *l - 1);
			used.insert(x);
		};
		auto del = [&](int x){
			used.erase(used.find(x));
			if(used.empty()) return;
			auto it = used.upper_bound(x);
			if(it == used.begin()){
				mn.erase(mn.find(*it - x - 1));
				return;
			}
			if(it == used.end()){
				it--;
				mn.erase(mn.find(x - *it - 1));
				return;
			}
			
			auto l = it; l--;
			mn.erase(mn.find(*it - x - 1));
			mn.erase(mn.find(x - *l - 1));
			mn.insert(*it - *l - 1);
		};
		
		for(int i=0;i<(int)tot.size();){
			int j = i;
			while(j < (int)tot.size() && tot[j][0] == tot[i][0]){
				if(tot[j][1] > 0) add(t[tot[j][1] - 1]);
				else del(t[-tot[j][1] - 1]);
				j++;
			}
			
			v.push_back(tot[i][0]);
			if(used.empty()){
				Mn.push_back({0, 0, 0});
				is.push_back(1);
			} else {
				assert(!mn.empty());
				Mn.push_back({*used.begin() - 1, n - *--used.end(), *--mn.end()});
				is.push_back(0);
			}
			
			i = j;
		}
		
		//~ cout<<d<<"\n";
		//~ for(int i=0;i<(int)v.size();i++){
			//~ cout<<v[i]<<" ";
		//~ } cout<<"\n";
		//~ for(int i=0;i<(int)v.size();i++){
			//~ cout<<is[i]<<" ";
		//~ } cout<<"\n";
		//~ for(int i=0;i<(int)v.size();i++){
			//~ cout<<Mn[i][0]<<" ";
		//~ } cout<<"\n";
		//~ for(int i=0;i<(int)v.size();i++){
			//~ cout<<Mn[i][1]<<" ";
		//~ } cout<<"\n";
		//~ for(int i=0;i<(int)v.size();i++){
			//~ cout<<Mn[i][2]<<" ";
		//~ } cout<<"\n";
		
		multiset<int> mnl, mnr;
		mn.clear();
		int r = 0, cnt = 0;
		for(int i=0;i + 1 < (int)v.size();i++){
			while(r < (int)v.size() && v[r] - v[i] < m){
				mn.insert(Mn[r][2]);
				mnl.insert(Mn[r][0]);
				mnr.insert(Mn[r][1]);
				cnt += is[r];
				r++;
			}
			
			if(cnt == 0){
				res = min(res, 1ll * d + max(*--mn.end(), *--mnl.end() + *--mnr.end()));
			}
			
			mn.erase(mn.find(Mn[i][2]));
			mnl.erase(mnl.find(Mn[i][0]));
			mnr.erase(mnr.find(Mn[i][1]));
			cnt -= is[i];
		}
	};
	
	//~ check(4);
	
	for(int i=0;i<sz;i++){
		for(int j=0;j<sz;j++){
			if(y[i] <= y[j]){
				check(y[i] - 1 + m - y[j]);
			}
		}
		
		for(int k=0;k<sz;k++){
			if(y[i] >= y[k]) continue;
			check(y[k] - y[i] - 1);
		}
	}
	
	cout<<res<<"\n";
}

Subtask #1
5.0 / 5.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 5 ms 212 KB Output is correct
18 Correct 221 ms 312 KB Output is correct
19 Correct 18 ms 212 KB Output is correct
20 Correct 6 ms 320 KB Output is correct
21 Incorrect 96 ms 304 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 5 ms 212 KB Output is correct
18 Correct 221 ms 312 KB Output is correct
19 Correct 18 ms 212 KB Output is correct
20 Correct 6 ms 320 KB Output is correct
21 Incorrect 96 ms 304 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

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

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 320 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 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 5 ms 212 KB Output is correct
18 Correct 221 ms 312 KB Output is correct
19 Correct 18 ms 212 KB Output is correct
20 Correct 6 ms 320 KB Output is correct
21 Incorrect 96 ms 304 KB Output isn't correct
22 Halted 0 ms 0 KB -