oj.uz

Submission #91031

# Submission time Handle Problem Language Result Execution time Memory
91031 2018-12-25T16:43:37 Z doowey Wall (IOI14_wall) C++14
61 / 100
 653 ms 263168 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 * 3];
 
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){
  mini(node * 2, Tree[node].min_op);
  mini(node * 2 + 1, Tree[node].min_op);
  maxi(node * 2, Tree[node].max_op);
  maxi(node * 2 + 1, Tree[node].max_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 2 ms 420 KB Output is correct
2 Correct 3 ms 600 KB Output is correct
3 Correct 3 ms 656 KB Output is correct
4 Correct 7 ms 1144 KB Output is correct
5 Correct 6 ms 1292 KB Output is correct
6 Correct 6 ms 1396 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1396 KB Output is correct
2 Correct 145 ms 14800 KB Output is correct
3 Correct 175 ms 14800 KB Output is correct
4 Correct 599 ms 31168 KB Output is correct
5 Correct 298 ms 41876 KB Output is correct
6 Correct 285 ms 50472 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 50472 KB Output is correct
2 Correct 3 ms 50472 KB Output is correct
3 Correct 3 ms 50472 KB Output is correct
4 Correct 7 ms 50472 KB Output is correct
5 Correct 6 ms 50472 KB Output is correct
6 Correct 6 ms 50472 KB Output is correct
7 Correct 2 ms 50472 KB Output is correct
8 Correct 148 ms 53072 KB Output is correct
9 Correct 174 ms 53072 KB Output is correct
10 Correct 518 ms 69652 KB Output is correct
11 Correct 298 ms 80232 KB Output is correct
12 Correct 288 ms 88936 KB Output is correct
13 Correct 2 ms 88936 KB Output is correct
14 Correct 151 ms 91156 KB Output is correct
15 Correct 30 ms 91156 KB Output is correct
16 Correct 509 ms 104600 KB Output is correct
17 Correct 290 ms 113724 KB Output is correct
18 Correct 286 ms 122688 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 122688 KB Output is correct
2 Correct 3 ms 122688 KB Output is correct
3 Correct 3 ms 122688 KB Output is correct
4 Correct 6 ms 122688 KB Output is correct
5 Correct 6 ms 122688 KB Output is correct
6 Correct 6 ms 122688 KB Output is correct
7 Correct 2 ms 122688 KB Output is correct
8 Correct 150 ms 125668 KB Output is correct
9 Correct 176 ms 125668 KB Output is correct
10 Correct 505 ms 142116 KB Output is correct
11 Correct 296 ms 152812 KB Output is correct
12 Correct 288 ms 161380 KB Output is correct
13 Correct 2 ms 161380 KB Output is correct
14 Correct 150 ms 163804 KB Output is correct
15 Correct 29 ms 163804 KB Output is correct
16 Correct 501 ms 177172 KB Output is correct
17 Correct 289 ms 186172 KB Output is correct
18 Correct 291 ms 195212 KB Output is correct
19 Correct 653 ms 259452 KB Output is correct
20 Runtime error 653 ms 263168 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 -