oj.uz

Submission #959634

# Submission time Handle Problem Language Result Execution time Memory
959634 2024-04-08T14:41:39 Z vjudge1 Wall (IOI14_wall) C++17
32 / 100
 3000 ms 21472 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
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 77 ms 892 KB Output is correct
5 Correct 144 ms 888 KB Output is correct
6 Correct 140 ms 856 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 110 ms 11156 KB Output is correct
3 Correct 60 ms 5712 KB Output is correct
4 Correct 161 ms 20628 KB Output is correct
5 Correct 142 ms 21408 KB Output is correct
6 Correct 151 ms 19932 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 352 KB Output is correct
2 Correct 2 ms 352 KB Output is correct
3 Correct 2 ms 352 KB Output is correct
4 Correct 75 ms 900 KB Output is correct
5 Correct 139 ms 1104 KB Output is correct
6 Correct 139 ms 880 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 114 ms 14108 KB Output is correct
9 Correct 59 ms 7920 KB Output is correct
10 Correct 159 ms 20380 KB Output is correct
11 Correct 143 ms 21472 KB Output is correct
12 Correct 152 ms 19868 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 114 ms 13956 KB Output is correct
15 Correct 793 ms 1996 KB Output is correct
16 Execution timed out 3053 ms 19680 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 548 KB Output is correct
2 Correct 2 ms 344 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 89 ms 860 KB Output is correct
5 Correct 165 ms 876 KB Output is correct
6 Correct 141 ms 884 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 112 ms 14060 KB Output is correct
9 Correct 60 ms 8048 KB Output is correct
10 Correct 159 ms 20436 KB Output is correct
11 Correct 163 ms 21360 KB Output is correct
12 Correct 160 ms 19796 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 114 ms 13896 KB Output is correct
15 Correct 855 ms 2000 KB Output is correct
16 Execution timed out 3086 ms 19916 KB Time limit exceeded
17 Halted 0 ms 0 KB -