oj.uz

Submission #1103968

# Submission time Handle Problem Language Result Execution time Memory
1103968 2024-10-22T13:40:07 Z Naxocist Wall (IOI14_wall) C++17
24 / 100
 419 ms 103240 KB 
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;

#define INF 2e9
const int N = 2e6 + 3;
struct node {
  int val, lzmn, lzmx;
  node(): val(0), lzmn(INF), lzmx(-INF) {}
} seg[4*N];

int n;

void push(int i, int l, int r) {
  seg[i].val = max(seg[i].val, seg[i].lzmx);
  seg[i].val = min(seg[i].val, seg[i].lzmn);

  int mn = seg[i].lzmn, mx = seg[i].lzmx;

  if(l != r) {
    seg[2*i].lzmn = min(seg[2*i].lzmn, mn);
    seg[2*i+1].lzmn = min(seg[2*i+1].lzmn, mn);

    seg[2*i].lzmx = max(seg[2*i].lzmx, mx);
    seg[2*i+1].lzmx = max(seg[2*i+1].lzmx, mx);
  }

  seg[i].lzmn = INF, seg[i].lzmx = -INF;
}

void upd(int a, int b, int mn, int mx, int i = 1, int l = 1, int r = n) {
  push(i,l,r);
  if(a <= l and r <= b) {
    seg[i].lzmx = mx;
    seg[i].lzmn = mn;
    push(i,l,r);
    return ;
  }
  if(r < a or l > b) return ;
  int md = l + (r-l)/2;
  upd(a,b,mn,mx,2*i,l,md); upd(a,b,mn,mx,2*i+1,md+1,r);
}

int qry(int p, int i = 1, int l = 1, int r = n) {
  push(i,l,r);
  if(l == r) return seg[i].val;
  int md = l + (r-l)/2;
  if(p <= md) return qry(p,2*i,l,md);
  return qry(p,2*i+1,md+1,r);
}

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

  for(int i=0; i<k; ++i) {
    int l = left[i], r = right[i], o = op[i], h = height[i]; l++, r++;
    int mn, mx;
    if(o == 1) upd(l,r,INF,h); // add
    else upd(l,r,h,-INF); // rem
  }

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

Compilation message

wall.cpp: In function 'void buildWall(int, int, int*, int*, int*, int*, int*)':
wall.cpp:57:9: warning: unused variable 'mn' [-Wunused-variable]
   57 |     int mn, mx;
      |         ^~
wall.cpp:57:13: warning: unused variable 'mx' [-Wunused-variable]
   57 |     int mn, mx;
      |             ^~

Subtask #1
0 / 8.0

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

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 94288 KB Output is correct
2 Correct 115 ms 101968 KB Output is correct
3 Correct 162 ms 97696 KB Output is correct
4 Correct 419 ms 102724 KB Output is correct
5 Correct 242 ms 103232 KB Output is correct
6 Correct 261 ms 103240 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 94188 KB Output is correct
2 Correct 17 ms 94288 KB Output is correct
3 Incorrect 16 ms 94288 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

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