oj.uz

Submission #109465

# Submission time Handle Problem Language Result Execution time Memory
109465 2019-05-06T16:03:19 Z Arturgo Examination (JOI19_examination) C++14
43 / 100
 743 ms 36708 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 << 17);
  while(pos != 0) {
    arbre[pos] += val;
    pos /= 2;
  }
}

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

  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 << 18), 0);

  for(Req& req : reqs) {
    if(req.type) {
      reponses[req.id] = nbInter(req.lig, (1 << 17) - 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 4 ms 2432 KB Output is correct
2 Correct 4 ms 2432 KB Output is correct
3 Correct 4 ms 2432 KB Output is correct
4 Correct 4 ms 2432 KB Output is correct
5 Correct 5 ms 2432 KB Output is correct
6 Correct 5 ms 2432 KB Output is correct
7 Correct 21 ms 3200 KB Output is correct
8 Correct 16 ms 3200 KB Output is correct
9 Correct 22 ms 3200 KB Output is correct
10 Correct 16 ms 3072 KB Output is correct
11 Correct 16 ms 3200 KB Output is correct
12 Correct 15 ms 2940 KB Output is correct
13 Correct 18 ms 3196 KB Output is correct
14 Correct 17 ms 3068 KB Output is correct
15 Correct 17 ms 3196 KB Output is correct
16 Correct 14 ms 2944 KB Output is correct
17 Correct 17 ms 3072 KB Output is correct
18 Correct 13 ms 2816 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 679 ms 20176 KB Output is correct
2 Correct 559 ms 20100 KB Output is correct
3 Correct 554 ms 20172 KB Output is correct
4 Correct 491 ms 18880 KB Output is correct
5 Correct 280 ms 16432 KB Output is correct
6 Correct 250 ms 15168 KB Output is correct
7 Correct 621 ms 19264 KB Output is correct
8 Correct 607 ms 20168 KB Output is correct
9 Correct 644 ms 19264 KB Output is correct
10 Correct 315 ms 16320 KB Output is correct
11 Correct 574 ms 18880 KB Output is correct
12 Correct 210 ms 15040 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 679 ms 20176 KB Output is correct
2 Correct 559 ms 20100 KB Output is correct
3 Correct 554 ms 20172 KB Output is correct
4 Correct 491 ms 18880 KB Output is correct
5 Correct 280 ms 16432 KB Output is correct
6 Correct 250 ms 15168 KB Output is correct
7 Correct 621 ms 19264 KB Output is correct
8 Correct 607 ms 20168 KB Output is correct
9 Correct 644 ms 19264 KB Output is correct
10 Correct 315 ms 16320 KB Output is correct
11 Correct 574 ms 18880 KB Output is correct
12 Correct 210 ms 15040 KB Output is correct
13 Correct 671 ms 20872 KB Output is correct
14 Correct 686 ms 20672 KB Output is correct
15 Correct 743 ms 20160 KB Output is correct
16 Correct 513 ms 19328 KB Output is correct
17 Correct 391 ms 19044 KB Output is correct
18 Correct 265 ms 15364 KB Output is correct
19 Correct 732 ms 20824 KB Output is correct
20 Correct 580 ms 20532 KB Output is correct
21 Correct 676 ms 20488 KB Output is correct
22 Correct 271 ms 16212 KB Output is correct
23 Correct 557 ms 18780 KB Output is correct
24 Correct 255 ms 15164 KB Output is correct

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2432 KB Output is correct
2 Correct 4 ms 2432 KB Output is correct
3 Correct 4 ms 2432 KB Output is correct
4 Correct 4 ms 2432 KB Output is correct
5 Correct 5 ms 2432 KB Output is correct
6 Correct 5 ms 2432 KB Output is correct
7 Correct 21 ms 3200 KB Output is correct
8 Correct 16 ms 3200 KB Output is correct
9 Correct 22 ms 3200 KB Output is correct
10 Correct 16 ms 3072 KB Output is correct
11 Correct 16 ms 3200 KB Output is correct
12 Correct 15 ms 2940 KB Output is correct
13 Correct 18 ms 3196 KB Output is correct
14 Correct 17 ms 3068 KB Output is correct
15 Correct 17 ms 3196 KB Output is correct
16 Correct 14 ms 2944 KB Output is correct
17 Correct 17 ms 3072 KB Output is correct
18 Correct 13 ms 2816 KB Output is correct
19 Correct 679 ms 20176 KB Output is correct
20 Correct 559 ms 20100 KB Output is correct
21 Correct 554 ms 20172 KB Output is correct
22 Correct 491 ms 18880 KB Output is correct
23 Correct 280 ms 16432 KB Output is correct
24 Correct 250 ms 15168 KB Output is correct
25 Correct 621 ms 19264 KB Output is correct
26 Correct 607 ms 20168 KB Output is correct
27 Correct 644 ms 19264 KB Output is correct
28 Correct 315 ms 16320 KB Output is correct
29 Correct 574 ms 18880 KB Output is correct
30 Correct 210 ms 15040 KB Output is correct
31 Correct 671 ms 20872 KB Output is correct
32 Correct 686 ms 20672 KB Output is correct
33 Correct 743 ms 20160 KB Output is correct
34 Correct 513 ms 19328 KB Output is correct
35 Correct 391 ms 19044 KB Output is correct
36 Correct 265 ms 15364 KB Output is correct
37 Correct 732 ms 20824 KB Output is correct
38 Correct 580 ms 20532 KB Output is correct
39 Correct 676 ms 20488 KB Output is correct
40 Correct 271 ms 16212 KB Output is correct
41 Correct 557 ms 18780 KB Output is correct
42 Correct 255 ms 15164 KB Output is correct
43 Runtime error 435 ms 36708 KB Execution killed with signal 11 (could be triggered by violating memory limits)
44 Halted 0 ms 0 KB -