| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 138207 |
2019-07-29T15:16:36 Z |
Arturgo |
Wall (IOI14_wall) |
C++14 |
|
939 ms |
61560 KB |
#include "wall.h"
#include <iostream>
using namespace std;
const int INFINI = 1000 * 1000 * 1000;
pair<int, int> bornes[(1 << 22)];
void push(pair<int, int>& init, pair<int, int> modif) {
init.first = max(init.first, modif.first);
init.second = max(init.second, init.first);
init.second = min(init.second, modif.second);
init.first = min(init.second, init.first);
}
void update(int noeud) {
if(noeud >= (1 << 21)) {
return;
}
push(bornes[2 * noeud], bornes[noeud]);
push(bornes[2 * noeud + 1], bornes[noeud]);
bornes[noeud] = {0, INFINI};
}
void update(int deb, int fin, pair<int, int> borne, int n = 1, int d = 0, int f = (1 << 21)) {
update(n);
if(deb >= f || d >= fin)
return;
if(deb <= d && f <= fin) {
push(bornes[n], borne);
update(n);
return;
}
int m = (d + f) / 2;
update(deb, fin, borne, 2 * n, d, m);
update(deb, fin, borne, 2 * n + 1, m, f);
}
void buildWall(int nbSlots, int nbReqs, int op[], int left[], int right[], int height[], int finalHeight[]) {
for(int iReq = 0;iReq < nbReqs;iReq++) {
if(op[iReq] == 1) {
update(left[iReq], right[iReq] + 1, {height[iReq], INFINI});
}
else {
update(left[iReq], right[iReq] + 1, {0, height[iReq]});
}
}
for(int iSommet = 1;iSommet < (1 << 21);iSommet++)
update(iSommet);
for(int iSommet = (1 << 21);iSommet < (1 << 21) + nbSlots;iSommet++) {
finalHeight[iSommet - (1 << 21)] = bornes[iSommet].first;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
54 ms |
33144 KB |
Output is correct |
| 2 |
Correct |
57 ms |
33400 KB |
Output is correct |
| 3 |
Correct |
55 ms |
33144 KB |
Output is correct |
| 4 |
Correct |
61 ms |
33272 KB |
Output is correct |
| 5 |
Correct |
59 ms |
33272 KB |
Output is correct |
| 6 |
Correct |
59 ms |
33352 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
53 ms |
33144 KB |
Output is correct |
| 2 |
Correct |
487 ms |
41128 KB |
Output is correct |
| 3 |
Correct |
325 ms |
36600 KB |
Output is correct |
| 4 |
Correct |
767 ms |
41540 KB |
Output is correct |
| 5 |
Correct |
482 ms |
42144 KB |
Output is correct |
| 6 |
Correct |
471 ms |
42128 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
54 ms |
33272 KB |
Output is correct |
| 2 |
Correct |
57 ms |
33272 KB |
Output is correct |
| 3 |
Correct |
55 ms |
33144 KB |
Output is correct |
| 4 |
Correct |
62 ms |
33260 KB |
Output is correct |
| 5 |
Correct |
61 ms |
33400 KB |
Output is correct |
| 6 |
Correct |
59 ms |
33372 KB |
Output is correct |
| 7 |
Correct |
53 ms |
33144 KB |
Output is correct |
| 8 |
Correct |
492 ms |
41040 KB |
Output is correct |
| 9 |
Correct |
316 ms |
36600 KB |
Output is correct |
| 10 |
Correct |
760 ms |
41620 KB |
Output is correct |
| 11 |
Correct |
483 ms |
42308 KB |
Output is correct |
| 12 |
Correct |
474 ms |
42232 KB |
Output is correct |
| 13 |
Correct |
54 ms |
33144 KB |
Output is correct |
| 14 |
Correct |
490 ms |
41056 KB |
Output is correct |
| 15 |
Correct |
97 ms |
33912 KB |
Output is correct |
| 16 |
Correct |
860 ms |
41856 KB |
Output is correct |
| 17 |
Correct |
495 ms |
41820 KB |
Output is correct |
| 18 |
Correct |
485 ms |
41908 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
53 ms |
33144 KB |
Output is correct |
| 2 |
Correct |
59 ms |
33272 KB |
Output is correct |
| 3 |
Correct |
54 ms |
33144 KB |
Output is correct |
| 4 |
Correct |
60 ms |
33400 KB |
Output is correct |
| 5 |
Correct |
61 ms |
33244 KB |
Output is correct |
| 6 |
Correct |
59 ms |
33272 KB |
Output is correct |
| 7 |
Correct |
53 ms |
33144 KB |
Output is correct |
| 8 |
Correct |
498 ms |
41104 KB |
Output is correct |
| 9 |
Correct |
319 ms |
36580 KB |
Output is correct |
| 10 |
Correct |
769 ms |
41700 KB |
Output is correct |
| 11 |
Correct |
482 ms |
42140 KB |
Output is correct |
| 12 |
Correct |
474 ms |
42104 KB |
Output is correct |
| 13 |
Correct |
59 ms |
33148 KB |
Output is correct |
| 14 |
Correct |
495 ms |
41084 KB |
Output is correct |
| 15 |
Correct |
98 ms |
33784 KB |
Output is correct |
| 16 |
Correct |
926 ms |
41988 KB |
Output is correct |
| 17 |
Correct |
482 ms |
41976 KB |
Output is correct |
| 18 |
Correct |
484 ms |
41864 KB |
Output is correct |
| 19 |
Correct |
921 ms |
59156 KB |
Output is correct |
| 20 |
Correct |
905 ms |
59220 KB |
Output is correct |
| 21 |
Correct |
909 ms |
61560 KB |
Output is correct |
| 22 |
Correct |
908 ms |
58868 KB |
Output is correct |
| 23 |
Correct |
907 ms |
58916 KB |
Output is correct |
| 24 |
Correct |
939 ms |
59012 KB |
Output is correct |
| 25 |
Correct |
906 ms |
58580 KB |
Output is correct |
| 26 |
Correct |
929 ms |
61376 KB |
Output is correct |
| 27 |
Correct |
911 ms |
61172 KB |
Output is correct |
| 28 |
Correct |
907 ms |
58560 KB |
Output is correct |
| 29 |
Correct |
920 ms |
58380 KB |
Output is correct |
| 30 |
Correct |
909 ms |
58488 KB |
Output is correct |
