Submission #55504

#TimeUsernameProblemLanguageResultExecution timeMemory
55504ksun48Cultivation (JOI17_cultivation)C++14
80 / 100
2065 ms24464 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; 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; } vector<int> pos; for(pair<int,int> z : seeds){ pos.push_back(z.first - x); pos.push_back(z.first + 1); } sort(pos.begin(), pos.end()); 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 (stderr)

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:72:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < pos.size(); i++){
                 ~~^~~~~~~~~~~~
cultivation.cpp:90:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < pos.size(); i++){
                 ~~^~~~~~~~~~~~
cultivation.cpp:91: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:128:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < xlist.size(); i++){
                 ~~^~~~~~~~~~~~~~
cultivation.cpp:132:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int k = 0; k < seeds.size(); k++){
                   ~~^~~~~~~~~~~~~~
cultivation.cpp:138:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i = 0; i + 1 < stuff.size(); i++){
                   ~~~~~~^~~~~~~~~~~~~~
#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...