Submission #109466

#	Time	Username	Problem	Language	Result	Execution time	Memory
109466		Arturgo	Examination (JOI19_examination)	C++14	100 / 100	1182 ms	30248 KiB

examination

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;

int nbEleves, nbReqs;

struct Req {
  int lig, col, id;
  bool type;
  Req(int _lig = 0, int _col = 0, int _id = 0, bool _type = false) {
    lig = _lig;
    col = _col;
    id = _id;
    type = _type;
  }
};

bool operator < (const Req& a, const Req &b) {
  if(a.col == b.col)
    return a.type < b.type;
  return a.col > b.col;
}

vector<int> arbre;

void ajoute(int pos, int val) {
  pos += (1 << 18);
  while(pos != 0) {
    arbre[pos] += val;
    pos /= 2;
  }
}

int nbInter(int deb, int fin) {
  deb += (1 << 18);
  fin += (1 << 18);

  int somme = 0;
  while(deb < fin) {
    if(deb % 2 == 1) {
      somme += arbre[deb];
      deb++;
    }
    if(fin % 2 == 1) {
      fin--;
      somme += arbre[fin];
    }
    deb /= 2;
    fin /= 2;
  }

  return somme;
}
      

vector<int> nombreHautDroite(vector<Req> reqs) {
  sort(reqs.begin(), reqs.end());

  map<int, int> indexes;
  for(Req& req : reqs) {
    indexes[req.lig] = 0;
  }

  int id = 0;
  for(auto it = indexes.begin();it != indexes.end();it++) {
    it->second = id;
    id++;
  }

  for(Req& req : reqs) {
    req.lig = indexes[req.lig];
  }

  vector<int> reponses(nbReqs, 0);
  arbre = vector<int>((1 << 19), 0);

  for(Req& req : reqs) {
    if(req.type) {
      reponses[req.id] = nbInter(req.lig, (1 << 18) - 1);
    }
    else {
      ajoute(req.lig, 1);
    }
  }

  return reponses;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin >> nbEleves >> nbReqs;

  vector<Req> ajoutes, enleves, quarts;
  for(int iEleve = 0;iEleve < nbEleves;iEleve++) {
    int maths, info;
    cin >> maths >> info;
    ajoutes.push_back(Req(maths, maths + info, iEleve, false));
    enleves.push_back(Req(-info, maths + info, iEleve, false));
    quarts.push_back(Req(maths, info, iEleve, false));
  }

  for(int iReq = 0;iReq < nbReqs;iReq++) {
    int maths, info, total;
    cin >> maths >> info >> total;
    if(maths + info < total) {
      ajoutes.push_back(Req(maths, total, iReq, true));
      enleves.push_back(Req(-info + 1, total, iReq, true));
    }
    else {
      quarts.push_back(Req(maths, info, iReq, true));
    }
  }

  vector<int> positifs = nombreHautDroite(ajoutes);
  vector<int> negatifs = nombreHautDroite(enleves);
  vector<int> autres = nombreHautDroite(quarts);

  for(int iReq = 0;iReq < nbReqs;iReq++) {
    cout << autres[iReq] + positifs[iReq] - negatifs[iReq] << endl;
  }
  return 0;
}

• Subtask 1: 2 / 2
• Subtask 2: 20 / 20
• Subtask 3: 21 / 21
• Subtask 4: 57 / 57