oj.uz

Submission #959631

# Submission time Handle Problem Language Result Execution time Memory
959631 2024-04-08T14:39:55 Z vjudge1 Wall (IOI14_wall) C++17
0 / 100
 115 ms 18008 KB 
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;

const int N = 2e6+6, inf = INT_MAX;

struct node {
  int mx, mn;
};

int n, lazMx[N*4], lazMn[N*4];
node seg[N*4];

void build(int p=1, int l=0, int r=n-1) {
  lazMx[p] = -inf;
  lazMn[p] = inf;
  if (l == r) {
    seg[p].mx = 0;
    seg[p].mn = 0;
    return;
  }
  int mid = (l+r) >> 1;
  seg[p].mx = seg[p].mn = 0;
}

void pushDown(int p) {
  for (int h : {p*2, p*2+1}) {
    if (lazMx[p] != -inf) {
      seg[h].mx = max(seg[h].mx, lazMx[p]);
      seg[h].mn = max(seg[h].mn, lazMx[p]);
      lazMx[h] = max(lazMx[h], lazMx[p]);
      if (lazMn[h] <= lazMx[p]) lazMn[h] = inf;
    }

    if (lazMn[p] != inf) {
      seg[h].mx = min(seg[h].mx, lazMn[p]);
      seg[h].mn = min(seg[h].mn, lazMn[p]);
      lazMn[h] = min(lazMn[h], lazMn[p]);
      if (lazMx[h] >= lazMn[p]) lazMx[h] = -inf;
    }
  }
  lazMx[p] = -inf;
  lazMn[p] = inf;
}

void updateMx(int a, int b, int c, int p=1, int l=0, int r=n-1) {
  if (seg[p].mn >= c) return;
  else if (a <= l && r <= b) {
    seg[p].mx = max(seg[p].mx, c);
    seg[p].mn = max(seg[p].mn, c); 
    lazMx[p] = max(lazMx[p], c);
    if (lazMn[p] <= lazMx[p]) lazMn[p] = inf;
    if (l == r) return;
  }
  pushDown(p);
  int mid = (l+r) >> 1;
  if (a <= mid) updateMx(a, b, c, p*2, l, mid);
  if (mid+1 <= b) updateMx(a, b, c, p*2+1, mid+1, r);
  seg[p].mx = max(seg[p*2].mx, seg[p*2+1].mx);
  seg[p].mn = min(seg[p*2].mn, seg[p*2+1].mn);
}

void updateMn(int a, int b, int c, int p=1, int l=0, int r=n-1) {
  if (seg[p].mx <= c) return;
  else if (a <= l && r <= b) {
    seg[p].mx = min(seg[p].mx, c);
    seg[p].mn = min(seg[p].mn, c); 
    lazMn[p] = min(lazMn[p], c);
    if (lazMx[p] >= lazMn[p]) lazMx[p] = -inf;
    if (l == r) return;
  }
  pushDown(p);
  int mid = (l+r) >> 1;
  if (a <= mid) updateMn(a, b, c, p*2, l, mid);
  if (mid+1 <= b) updateMn(a, b, c, p*2+1, mid+1, r);
  seg[p].mx = max(seg[p*2].mx, seg[p*2+1].mx);
  seg[p].mn = min(seg[p*2].mn, seg[p*2+1].mn);
}

int query(int a, int p=1, int l=0, int r=n-1) {
  if (l == r) {
    return seg[p].mx;
  }
  pushDown(p);
  int mid = (l+r) >> 1;
  if (a <= mid) return query(a, p*2, l, mid);
  else return query(a, p*2+1, mid+1, r);
}

void buildWall(int NN, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  n = NN;

  build();
  for (int i = 0; i < k; i++) {
    if (op[i] == 1) updateMx(left[i], right[i], height[i]);
    else updateMn(left[i], right[i], height[i]);
  }

  for (int i = 0; i < n; i++) {
    finalHeight[i] = query(i);
  }
}

Compilation message

wall.cpp: In function 'void build(int, int, int)':
wall.cpp:22:7: warning: unused variable 'mid' [-Wunused-variable]
   22 |   int mid = (l+r) >> 1;
      |       ^~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 3 ms 4440 KB Output is correct
3 Incorrect 2 ms 4444 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 115 ms 18008 KB Output is correct
3 Incorrect 58 ms 10836 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 2 ms 4680 KB Output is correct
3 Incorrect 2 ms 4444 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 2 ms 4496 KB Output is correct
3 Incorrect 3 ms 4444 KB Output isn't correct
4 Halted 0 ms 0 KB -