oj.uz

Submission #462506

# Submission time Handle Problem Language Result Execution time Memory
462506 2021-08-10T16:28:19 Z Mounir Snowball (JOI21_ho_t2) C++14
0 / 100
 15 ms 412 KB 
#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;
pii inters[N];
int nBoules, nJours;

int getInstant(int posInter, int posBoule){
      int delta = -(posBoule - posInter);
      int gauche = 0, droite = nJours + 1;
      while (droite > gauche){
            int mid = (gauche + droite)/2;
            if (inters[mid].deb <= delta && inters[mid].fin > delta)
                  droite = mid;
            else
                  gauche = mid + 1;
      }
      return gauche;
}


signed main(){ 
      ios::sync_with_stdio(false);
      cin.tie(nullptr);
      cout.tie(nullptr);
 
      cin >> nBoules >> nJours;
      vector<int> boules(nBoules);
      for (int& boule : boules)
            cin >> boule;

      int posCur = 0;
      inters[0] = {0, -1};
      for (int iJour = 1; iJour <= nJours; ++iJour){
            int delta; cin >> delta;
            posCur += delta;
            inters[iJour] = {min(inters[iJour - 1].deb, posCur), max(inters[iJour - 1].fin, posCur)};
      }

    //  cout << getInstant(4, 3) << endl; 


//      cout << "inter " << inters[nJours].deb << " " << inters[nJours].fin << endl;

      vector<pii> couverts(nBoules);
      for (int iBoule = 0; iBoule < nBoules; ++iBoule){
            int gauche = boules[iBoule] + inters[nJours].deb, droite = boules[iBoule]; //Gauche

            while (droite > gauche){
                  int mid = floor((gauche + droite)/double(2));
              ///    cout << "dicho " << gauche << " " << droite << " " << mid << endl;

                  if (getInstant(mid, boules[iBoule]) <= nJours && (iBoule == 0 || getInstant(mid, boules[iBoule]) < getInstant(mid, boules[iBoule - 1])))
                        droite = mid;
                  else
                        gauche = mid + 1;
            }

            couverts[iBoule].deb = gauche;
            gauche = boules[iBoule], droite = boules[iBoule] + inters[nJours].fin;
            while (droite > gauche){
                  int mid =  floor((gauche + droite)/double(2)) + 1;
                //  cout << "dicho " << gauche << " " << droite << " " << mid << endl;
                  //cout << getInstant(mid, boules[iBoule]) << endl << endl;

                  if (getInstant(mid, boules[iBoule]) <= nJours && (iBoule == nBoules - 1 || getInstant(mid, boules[iBoule]) < getInstant(mid, boules[iBoule + 1])))
                        gauche = mid;
                  else
                        droite = mid - 1;
            }
            couverts[iBoule].fin = gauche;
            cout << couverts[iBoule].fin - couverts[iBoule].deb + 1 << endl;
      }
      return 0;
 
}

Subtask #1
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 15 ms 400 KB Output is correct
5 Correct 14 ms 412 KB Output is correct
6 Correct 13 ms 332 KB Output is correct
7 Incorrect 11 ms 404 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 15 ms 400 KB Output is correct
5 Correct 14 ms 412 KB Output is correct
6 Correct 13 ms 332 KB Output is correct
7 Incorrect 11 ms 404 KB Output isn't correct
8 Halted 0 ms 0 KB -