Submission #55405

#TimeUsernameProblemLanguageResultExecution timeMemory
55405ksun48Cultivation (JOI17_cultivation)C++14
60 / 100
2084 ms9180 KiB
#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]){ auto it = grass.find(a); int a1 = *(--it); int a2 = *(++(++it)); diffs.erase(diffs.find(a1-a)); diffs.erase(diffs.find(a-a2)); diffs.insert(a1-a2); grass.erase(--it); } for(int a : ins[i]){ auto it = grass.insert(a); int a1 = *(--it); int a2 = *(++(++it)); 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); } } 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'; }

Compilation message (stderr)

cultivation.cpp: In constructor 'maxqueue::maxqueue()':
cultivation.cpp:15: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:16: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:20: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:66:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < pos.size(); i++){
                 ~~^~~~~~~~~~~~
cultivation.cpp:93:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < pos.size(); i++){
                 ~~^~~~~~~~~~~~
cultivation.cpp:94:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(j < pos.size() && pos[j] <= pos[i] + r - 1){
         ~~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...