oj.uz

Submission #1103976

# Submission time Handle Problem Language Result Execution time Memory
1103976 2024-10-22T13:52:42 Z vjudge1 Wall (IOI14_wall) C++17
100 / 100
 1141 ms 130632 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 = min(seg[i].val, seg[i].lzmn);
  seg[i].val = max(seg[i].val, seg[i].lzmx);

  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].lzmn = max(seg[2*i].lzmn, mx);
    seg[2*i+1].lzmn = max(seg[2*i+1].lzmn, mx);

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

  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:61:9: warning: unused variable 'mn' [-Wunused-variable]
   61 |     int mn, mx;
      |         ^~
wall.cpp:61:13: warning: unused variable 'mx' [-Wunused-variable]
   61 |     int mn, mx;
      |             ^~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 94288 KB Output is correct
2 Correct 16 ms 94456 KB Output is correct
3 Correct 20 ms 94436 KB Output is correct
4 Correct 21 ms 94544 KB Output is correct
5 Correct 19 ms 94544 KB Output is correct
6 Correct 18 ms 94544 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 94288 KB Output is correct
2 Correct 109 ms 101964 KB Output is correct
3 Correct 179 ms 101116 KB Output is correct
4 Correct 497 ms 110456 KB Output is correct
5 Correct 288 ms 113224 KB Output is correct
6 Correct 303 ms 111660 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 94288 KB Output is correct
2 Correct 14 ms 94288 KB Output is correct
3 Correct 25 ms 94372 KB Output is correct
4 Correct 24 ms 94584 KB Output is correct
5 Correct 23 ms 94544 KB Output is correct
6 Correct 19 ms 94544 KB Output is correct
7 Correct 19 ms 94196 KB Output is correct
8 Correct 103 ms 102072 KB Output is correct
9 Correct 169 ms 101284 KB Output is correct
10 Correct 498 ms 102716 KB Output is correct
11 Correct 311 ms 103240 KB Output is correct
12 Correct 290 ms 111820 KB Output is correct
13 Correct 23 ms 94288 KB Output is correct
14 Correct 114 ms 107848 KB Output is correct
15 Correct 42 ms 95560 KB Output is correct
16 Correct 509 ms 112456 KB Output is correct
17 Correct 313 ms 111944 KB Output is correct
18 Correct 303 ms 111956 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 94288 KB Output is correct
2 Correct 16 ms 94388 KB Output is correct
3 Correct 16 ms 94288 KB Output is correct
4 Correct 21 ms 94712 KB Output is correct
5 Correct 19 ms 94564 KB Output is correct
6 Correct 20 ms 94288 KB Output is correct
7 Correct 15 ms 94288 KB Output is correct
8 Correct 105 ms 101972 KB Output is correct
9 Correct 204 ms 101688 KB Output is correct
10 Correct 517 ms 110408 KB Output is correct
11 Correct 314 ms 103240 KB Output is correct
12 Correct 304 ms 111692 KB Output is correct
13 Correct 15 ms 94372 KB Output is correct
14 Correct 157 ms 107848 KB Output is correct
15 Correct 47 ms 95560 KB Output is correct
16 Correct 565 ms 112456 KB Output is correct
17 Correct 355 ms 111944 KB Output is correct
18 Correct 333 ms 111988 KB Output is correct
19 Correct 1052 ms 130580 KB Output is correct
20 Correct 1095 ms 128252 KB Output is correct
21 Correct 1120 ms 130624 KB Output is correct
22 Correct 1141 ms 128072 KB Output is correct
23 Correct 1113 ms 127756 KB Output is correct
24 Correct 1076 ms 128044 KB Output is correct
25 Correct 1081 ms 128016 KB Output is correct
26 Correct 1046 ms 130524 KB Output is correct
27 Correct 1128 ms 130632 KB Output is correct
28 Correct 1076 ms 128072 KB Output is correct
29 Correct 1101 ms 128252 KB Output is correct
30 Correct 1035 ms 128072 KB Output is correct