oj.uz

Submission #109466

# Submission time Handle Problem Language Result Execution time Memory
109466 2019-05-06T16:05:09 Z Arturgo Examination (JOI19_examination) C++14
100 / 100
 1182 ms 30248 KB 
#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.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4480 KB Output is correct
2 Correct 7 ms 4480 KB Output is correct
3 Correct 6 ms 4480 KB Output is correct
4 Correct 7 ms 4480 KB Output is correct
5 Correct 8 ms 4480 KB Output is correct
6 Correct 8 ms 4480 KB Output is correct
7 Correct 21 ms 4992 KB Output is correct
8 Correct 24 ms 5156 KB Output is correct
9 Correct 19 ms 5120 KB Output is correct
10 Correct 17 ms 5116 KB Output is correct
11 Correct 15 ms 4992 KB Output is correct
12 Correct 17 ms 4864 KB Output is correct
13 Correct 22 ms 5252 KB Output is correct
14 Correct 20 ms 5116 KB Output is correct
15 Correct 20 ms 5116 KB Output is correct
16 Correct 17 ms 5116 KB Output is correct
17 Correct 22 ms 5108 KB Output is correct
18 Correct 15 ms 4884 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 693 ms 19648 KB Output is correct
2 Correct 695 ms 19720 KB Output is correct
3 Correct 746 ms 19876 KB Output is correct
4 Correct 551 ms 19136 KB Output is correct
5 Correct 357 ms 18764 KB Output is correct
6 Correct 266 ms 16192 KB Output is correct
7 Correct 550 ms 19136 KB Output is correct
8 Correct 576 ms 19784 KB Output is correct
9 Correct 527 ms 19264 KB Output is correct
10 Correct 322 ms 18596 KB Output is correct
11 Correct 585 ms 19108 KB Output is correct
12 Correct 240 ms 16192 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 693 ms 19648 KB Output is correct
2 Correct 695 ms 19720 KB Output is correct
3 Correct 746 ms 19876 KB Output is correct
4 Correct 551 ms 19136 KB Output is correct
5 Correct 357 ms 18764 KB Output is correct
6 Correct 266 ms 16192 KB Output is correct
7 Correct 550 ms 19136 KB Output is correct
8 Correct 576 ms 19784 KB Output is correct
9 Correct 527 ms 19264 KB Output is correct
10 Correct 322 ms 18596 KB Output is correct
11 Correct 585 ms 19108 KB Output is correct
12 Correct 240 ms 16192 KB Output is correct
13 Correct 639 ms 20860 KB Output is correct
14 Correct 682 ms 19932 KB Output is correct
15 Correct 597 ms 19796 KB Output is correct
16 Correct 565 ms 19296 KB Output is correct
17 Correct 422 ms 18916 KB Output is correct
18 Correct 269 ms 16492 KB Output is correct
19 Correct 832 ms 20960 KB Output is correct
20 Correct 788 ms 20396 KB Output is correct
21 Correct 801 ms 19704 KB Output is correct
22 Correct 316 ms 18636 KB Output is correct
23 Correct 500 ms 19208 KB Output is correct
24 Correct 226 ms 16192 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4480 KB Output is correct
2 Correct 7 ms 4480 KB Output is correct
3 Correct 6 ms 4480 KB Output is correct
4 Correct 7 ms 4480 KB Output is correct
5 Correct 8 ms 4480 KB Output is correct
6 Correct 8 ms 4480 KB Output is correct
7 Correct 21 ms 4992 KB Output is correct
8 Correct 24 ms 5156 KB Output is correct
9 Correct 19 ms 5120 KB Output is correct
10 Correct 17 ms 5116 KB Output is correct
11 Correct 15 ms 4992 KB Output is correct
12 Correct 17 ms 4864 KB Output is correct
13 Correct 22 ms 5252 KB Output is correct
14 Correct 20 ms 5116 KB Output is correct
15 Correct 20 ms 5116 KB Output is correct
16 Correct 17 ms 5116 KB Output is correct
17 Correct 22 ms 5108 KB Output is correct
18 Correct 15 ms 4884 KB Output is correct
19 Correct 693 ms 19648 KB Output is correct
20 Correct 695 ms 19720 KB Output is correct
21 Correct 746 ms 19876 KB Output is correct
22 Correct 551 ms 19136 KB Output is correct
23 Correct 357 ms 18764 KB Output is correct
24 Correct 266 ms 16192 KB Output is correct
25 Correct 550 ms 19136 KB Output is correct
26 Correct 576 ms 19784 KB Output is correct
27 Correct 527 ms 19264 KB Output is correct
28 Correct 322 ms 18596 KB Output is correct
29 Correct 585 ms 19108 KB Output is correct
30 Correct 240 ms 16192 KB Output is correct
31 Correct 639 ms 20860 KB Output is correct
32 Correct 682 ms 19932 KB Output is correct
33 Correct 597 ms 19796 KB Output is correct
34 Correct 565 ms 19296 KB Output is correct
35 Correct 422 ms 18916 KB Output is correct
36 Correct 269 ms 16492 KB Output is correct
37 Correct 832 ms 20960 KB Output is correct
38 Correct 788 ms 20396 KB Output is correct
39 Correct 801 ms 19704 KB Output is correct
40 Correct 316 ms 18636 KB Output is correct
41 Correct 500 ms 19208 KB Output is correct
42 Correct 226 ms 16192 KB Output is correct
43 Correct 1182 ms 24316 KB Output is correct
44 Correct 1070 ms 29332 KB Output is correct
45 Correct 1024 ms 29120 KB Output is correct
46 Correct 712 ms 25964 KB Output is correct
47 Correct 448 ms 25560 KB Output is correct
48 Correct 279 ms 16924 KB Output is correct
49 Correct 1107 ms 28692 KB Output is correct
50 Correct 1149 ms 29040 KB Output is correct
51 Correct 1133 ms 30248 KB Output is correct
52 Correct 435 ms 25328 KB Output is correct
53 Correct 751 ms 27072 KB Output is correct