#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL r, c, n;
vector<pair<LL,LL> > seeds;
const LL INF = 2100100100;
LL best = INF;
set<LL> tried;
void tryxfast(LL x){
if(x < 0 || tried.find(x) != tried.end()){
return;
}
tried.insert(x);
map<LL, vector<pair<LL, LL> > > events;
for(pair<LL,LL> z : seeds){
events[z.first].push_back({0, z.second}); // ins
events[z.first + x + 1].push_back({1, z.second}); // del
}
vector<LL> pos;
vector<LL> ups;
vector<LL> downs;
vector<LL> totals;
multiset<LL> grass;
grass.insert(-1);
grass.insert(c);
multiset<LL> diffs;
diffs.insert(c+1);
for(auto tt : events){
for(pair<LL,LL> event : tt.second){
LL a = event.second;
if(event.first == 0){
grass.insert(a);
}
LL a1 = *(--grass.find(a));
LL a2 = *(++grass.find(a));
if(event.first == 0){
diffs.erase(diffs.find(a2-a1));
diffs.insert(a-a1);
diffs.insert(a2-a);
} else if(event.first == 1){
diffs.erase(diffs.find(a-a1));
diffs.erase(diffs.find(a2-a));
diffs.insert(a2-a1);
}
if(event.first == 1){
grass.erase(grass.find(a));
}
}
pos.push_back(tt.first);
totals.push_back( *(--diffs.end()) );
ups.push_back( *(++grass.begin()) - 0 );
downs.push_back( c-1 - *(--(--grass.end())) );
}
// two pointers:
LL j = 0;
multiset<LL> upset;
multiset<LL> downset;
multiset<LL> totalset;
for(LL 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++;
}
LL total = *(--totalset.end());
if(total < c+1){
best = min(best, max(*(--upset.end()) + *(--downset.end()), total - 1) + 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(LL i = 0; i < n; i++){
LL s, e;
cin >> s >> e;
s--; e--;
seeds.push_back({s,e});
}
sort(seeds.begin(), seeds.end());
for(LL i = 0; i < n; i++){
for(LL 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 function 'void tryxfast(LL)':
cultivation.cpp:63:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(LL i = 0; i < pos.size(); i++){
~~^~~~~~~~~~~~
cultivation.cpp:64: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 |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
484 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
484 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
