| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 55605 | 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;
vector<int> xlist;
int len;
int up[400][400];
int down[400][400];
int total[400][400];
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++;
}
}
int ups[700];
int downs[700];
int totals[700];
int pos1[700];
int pos2[700];
int pos[700];
int lastc = 0;
void tryxfast(int x){
if(x < 0 || (x+1) <= (r-1)/n || (LL)x >= (LL)best - (LL)lastc){
return;
}
for(int i = 0; i < len; i++){
pos1[i] = xlist[i] - x;
pos2[i] = xlist[i] + 1;
}
merge(pos1, pos1 + len, pos2, pos2 + len, pos);
int sz = len * 2;
int a = 0;
int b = 0;
for(int i = 0; i < sz; i++){
while(a + 1 < len && xlist[a+1] - x <= pos[i]) a++;
while(b + 1 < len && xlist[b+1] + 1 <= pos[i]) b++;
// a >= b
ups[i] = up[a][b];
downs[i] = down[a][b];
totals[i] = total[a][b];
}
// two pointers:
int j = 0;
maxqueue* upset = new maxqueue();
maxqueue* downset = new maxqueue();
maxqueue* totalset = new maxqueue();
LL bestneed = best + 1;
for(int i = 0; i < sz; i++){
while(j < sz && pos[j] <= pos[i] + r - 1){
insert(upset, ups[j]);
insert(downset, downs[j]);
insert(totalset, totals[j]);
j++;
}
if(j == sz) break;
int total = get(totalset);
if(total < c+1){
LL need = max((LL)get(upset) + (LL)get(downset), (LL)total - 1);
bestneed = min(bestneed, need);
}
pop(upset, i);
pop(downset, i);
pop(totalset, i);
}
lastc = bestneed;
best = min((LL)best, bestneed + (LL)x);
}
int main(){
double st = time();
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({e,s});
}
sort(seeds.begin(), seeds.end());
set<int> xset;
for(int i = 0; i < n; i++){
swap(seeds[i].first, seeds[i].second);
xset.insert(seeds[i].first);
}
xlist.push_back(-1);
for(int x : xset){
xlist.push_back(x);
}
len = xlist.size();
// now n^2 log n
for(int i = 0; i < xlist.size(); i++){
vector<int> ins[xlist.size() + 1];
vector<int> del[xlist.size() + 1];
for(int k = 0; k < seeds.size(); k++){
int p = seeds[k].first;
if(p <= xlist[i]){
ins[0].push_back(seeds[k].second);
int jdel = lower_bound(xlist.begin(), xlist.end(), p) - xlist.begin();
del[jdel].push_back(seeds[k].second);
}
}
multiset<int> grass;
grass.insert(-1);
grass.insert(c);
multiset<int> diffs;
diffs.insert(-(c+1));
for(int j = 0; j <= i; j++){
for(int a : del[j]){
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[j]){
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);
}
total[i][j] = -*diffs.begin();
up[i][j] = *(++grass.begin()) - 0;
down[i][j] = c-1 - *(--(--grass.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));
}
}
vector<int> tries;
for(int r : trying){
tries.push_back(-r);
}
for(int j = 0; j < 500 && j < tries.size(); j++){
lastc = 0;
tryxfast(tries[tries.size()-1-j]);
}
lastc = 0;
for(int r : tries){
if(clock() > time + 1.95 * CLOCKS_PER_SEC) break;
tryxfast(r);
}
cout << best << '\n';
}