#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 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 idx(LL a){
int s = 0;
int e = xlist.size();
while(s + 1 < e){
int m = (s+e) / 2;
if(a >= xlist[m]){
s = m;
} else {
e = m;
}
}
return 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;
int i1 = 0;
int j1 = 0;
while(i1 < seeds.size() || j1 < seeds.size()){
if(i1 == seeds.size()){
pos.push_back(seeds[j1++].first + 1);
} else if(j1 == seeds.size()){
pos.push_back(seeds[i1++].first - x);
} else if(seeds[i1].first - x == seeds[j1].first + 1){
pos.push_back(seeds[i1++].first - x);
j1++;
} else if(seeds[i1].first - x < seeds[j1].first + 1){
pos.push_back(seeds[i1++].first - x);
} else {
pos.push_back(seeds[j1++].first + 1);
}
}
vector<int> ups;
vector<int> downs;
vector<int> totals;
for(int i = 0; i < pos.size(); i++){
// use -pos[i]-x, x-pos[i]+1 for start and end
// where start and end column is relative to your column
// replace this with lookup of up, down totals for each
int a = idx((LL)pos[i]+x);
int b = idx((LL)pos[i]-1);
// a >= b
ups.push_back(up[a][b]);
downs.push_back(down[a][b]);
totals.push_back(total[a][b]);
}
// 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);
}
}
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({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);
}
for(int i = 0; i < xlist.size(); i++){
for(int j = 0; j <= i; j++){
vector<int> stuff;
int tot = 0;
for(int k = 0; k < seeds.size(); k++){
int p = seeds[k].first;
if(p <= xlist[i] && p > xlist[j]){
stuff.push_back(seeds[k].second);
}
}
for(int i = 0; i + 1 < stuff.size(); i++){
tot = max(tot, stuff[i+1] - stuff[i]);
}
if(stuff.size() == 0){
total[i][j] = up[i][j] = down[i][j] = c+1;
} else {
assert(i > j);
up[i][j] = stuff[0] - 0;
down[i][j] = c-1 - stuff[stuff.size()-1];
total[i][j] = tot;
}
}
}
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';
}
Compilation message
cultivation.cpp: In constructor 'maxqueue::maxqueue()':
cultivation.cpp:21:6: warning: 'maxqueue::len' will be initialized after [-Wreorder]
int len;
^~~
cultivation.cpp:18:14: warning: 'std::vector<int> maxqueue::elements' [-Wreorder]
vector<int> elements;
^~~~~~~~
cultivation.cpp:22:2: warning: when initialized here [-Wreorder]
maxqueue() : s(0), len(0), elements(0), indices(0) {}
^~~~~~~~
cultivation.cpp: In function 'void insert(maxqueue*, int)':
cultivation.cpp:26:53: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(m->elements.size() > 0 && m->elements.size() > m->s && m->elements[m->elements.size()-1] <= f){
~~~~~~~~~~~~~~~~~~~^~~~~~
cultivation.cpp: In function 'void tryxfast(int)':
cultivation.cpp:69:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(i1 < seeds.size() || j1 < seeds.size()){
~~~^~~~~~~~~~~~~~
cultivation.cpp:69:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(i1 < seeds.size() || j1 < seeds.size()){
~~~^~~~~~~~~~~~~~
cultivation.cpp:70:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(i1 == seeds.size()){
~~~^~~~~~~~~~~~~~~
cultivation.cpp:72:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
} else if(j1 == seeds.size()){
~~~^~~~~~~~~~~~~~~
cultivation.cpp:88:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < pos.size(); i++){
~~^~~~~~~~~~~~
cultivation.cpp:106:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < pos.size(); i++){
~~^~~~~~~~~~~~
cultivation.cpp:107:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(j < pos.size() && pos[j] <= pos[i] + r - 1){
~~^~~~~~~~~~~~
cultivation.cpp: In function 'int main()':
cultivation.cpp:144:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < xlist.size(); i++){
~~^~~~~~~~~~~~~~
cultivation.cpp:148:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int k = 0; k < seeds.size(); k++){
~~^~~~~~~~~~~~~~
cultivation.cpp:154:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i + 1 < stuff.size(); i++){
~~~~~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
248 KB |
Output is correct |
| 2 |
Correct |
2 ms |
356 KB |
Output is correct |
| 3 |
Correct |
2 ms |
560 KB |
Output is correct |
| 4 |
Correct |
3 ms |
560 KB |
Output is correct |
| 5 |
Incorrect |
3 ms |
560 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
248 KB |
Output is correct |
| 2 |
Correct |
2 ms |
356 KB |
Output is correct |
| 3 |
Correct |
2 ms |
560 KB |
Output is correct |
| 4 |
Correct |
3 ms |
560 KB |
Output is correct |
| 5 |
Incorrect |
3 ms |
560 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
248 KB |
Output is correct |
| 2 |
Correct |
2 ms |
356 KB |
Output is correct |
| 3 |
Correct |
2 ms |
560 KB |
Output is correct |
| 4 |
Correct |
3 ms |
560 KB |
Output is correct |
| 5 |
Incorrect |
3 ms |
560 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
792 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
792 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
248 KB |
Output is correct |
| 2 |
Correct |
2 ms |
356 KB |
Output is correct |
| 3 |
Correct |
2 ms |
560 KB |
Output is correct |
| 4 |
Correct |
3 ms |
560 KB |
Output is correct |
| 5 |
Incorrect |
3 ms |
560 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
