#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 curidx;
int len;
maxqueue() : s(0), curidx(0), len(0), elements(0), indices(0) {}
};
void insert(maxqueue* m, int f){
while(m->elements.size() > 0 && 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){
if(m->indices[m->s] == m->curidx){
m->s++;
}
m->curidx++;
}
void tryxfast(int x){
if(x < 0 || tried.find(x) != tried.end()){
return;
}
tried.insert(x);
set<int> times;
for(pair<int,int> z : seeds){
times.insert(z.first - x);
times.insert(z.first + 1);
}
vector<int> pos;
map<int,int> idx;
for(int t : times){
idx[t] = pos.size();
pos.push_back(t);
}
vector<int> ins[pos.size()];
vector<int> del[pos.size()];
for(pair<int,int> z : seeds){
ins[idx[z.first - x]].push_back(z.second); // ins
del[idx[z.first + 1]].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 : 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);
}
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));
}
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);
pop(downset);
pop(totalset);
}
delete upset;
delete downset;
delete totalset;
/*// two pointers:
int j = 0;
multiset<int> upset;
multiset<int> downset;
multiset<int> totalset;
for(int i = 0; i < pos.size(); i++){
while(j < pos.size() && pos[j] <= pos[i] + r - 1){
upset.insert(-ups[j]);
downset.insert(-downs[j]);
totalset.insert(-totals[j]);
j++;
}
int total = -*totalset.begin();
if(total < c+1){
LL need = max((LL)-*upset.begin() + (LL)-*downset.begin(), (LL)total - 1);
best = (int)min((LL)best, need + x);
}
upset.erase(upset.find(-ups[i]));
downset.erase(downset.find(-downs[i]));
totalset.erase(totalset.find(-totals[i]));
}*/
}
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());
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
tryxfast(seeds[i].first + r-1 - seeds[j].first);
tryxfast(seeds[i].first - 1 - seeds[j].first);
}
}
cout << best << '\n';
}
Compilation message
cultivation.cpp: In constructor 'maxqueue::maxqueue()':
cultivation.cpp:16:6: warning: 'maxqueue::len' will be initialized after [-Wreorder]
int len;
^~~
cultivation.cpp:12:14: warning: 'std::vector<int> maxqueue::elements' [-Wreorder]
vector<int> elements;
^~~~~~~~
cultivation.cpp:17:2: warning: when initialized here [-Wreorder]
maxqueue() : s(0), curidx(0), len(0), elements(0), indices(0) {}
^~~~~~~~
cultivation.cpp: In function 'void tryxfast(int)':
cultivation.cpp:71:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < pos.size(); i++){
~~^~~~~~~~~~~~
cultivation.cpp:97:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < pos.size(); i++){
~~^~~~~~~~~~~~
cultivation.cpp:98:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(j < pos.size() && pos[j] <= pos[i] + r - 1){
~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
248 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
248 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
248 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
356 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
356 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
248 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
