| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 55311 | ksun48 | Cultivation (JOI17_cultivation) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int r, c, n;
vector<pair<int,int> > seeds;
const int INF = 2100100100;
int best = INF;
set<int> tried;
struct maxqueue {
vector<int> elements;
vector<int> indices;
int s;
int len;
maxqueue() : s(0), len(0), elements(0), indices(0) {}
};
void insert(maxqueue* m, int f){
while(m->elements.size() > 0 && m->elements.size() > m->s && m->elements[m->elements.size()-1] <= f){
m->elements.pop_back();
m->indices.pop_back();
}
m->elements.push_back(f);
m->indices.push_back(m->len);
m->len++;
}
int get(maxqueue* m){
return m->elements[m->s];
}
void pop(maxqueue *m, int idx){
if(m->indices[m->s] == idx){
m->s++;
}
}
void tryxfast(int x){
if(x < 0){
return;
}
set<int> times;
for(pair<int,int> z : seeds){
times.insert(z.first - x);
times.insert(z.first + 1);
}
vector<int> pos;
for(int t : times){
pos.push_back(t);
}
vector<int> ins[pos.size()];
vector<int> del[pos.size()];
for(pair<int,int> z : seeds){
ins[lower_bound(pos.begin(), pos.end(), z.first - x)-pos.begin()].push_back(z.second); // ins
del[lower_bound(pos.begin(), pos.end(), z.first + 1)-pos.begiN()].push_back(z.second); // del
}
vector<int> ups;
vector<int> downs;
vector<int> totals;
multiset<int> grass;
grass.insert(-1);
grass.insert(c);
multiset<int> diffs;
diffs.insert(-(c+1));
for(int i = 0; i < pos.size(); i++){
for(int a : del[i]){
int a1 = *(--grass.find(a));
int a2 = *(++grass.find(a));
diffs.erase(diffs.find(a1-a));
diffs.erase(diffs.find(a-a2));
diffs.insert(a1-a2);
grass.erase(grass.find(a));
}
for(int a : ins[i]){
grass.insert(a);
int a1 = *(--grass.find(a));
int a2 = *(++grass.find(a));
diffs.erase(diffs.find(a1-a2));
diffs.insert(a1-a);
diffs.insert(a-a2);
}
totals.push_back( -*diffs.begin() );
ups.push_back( *(++grass.begin()) - 0 );
downs.push_back( c-1 - *(--(--grass.end())) );
}
// two pointers:
int j = 0;
maxqueue* upset = new maxqueue();
maxqueue* downset = new maxqueue();
maxqueue* totalset = new maxqueue();
for(int i = 0; i < pos.size(); i++){
while(j < pos.size() && pos[j] <= pos[i] + r - 1){
insert(upset, ups[j]);
insert(downset, downs[j]);
insert(totalset, totals[j]);
j++;
}
int total = get(totalset);
if(total < c+1){
LL need = max((LL)get(upset) + (LL)get(downset), (LL)total - 1);
best = (int)min((LL)best, need + x);
}
pop(upset, i);
pop(downset, i);
pop(totalset, i);
}
delete upset;
delete downset;
delete totalset;
}
int main(){
cin.sync_with_stdio(0); cin.tie(0);
cin >> r >> c >> n;
for(int i = 0; i < n; i++){
int s, e;
cin >> s >> e;
s--; e--;
seeds.push_back({s,e});
}
sort(seeds.begin(), seeds.end());
set<int> trying;
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
trying.insert(seeds[i].first + r-1 - seeds[j].first);
trying.insert(seeds[i].first - 1 - seeds[j].first);
}
}
for(int r : trying){
tryxfast(r);
}
cout << best << '\n';
}