Submission #63111

#	Time	Username	Problem	Language	Result	Execution time	Memory
63111		Arturgo	Cultivation (JOI17_cultivation)	C++11	80 / 100	2049 ms	9412 KiB

cultivation

#include <iostream>
#include <queue>
#include <map>
#include <vector>
#include <algorithm>
#include <list>
#include <set>
#include <cassert>
using namespace std;

int nbLigs, nbCols;
vector<pair<int, int>> points;

struct pfile {
  int deb, fin;
  pair<long long, int> elems[1000];

  inline void vide() {
    deb = fin = 0;
  }

  inline void ajoute(long long date, int val) {
    while(deb != fin && elems[fin - 1].second <= val) {
      fin--;
    }
    elems[fin++] = {date, val};
  }
  
  inline int taille() {
    return fin - deb;
  }

  inline void supprime(long long date) {
    while(deb != fin && elems[deb].first <= date)
      deb++;
  }

  inline int maximum() {
    if(deb == fin)
      return 2000*1000*1000;
    return elems[deb].second;
  }
};

struct max_ecart {
  map<int, int> positions;
  priority_queue<pair<int, int>> ecarts;

  max_ecart() {
    positions[-1]++;
    positions[nbLigs]++;
    ecarts.push({nbLigs + 1, -1}); 
  }

  int tr(int dist) {
    if(dist == nbLigs)
      return 2000 * 1000 * 1000;
    return dist;
  }

  void ajoute(int pos) {
    auto it = positions.lower_bound(pos);
    int deb, fin;
    fin = it->first;
    it--;
    deb = it->first;

    positions[pos]++;
    
    ecarts.push({fin - pos, pos});
    ecarts.push({pos - deb, deb});
  }

  int minN() {
    auto it = positions.begin();
    it++;
    return tr(it->first);
  }

  int minS() {
    auto it = positions.rbegin();
    it++;
    return tr(nbLigs - it->first - 1);
  }

  int minTot() {
    while(!ecarts.empty()) {
      pair<int, int> t = ecarts.top();

      if(positions.find(t.second) != positions.end() && positions.upper_bound(t.second)->first == t.first + t.second) {
	return tr(t.first - 1);
      }
      else {
	ecarts.pop();
      }
    }
    return 2000 * 1000 * 1000;
  }
};

struct Inter {
  long long taille;
  int minN, minS, minTot;
};

Inter dyn_inters[300][300];

void precalcule_ecarts() {
  for(int iDeb = 0;iDeb < (int)points.size();iDeb++) {
    max_ecart curEcarts;
    for(int iFin = iDeb;iFin < (int)points.size();iFin++) {
      curEcarts.ajoute(points[iFin].first);
      Inter nouv;
      nouv.minN = curEcarts.minN();
      nouv.minS = curEcarts.minS();
      nouv.minTot = curEcarts.minTot();
      dyn_inters[iDeb][iFin] = nouv;
    }
  }
}

pfile minS, minN, minTot;

long long traite(long long dist) {
  vector<Inter> intervalles;
  
  Inter debut;
  debut.minN = debut.minS = debut.minTot = 2000 * 1000 * 1000;
  intervalles.push_back(debut);
  
  long long derDeb = -1000 * 1000 * 1000;

  int debInd = 0, finInd = 0;

  int iDebut = 0, iFin = 0;
  
  while(iDebut != (int)points.size() || iFin != (int)points.size()) {
    long long minTemps = (long long)4000 * 1000 * 1000;
    if(iDebut != (int)points.size())
      minTemps = min<long long>(minTemps, points[iDebut].second);
    if(iFin != (int)points.size())
      minTemps = min<long long>(minTemps, points[iFin].second + dist);
    
    intervalles.back().taille = minTemps - derDeb;
    derDeb = minTemps;

    while(iDebut != (int)points.size() && points[iDebut].second == minTemps) {
      finInd++;
      iDebut++;
    }

    while(iFin != (int)points.size() && points[iFin].second + dist == minTemps) {
      debInd++;
      iFin++;
    }

    Inter nouv;
    if(debInd == finInd) {
      nouv.minS = nouv.minN = nouv.minTot = 1000 * 1000 * 1000;
    }
    else {
      nouv = dyn_inters[debInd][finInd - 1];
    }
    intervalles.push_back(nouv);
  }
  
  intervalles.back().taille = 1000 * 1000 * 1000;

  long long minPrix = 2000 * 1000 * 1000;

  long long posFin = 0, posDeb = 0;
  int fin = 1;

  minS.vide();
  minN.vide();
  minTot.vide();
  for(int deb = 1;fin < (int)intervalles.size() - 1;) {
    if(posFin - posDeb < nbCols) {
      posFin += intervalles[fin].taille;
      minS.ajoute(posFin, intervalles[fin].minS);
      minN.ajoute(posFin, intervalles[fin].minN);
      minTot.ajoute(posFin, intervalles[fin].minTot);
      fin++;
    }

    if(posFin - posDeb >= nbCols) {
      minPrix = min<long long>(minPrix, max(minS.maximum() + minN.maximum(), minTot.maximum()));
      posDeb += intervalles[deb].taille;
      minS.supprime(posDeb);
      minN.supprime(posDeb);
      minTot.supprime(posDeb);
      deb++;
    }
  }

  return minPrix + dist - 1;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin >> nbCols >> nbLigs;
  
  int nbPoints;
  cin >> nbPoints;
  
  for(int iPoint = 0;iPoint < nbPoints;iPoint++) {
    int lig, col;
    cin >> lig >> col;
    points.push_back({col - 1, lig - 1});
  }

  sort(points.begin(), points.end(), [](const pair<int, int>&a, const pair<int, int>&b){return a.second < b.second;});
  
  set<int> distancesCol;

  distancesCol.insert(1);
  distancesCol.insert(nbCols);
  distancesCol.insert(2 * nbCols);
  for(int iPointA = 0;iPointA < nbPoints;iPointA++) {
    for(int iPointB = 0;iPointB < nbPoints;iPointB++) {
      distancesCol.insert(abs(points[iPointA].second - points[iPointB].second));
      distancesCol.insert(abs(nbCols - points[iPointA].second + points[iPointB].second));
    }
  }

  precalcule_ecarts();

  long long minTotal = 2000 * 1000 * 1000;
  for(int dist : distancesCol) {
    if(dist >= 1) {
      minTotal = min(minTotal, traite(dist));
    }
  }

  cout << minTotal << endl;

  return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 15 / 15
• Subtask 4: 30 / 30
• Subtask 5: 20 / 20
• Subtask 6: 0 / 20