oj.uz

Submission #70863

# Submission time Handle Problem Language Result Execution time Memory
70863 2018-08-23T14:32:41 Z doowey Wall (IOI14_wall) C++14
61 / 100
 1226 ms 262700 KB 
#include "wall.h"
#include <bits/stdc++.h>

using namespace std;

const int N = 2000101;

struct Node{
  int min_op;
  int max_op;
};

Node Tree[N * 4];

void init(int node, int cl, int cr){
  Tree[node].min_op = (int)1e9 + 9;
  Tree[node].max_op = 0;
  if(cl == cr){
    return;
  }
  int md = (cl + cr)/2;
  init(node * 2, cl, md);
  init(node * 2 + 1, md + 1, cr);

}

void maxi(int node, int x){ // apply max(node)
  Tree[node].max_op = max(Tree[node].max_op, x);
  Tree[node].min_op = max(Tree[node].min_op, Tree[node].max_op);
}

void mini(int node, int x){ // apply min(node)
  Tree[node].min_op = min(Tree[node].min_op, x);
  Tree[node].max_op = min(Tree[node].max_op, Tree[node].min_op);
}

void push(int node, int tl, int tr){
  maxi(node * 2, Tree[node].max_op);
  maxi(node * 2 + 1, Tree[node].max_op);
  mini(node * 2, Tree[node].min_op);
  mini(node * 2 + 1, Tree[node].min_op);
  Tree[node].max_op = 0;
  Tree[node].min_op = (int)1e9 + 9;
}

void update(int node, int cl, int cr, int tl, int tr, int x, int op){
  if(cr < tl)
    return;
  if(cl > tr)
    return;
  if(cl >= tl and cr <= tr){
    if(op == 1)
      maxi(node, x);
    else
      mini(node, x);
    return;
  }
  push(node, cl, cr);
  int md = (cl + cr)/2;
  update(node*2, cl, md, tl, tr, x, op);
  update(node*2+1, md + 1, cr, tl, tr, x, op);
}

int fin[N];

void ff(int node, int cl, int cr){
  if(cl == cr){
    fin[cl] = Tree[node].max_op;
    return;
  }
  push(node, cl, cr);
  int md = (cl + cr)/2;
  ff(node * 2, cl, md);
  ff(node * 2 + 1, md + 1, cr);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  init(1, 0, n-1);
  for(int i = 0;i < k;i ++ ){
    update(1, 0, n - 1, left[i], right[i], height[i], op[i]);
  }
  ff(1, 0, n - 1);
  for(int i = 0;i < n;i ++ )
    finalHeight[i] = fin[i];
  return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 248 KB Output is correct
2 Correct 6 ms 624 KB Output is correct
3 Correct 5 ms 644 KB Output is correct
4 Correct 9 ms 1184 KB Output is correct
5 Correct 10 ms 1272 KB Output is correct
6 Correct 10 ms 1540 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1540 KB Output is correct
2 Correct 215 ms 14820 KB Output is correct
3 Correct 300 ms 14820 KB Output is correct
4 Correct 900 ms 31352 KB Output is correct
5 Correct 498 ms 41920 KB Output is correct
6 Correct 427 ms 50564 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 50564 KB Output is correct
2 Correct 5 ms 50564 KB Output is correct
3 Correct 5 ms 50564 KB Output is correct
4 Correct 13 ms 50564 KB Output is correct
5 Correct 8 ms 50564 KB Output is correct
6 Correct 8 ms 50564 KB Output is correct
7 Correct 2 ms 50564 KB Output is correct
8 Correct 190 ms 53336 KB Output is correct
9 Correct 235 ms 53336 KB Output is correct
10 Correct 724 ms 69872 KB Output is correct
11 Correct 496 ms 80472 KB Output is correct
12 Correct 374 ms 89080 KB Output is correct
13 Correct 4 ms 89080 KB Output is correct
14 Correct 278 ms 91332 KB Output is correct
15 Correct 41 ms 91332 KB Output is correct
16 Correct 725 ms 104776 KB Output is correct
17 Correct 440 ms 113900 KB Output is correct
18 Correct 391 ms 122944 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 122944 KB Output is correct
2 Correct 7 ms 122944 KB Output is correct
3 Correct 5 ms 122944 KB Output is correct
4 Correct 11 ms 122944 KB Output is correct
5 Correct 10 ms 122944 KB Output is correct
6 Correct 8 ms 122944 KB Output is correct
7 Correct 3 ms 122944 KB Output is correct
8 Correct 224 ms 125892 KB Output is correct
9 Correct 270 ms 125892 KB Output is correct
10 Correct 794 ms 142216 KB Output is correct
11 Correct 465 ms 152744 KB Output is correct
12 Correct 450 ms 160924 KB Output is correct
13 Correct 3 ms 160924 KB Output is correct
14 Correct 280 ms 163308 KB Output is correct
15 Correct 51 ms 163308 KB Output is correct
16 Correct 786 ms 176488 KB Output is correct
17 Correct 495 ms 185060 KB Output is correct
18 Correct 444 ms 193776 KB Output is correct
19 Correct 1226 ms 256068 KB Output is correct
20 Runtime error 1144 ms 262700 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
21 Halted 0 ms 0 KB -