Submission #55620

#TimeUsernameProblemLanguageResultExecution timeMemory
55620ksun48Cultivation (JOI17_cultivation)C++14
80 / 100
1983 ms95176 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 len; 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 ups[700]; int downs[700]; int totals[700]; int pos1[700]; int pos2[700]; int pos[700]; int lastc = 0; void tryxfast(int x){ if(x < 0 || (x+1) <= (r-1)/n || (LL)x >= (LL)best - (LL)lastc){ return; } for(int i = 0; i < len; i++){ pos1[i] = xlist[i] - x; pos2[i] = xlist[i] + 1; } merge(pos1, pos1 + len, pos2, pos2 + len, pos); int sz = len * 2; int a = 0; int b = 0; for(int i = 0; i < sz; i++){ while(a + 1 < len && xlist[a+1] - x <= pos[i]) a++; while(b + 1 < len && xlist[b+1] + 1 <= pos[i]) b++; // a >= b ups[i] = up[a][b]; downs[i] = down[a][b]; totals[i] = total[a][b]; } // two pointers: int j = 0; maxqueue* upset = new maxqueue(); maxqueue* downset = new maxqueue(); maxqueue* totalset = new maxqueue(); LL bestneed = best + 1; for(int i = 0; i < sz; i++){ while(j < sz && pos[j] <= pos[i] + r - 1){ insert(upset, ups[j]); insert(downset, downs[j]); insert(totalset, totals[j]); j++; } if(j == sz) break; int total = get(totalset); if(total < c+1){ LL need = max((LL)get(upset) + (LL)get(downset), (LL)total - 1); bestneed = min(bestneed, need); } pop(upset, i); pop(downset, i); pop(totalset, i); } lastc = bestneed; best = min((LL)best, bestneed + (LL)x); } int main(){ double st = clock(); 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); } len = xlist.size(); // now n^2 log n for(int i = 0; i < xlist.size(); i++){ vector<int> ins[xlist.size() + 1]; vector<int> del[xlist.size() + 1]; for(int k = 0; k < seeds.size(); k++){ int p = seeds[k].first; if(p <= xlist[i]){ ins[0].push_back(seeds[k].second); int jdel = lower_bound(xlist.begin(), xlist.end(), p) - xlist.begin(); del[jdel].push_back(seeds[k].second); } } multiset<int> grass; grass.insert(-1); grass.insert(c); multiset<int> diffs; diffs.insert(-(c+1)); for(int j = 0; j <= i; j++){ for(int a : del[j]){ 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)); } for(int a : ins[j]){ 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); } total[i][j] = -*diffs.begin(); up[i][j] = *(++grass.begin()) - 0; down[i][j] = c-1 - *(--(--grass.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)); } } vector<int> tries; for(int r : trying){ tries.push_back(-r); } for(int j = 50000; j < 60000 && j < tries.size(); j++){ lastc = 0; tryxfast(tries[tries.size()-1-j]); } for(int j = 40000; j < 50000 && j < tries.size(); j++){ lastc = 0; tryxfast(tries[tries.size()-1-j]); } lastc = 0; for(int r : tries){ if(clock() > st + 1.95 * CLOCKS_PER_SEC) break; tryxfast(r); } cout << best << '\n'; }

Compilation message (stderr)

cultivation.cpp: In constructor 'maxqueue::maxqueue()':
cultivation.cpp:22:6: warning: 'maxqueue::len' will be initialized after [-Wreorder]
  int len;
      ^~~
cultivation.cpp:19:14: warning:   'std::vector<int> maxqueue::elements' [-Wreorder]
  vector<int> elements;
              ^~~~~~~~
cultivation.cpp:23: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:27: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 'int main()':
cultivation.cpp:126:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < xlist.size(); i++){
                 ~~^~~~~~~~~~~~~~
cultivation.cpp:130:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int k = 0; k < seeds.size(); k++){
                  ~~^~~~~~~~~~~~~~
cultivation.cpp:178:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int j = 50000; j < 60000 && j < tries.size(); j++){
                                  ~~^~~~~~~~~~~~~~
cultivation.cpp:182:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int j = 40000; j < 50000 && j < tries.size(); j++){
                                  ~~^~~~~~~~~~~~~~
#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...