Submission #462527

#	Time	Username	Problem	Language	Result	Execution time	Memory
462527		Mounir	Snowball (JOI21_ho_t2)	C++14	33 / 100	2576 ms	6628 KiB

Main

#include <bits/stdc++.h>
#define sz(x) (int)x.size()
#define chmin(x, v) x = min(x, v)
#define chmax(x, v) x = max(x, v)
#define all(x) x.begin(), x.end()
#define pb push_back
#define pii pair<int, int>
#define deb first
#define fin second
#define int long long
using namespace std;
 
const int N = 5e5, OO = 1e18;
int debs[N], fins[N];
int nBoules, nJours;
 
int getInstant(int posInter, int posBoule){
      int delta = -(posBoule - posInter);
      if (delta < 0)
            return lower_bound(debs, debs + nJours + 1, -delta) - debs;
      else
            return upper_bound(fins, fins + nJours + 1, delta) - fins;
}

int boules[N]; 
 
signed main(){ 
      ios::sync_with_stdio(false);
      cin.tie(nullptr);
      cout.tie(nullptr);
 
      cin >> nBoules >> nJours;
      for (int i = 0; i < nBoules; ++i)
            cin >> boules[i];

      int posCur = 0;
      debs[0] = 0; fins[0] = -1;
      for (int iJour = 1; iJour <= nJours; ++iJour){
            int delta; cin >> delta;
            posCur += delta;
            debs[iJour] = -min(-debs[iJour - 1], posCur);
            fins[iJour] = max(0ll, max(posCur, fins[iJour - 1]));
      }

    //  int debut[nBoules];
 
      for (int iBoule = 0; iBoule < nBoules; ++iBoule){
            int gauche = boules[iBoule] - debs[nJours], droite = boules[iBoule]; //Gauche
 
            while (droite > gauche){
                  int mid = floor((gauche + droite)/double(2));
                  int moment = getInstant(mid, boules[iBoule]);
 
                  if (moment <= nJours && (iBoule == 0 || moment < getInstant(mid, boules[iBoule - 1])))
                        droite = mid;
                  else
                        gauche = mid + 1;
            }

           // debut[iBoule] = ga
 
            int deb = gauche;
            gauche = boules[iBoule] - 1, droite = boules[iBoule] + fins[nJours];
            while (droite > gauche){
                  int mid =  floor((gauche + droite)/double(2)) + 1;
                //  cout << "dicho " << gauche << " " << droite << " " << mid << endl;
                  //cout << getInstant(mid, boules[iBoule]) << endl << endl;
                  int moment = getInstant(mid, boules[iBoule]);
 
                  if (moment <= nJours && (iBoule == nBoules - 1 || moment < getInstant(mid, boules[iBoule + 1])))
                        gauche = mid;
                  else
                        droite = mid - 1;
            }
            
            cout << gauche - deb + 1 << endl;
        //    cout << couverts[iBoule].deb << " " << couverts[iBoule].fin << endl;
      }
      return 0;
 
}

• Subtask 1: 33 / 33
• Subtask 2: 0 / 67