oj.uz

Submission #766840

# Submission time Handle Problem Language Result Execution time Memory
766840 2023-06-26T08:07:24 Z emad234 Wall (IOI14_wall) C++17
0 / 100
 128 ms 13932 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];
pair<int,int>lazyMx[mxN],lazyMn[mxN];
int N,s,e,val;
void spread(int l,int r, int ind){
  if(l != r){
    if(lazyMx[ind].S < lazyMn[ind].S){
      seg[ind * 2] = max(seg[ind * 2],lazyMx[ind].F);
      seg[ind * 2] = min(seg[ind * 2],lazyMn[ind].F);
      seg[ind * 2 + 1] = max(seg[ind * 2 + 1],lazyMx[ind].F);
      seg[ind * 2 + 1] = min(seg[ind * 2 + 1],lazyMn[ind].F);
    }else{
      seg[ind * 2] = min(seg[ind * 2],lazyMn[ind].F);
      seg[ind * 2] = max(seg[ind * 2],lazyMx[ind].F);
      seg[ind * 2 + 1] = min(seg[ind * 2 + 1],lazyMn[ind].F);
      seg[ind * 2 + 1] = max(seg[ind * 2 + 1],lazyMx[ind].F);
    }
    if(lazyMx[ind * 2].S < lazyMx[ind].S) lazyMx[ind * 2] = lazyMx[ind];
    if(lazyMn[ind * 2].S < lazyMn[ind].S)  lazyMn[ind * 2] = lazyMn[ind];

    if(lazyMx[ind * 2 + 1].S < lazyMx[ind].S) lazyMx[ind * 2 + 1] = lazyMx[ind];
    if(lazyMn[ind * 2 + 1].S < lazyMn[ind].S)  lazyMn[ind * 2 + 1] = lazyMn[ind];
  }
  lazyMn[ind] = {1e9,-1};
  lazyMx[ind] = {-1,-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] = {val,op};
    seg[ind] = min(seg[ind],val);
    spread(l,r,ind);
    return;
  }
  int md = (l + r) / 2;
  updateMn(l,md,ind * 2,op);updateMn(md + 1,r,ind * 2 + 1,op);
}
void updateMx(int l,int r,int ind,int op){
  if(l > e || r < s) return;
  if(l >= s && r <= e){
    spread(l,r,ind);
    lazyMx[ind] = {val,op};
    seg[ind] = max(seg[ind],val);
    spread(l,r,ind);
    return;
  }
  int md = (l + r) / 2;
  updateMx(l,md,ind * 2,op);updateMx(md + 1,r,ind * 2 + 1,op);
}
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) {
    spread(l,r,ind);
    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,-1};
    lazyMx[i] = {-1,-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 printseg()':
wall.cpp:69:7: warning: unused variable 'p2' [-Wunused-variable]
   69 |   int p2 = 1;
      |       ^~
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 1 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Incorrect 2 ms 340 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 212 KB Output is correct
2 Correct 100 ms 13932 KB Output is correct
3 Incorrect 128 ms 8496 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 212 KB Output is correct
2 Correct 3 ms 452 KB Output is correct
3 Incorrect 2 ms 368 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 312 KB Output is correct
2 Correct 2 ms 456 KB Output is correct
3 Incorrect 2 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -