oj.uz

Submission #229488

# Submission time Handle Problem Language Result Execution time Memory
229488 2020-05-04T15:59:12 Z tushar_2658 Wall (IOI14_wall) C++14
0 / 100
 238 ms 71032 KB 
#include "wall.h"
#include "bits/stdc++.h"
using namespace std;

const int maxn = 2000005;
int N, K;
int lazy[maxn << 2][2], t[maxn << 2];

void push_down(int node, int b, int e){
  t[node] = min(lazy[node][0], t[node]);
  t[node] = max(lazy[node][1], t[node]);
  if(b != e){
    lazy[2*node][0] = min(lazy[2*node][0], lazy[node][0]);
    lazy[2*node + 1][0] = min(lazy[2*node + 1][0], lazy[node][0]);
    lazy[2*node][1] = max(lazy[2*node][1], lazy[node][1]);
    lazy[2*node + 1][1] = max(lazy[2*node + 1][1], lazy[node][1]);
  }
  lazy[node][0] = INT_MAX;
  lazy[node][1] = INT_MIN;
}

void upd(int node, int b, int e, int i, int j, int val, int id){
  push_down(node, b, e);
  if(i > e || j < b)return;
  if(b >= i && j >= e){
    if(id == 1){
      t[node] = max(t[node], val);
      if(b != e){
        lazy[2*node][1] = max(lazy[2*node][1], val);
        lazy[2*node + 1][1] = max(lazy[2*node + 1][1], val);
      }
    }else {
      t[node] = min(t[node], val);
      if(b != e){
        lazy[2*node][0] = min(lazy[2*node][0], val);
        lazy[2*node + 1][0] = min(lazy[2*node + 1][0], val);
      }
    }
    return;
  }
  int mid = (b + e) >> 1;
  upd(2*node, b, mid, i, j, val, id);
  upd(2*node + 1, mid + 1, e, i, j, val, id);
}

int query(int node, int b, int e, int i){
  if(b == e){
    push_down(node, b, e);
    return t[node];
  }else {
    push_down(node, b, e);
    int mid = (b + e) >> 1;
    if(i <= mid){
      return query(2*node, b, mid, i);
    }else {
      return query(2*node + 1, mid + 1, e, i);
    }
  }
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  N = n, K = k;
  for(int i = 0; i < (maxn << 2); ++i){
    lazy[i][0] = INT_MAX;
    lazy[i][1] = INT_MIN;
  }
  for(int i = 0; i < K; ++i){
    upd(1, 1, N, left[i] + 1, right[i] + 1, height[i], op[i]);
  }
  for(int i = 1; i <= N; ++i){
    finalHeight[i - 1] = query(1, 1, N, i);
  }

  return;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 62968 KB Output is correct
2 Correct 39 ms 63096 KB Output is correct
3 Incorrect 40 ms 62968 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 62976 KB Output is correct
2 Correct 206 ms 71032 KB Output is correct
3 Incorrect 238 ms 66808 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 62976 KB Output is correct
2 Correct 38 ms 63096 KB Output is correct
3 Incorrect 39 ms 62968 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 62968 KB Output is correct
2 Correct 39 ms 63096 KB Output is correct
3 Incorrect 40 ms 63096 KB Output isn't correct
4 Halted 0 ms 0 KB -