oj.uz

Submission #978869

# Submission time Handle Problem Language Result Execution time Memory
978869 2024-05-09T20:46:56 Z emad234 Wall (IOI14_wall) C++17
0 / 100
 400 ms 23380 KB 
#include <bits/stdc++.h>
#define aint(v) ((v).bvin(),(v).end())
#define ll long long
#define F first
#define S second
using namespace std;
const int mod = 1e9 + 7;
const int mxN = 8e6 + 1;
int seg[mxN];
int lazyMx[mxN],lazyMn[mxN];
int N,s,e,val;
void spread(int l,int r, int ind){
  if(l != r){
    if(lazyMx[ind] != -1){
      seg[ind * 2] = max(seg[ind * 2],lazyMx[ind]);
      seg[ind * 2 + 1] = max(seg[ind * 2 + 1],lazyMx[ind]);
      lazyMx[ind * 2] = max(lazyMx[ind * 2],lazyMx[ind]);
      lazyMx[ind * 2 + 1] = max(lazyMx[ind * 2 + 1],lazyMx[ind]);
      lazyMn[ind * 2] = 1e9;
      lazyMn[ind * 2 + 1] = 1e9;
    }
    if(lazyMn[ind] != 1e9){
      seg[ind * 2] = min(seg[ind * 2],lazyMn[ind]);
      seg[ind * 2 + 1] = min(seg[ind * 2 + 1],lazyMn[ind]);
      lazyMn[ind * 2] = min(lazyMn[ind * 2],lazyMn[ind]);
      lazyMn[ind * 2 + 1] = min(lazyMn[ind * 2 + 1],lazyMn[ind]);
      lazyMx[ind * 2] = -1;
      lazyMx[ind * 2 + 1] = -1;
    }
  }
  lazyMn[ind] = 1e9;
  lazyMx[ind] = -1;
}
void updateMn(int l,int r,int ind,int op){
  if(l > e || r < s) return;
  if(l >= s && r <= e){
    spread(l,r,ind);
    lazyMn[ind] = min(val,lazyMn[ind]);
    seg[ind] = min(seg[ind],val);
    return;
  }
  spread(l,r,ind);
  int md = (l + r) / 2;
  updateMn(l,md,ind * 2,op);updateMn(md + 1,r,ind * 2 + 1,op);
  seg[ind] = max(seg[ind * 2],seg[ind * 2 + 1]);
}
void updateMx(int l,int r,int ind,int op){
  if(l > e || r < s) return;
  if(l >= s && r <= e){
    lazyMx[ind] = max(lazyMx[ind],val);
    seg[ind] = max(seg[ind],val);
    return;
  }
  spread(l,r,ind);
  int md = (l + r) / 2;
  updateMx(l,md,ind * 2,op);updateMx(md + 1,r,ind * 2 + 1,op);
  seg[ind] = max(seg[ind * 2],seg[ind * 2 + 1]);
}
int query(int l = 1,int r = N,int ind = 1){
  spread(l,r,ind);
  if(l > e || r < s) return 0;
  if(l >= s && r <= e) {
    return seg[ind];
  }
  int md = (l + r) / 2;
  return max(query(l,md,ind * 2),query(md + 1,r,ind * 2 + 1));
}
void printseg(){
  int p2 = 1;
  for(int i = 1;i <= N;i++){
    spread(1,2,i);
    cout<<seg[i]<<' ';
    if(p2 * 2 - 1 == i){
      cout<<'\n';
      p2 = p2 * 2;
    }
  }
}
void buildWall(int n,int k,int op[],int left[],int right[],int height[],int finalHeight[]){
  N = exp2(ceil(log2(n)));
  for(int i = 0; i<= N;i++){
    lazyMn[i] = 1e9;
    lazyMx[i] = -1;
  }
  bool sec = 0;
  for(int i = 0;i < k;i++){
    s = left[i] + 1,e = right[i] + 1;
    val = height[i];
    if(op[i] == 1){
      updateMx(1,N,1,i);
    }else{
      updateMn(1,N,1,i);
    }
  }
  // printseg();
  for(int i = 0 ; i <n;i++){
    s = e = i + 1;
    finalHeight[i] = query();
  }
}
// main()
// {
//   int n;
//   int k;
//
//   int i, j;
//   int status = 0;
//
//   status = scanf("%d%d", &n, &k);
//   assert(status == 2);
//
//   int* op = (int*)calloc(sizeof(int), k);
//   int* left = (int*)calloc(sizeof(int), k);
//   int* right = (int*)calloc(sizeof(int), k);
//   int* height = (int*)calloc(sizeof(int), k);
//   int* finalHeight = (int*)calloc(sizeof(int), n);
//
//   for (i = 0; i < k; i++){
//     status = scanf("%d%d%d%d", &op[i], &left[i], &right[i], &height[i]);
//     assert(status == 4);
//   }
//
//   buildWall(n, k, op, left, right, height, finalHeight);
//
//   for (j = 0; j < n; j++)
//     printf("%d ", finalHeight[j]);
//
//   return 0;
// }

Compilation message

wall.cpp: In function 'void buildWall(int, int, int*, int*, int*, int*, int*)':
wall.cpp:85:8: warning: unused variable 'sec' [-Wunused-variable]
   85 |   bool sec = 0;
      |        ^~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2396 KB Output is correct
2 Correct 2 ms 2504 KB Output is correct
3 Incorrect 2 ms 2396 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 2396 KB Output is correct
2 Correct 110 ms 16136 KB Output is correct
3 Correct 134 ms 10716 KB Output is correct
4 Incorrect 400 ms 23380 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 2 ms 2396 KB Output is correct
3 Incorrect 1 ms 2396 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 2392 KB Output is correct
2 Correct 2 ms 2396 KB Output is correct
3 Incorrect 2 ms 2392 KB Output isn't correct
4 Halted 0 ms 0 KB -